Eine Anmerkung zu N!

32

JE Maxfield hat folgenden Satz bewiesen (siehe DOI: 10.2307 / 2688966 ):

Wenn A eine positive ganze Zahl mit m Ziffern ist, gibt es eine positive ganze Zahl N so dass die ersten m Ziffern von N!bildet die ganze Zahl A .

Herausforderung

Ihre Herausforderung ist gegeben, einige A1 finden eine entsprechende .N1

Einzelheiten

  • N!repräsentiert die FakultätN!=123N vonN .
  • Die Ziffern von A in unserem Fall als Basis 10 verstehen .
  • Ihre Einreichung sollte für beliebige A1 funktionieren, vorausgesetzt , Sie haben genügend Zeit und Speicher. Es reicht nicht aus, beispielsweise 32-Bit-Typen zur Darstellung von Ganzzahlen zu verwenden.
  • Sie müssen nicht unbedingt ausgeben müssen , die am wenigsten möglich N .

Beispiele

A            N
1            1
2            2
3            9
4            8
5            7
6            3
7            6
9           96
12           5
16          89
17          69
18          76
19          63
24           4
72           6
841      12745
206591378  314

Das kleinstmögliche N für jedes A finden Sie unter https://oeis.org/A076219

Fehler
quelle
26
Ich ... warum hat er diesen Satz bewiesen? Ist er gerade eines Tages aufgewacht und hat gesagt "Ich werde das lösen!" oder hat es einen zweck erfüllt?
Magic Octopus Urn
11
@MagicOctopusUrn Haben Sie sich vorher noch nie mit einem Zahlentheoretiker befasst?
Brady Gilg
2
Hier ist der Beweis, dass es jemanden interessiert.
Esolanging Fruit

Antworten:

14

Python 2 , 50 Bytes

f=lambda a,n=2,p=1:(`p`.find(a)and f(a,n+1,p*n))+1

Probieren Sie es online!

Dies ist eine Variation der unten erläuterten 47-Byte-Lösung, die angepasst wurde, um 1zur Eingabe zurückzukehren '1'. (Wir addieren also 1eher den vollständigen Ausdruck als den rekursiven Aufruf und beginnen mit dem Zählen n==2, um eine Tiefenebene zu entfernen und das Ergebnis für alle Nichteingaben '1'auszugleichen.)

Python 2 , 45 Bytes (Karten 1 bis True)

f=lambda a,n=2,p=1:`-a`in`-p`or-~f(a,n+1,p*n)

Dies ist eine weitere Variante von @Jo King und @xnor, die Eingaben als Zahl akzeptiert und Truezur Eingabe zurückgibt 1. Einige Leute denken, dass dies ein faires Spiel ist, aber ich persönlich finde es ein bisschen komisch.

Aber es kostet nur 3 Bytes, um das icky Boolesche Ergebnis zu verpacken +(), was uns eine kürzere "nette" Lösung gibt:

Python 2 , 48 Bytes

f=lambda a,n=2,p=1:+(`-a`in`-p`)or-~f(a,n+1,p*n)

Dies ist meine vorherige Lösung, die 0zur Eingabe zurückgibt '1'. Es wäre gültig gewesen, wenn es sich um eine nicht negativeN Frage gehandelt hätte .

Python 2 , 47 Bytes (ungültig)

f=lambda a,n=1,p=1:`p`.find(a)and-~f(a,n+1,p*n)

Probieren Sie es online!

Nimmt einen String als Eingabe wie f('18').

Der Trick dabei ist x.find(y) == 0genau das, wann x.startswith(y).

Der and-Ausdruck schließt `p`.find(a)mit dem Ergebnis kurz 0, sobald er mit `p`beginnt a. Andernfalls wird es ausgewertet -~f(a,n+1,p*n), id est 1 + f(a,n+1,p*n).

Das Endergebnis ist 1 + (1 + (1 + (... + 0))), nSchichten tief, so n.

Lynn
quelle
Schöne Lösung übrigens. Ich arbeitete an der gleichen Methode, berechnete jedoch die Fakultät für jede Iteration. Die Implementierung Ihres Ansatzes hat mir +1sowieso ein paar Bytes erspart.
Shaggy
1
Für Ihre True-for-1-Version können Sie die Basisfallbedingung unter aAngabe einer Zahl verkürzen .
27.
@ Xnor Ich hätte nicht gedacht, `` -ain -p``, das ist ein ordentlicher Trick :)
Lynn
Wenn der Proof weiterhin gilt, wenn N auf gerade Werte beschränkt ist, gibt diese 45-Byte-Lösung immer eine Zahl aus.
negativ sieben
9

Brachylog , 3 5 Bytes

ℕ₁ḟa₀

Probieren Sie es online!

Übernimmt die Eingabe über die Ausgabevariable und die Ausgabe über die Eingabevariable. (Umgekehrt werden nur beliebige Präfixe der Fakultät der Eingabe gefunden, was nicht ganz so interessant ist.) Zeitüberschreitung beim vorletzten Testfall für TIO, aber beim letzten . Ich habe es zum Zeitpunkt des Schreibens einige Minuten auf meinem Laptop auf 841 ausgeführt und es hat noch keine Antwort ausgespuckt, aber ich glaube daran.

         The (implicit) output variable
   a₀    is a prefix of
  ḟ      the factorial of
         the (implicit) input variable
ℕ₁       which is a positive integer.

Da die einzige Eingabe ḟa₀für 1 nicht funktioniert, ist 1 ein positives Präfix von 1! = 1 1|ḟa₀funktioniert genauso gut.

Außerdem wurde 841 seit fast drei Stunden ausgeführt und es wurde immer noch keine Ausgabe erstellt. Ich denke, die Fakultät jeder ganzen Zahl von 1 bis 12745 zu berechnen, ist nicht gerade schnell.

Nicht verwandte Zeichenfolge
quelle
2
Die Implementierung des faktoriellen Prädikats in Brachylog ist etwas kompliziert, sodass es mit akzeptabler Effizienz in beide Richtungen verwendet werden kann. Man könnte einen viel schnelleren Algorithmus implementieren, um die Fakultät zu berechnen, aber er würde in die andere Richtung extrem langsam ablaufen (dh die ursprüngliche Zahl aus der Fakultät herausfinden).
Fatalize
Oh cool! Wenn ich mir die Quelle anschaue, kann ich nicht sagen, was es alles tut, aber ich kann Ihnen sagen, dass Sie eine Menge guter Gedanken hineingesteckt haben.
Nicht verwandte
7

C ++ (gcc) , 107 95 Bytes mit -lgmpund-lgmpxx

Vielen Dank an die Leute in den Kommentaren für den Hinweis auf ein paar dumme Pannen.

#import<gmpxx.h>
auto f(auto A){mpz_class n,x=1,z;for(;z!=A;)for(z=x*=++n;z>A;z/=10);return n;}

Probieren Sie es online!

Berechnet n!durch Multiplikation (n-1)!durch n , dividiert es dann wiederholt durch 10 bis es nicht mehr größer als die übergebene ganze Zahl ist. An diesem Punkt wird die Schleife beendet, wenn die Fakultät gleich der übergebenen Ganzzahl ist, oder fährt andernfalls mit dem nächsten n .

Neil A.
quelle
Sie müssen keine Flags mehr zählen, das sind also 107Bytes.
AdmBorkBork
Warum brauchen Sie das zweite Semikolon vorher return?
Ruslan
Sie können einen einzelnen Zeichennamen für die Funktion verwenden und ein paar Bytes speichern.
Shaggy
6

Gelee , 8 Bytes

1!w⁼1ʋ1#

Probieren Sie es online!

Nimmt eine Ganzzahl und gibt einen Singleton zurück.

Erik der Outgolfer
quelle
2

Pyth - 8 Bytes

f!x`.!Tz

f              filter. With no second arg, it searches 1.. for first truthy
 !             logical not, here it checks for zero
  x    z       indexof. z is input as string
   `           string repr
    .!T        Factorial of lambda var

Probieren Sie es online aus .

Maltysen
quelle
2

JavaScript, 47 43 Bytes

Ausgabe als BigInt.

n=>(g=x=>`${x}`.search(n)?g(x*++i):i)(i=1n)

Probieren Sie es online!

Ein paar Bytes gespart, indem Lynn versucht hat, die Fakultät zu "bauen", anstatt sie bei jeder Iteration zu berechnen. Stimmen Sie also auch ihrer Lösung zu, wenn Sie diese unterstützen.

Zottelig
quelle
Leider _Ês bU}f1funktioniert in Japt nicht
Verkörperung der Ignoranz
@EmbodimentofIgnorance, ja, das hatte ich auch. Sie könnten das Leerzeichen danach entfernen s.
Shaggy
@EmbodimentofIgnorance, Sie können auch das entfernen, 1wenn zurückgegeben werden 0kann n=1.
Shaggy
3 Bytes weniger:x=i=1n;f=n=>`${x*=++i}`.search(n)?f(n):i
vrugtehagel
@vrugtehagel, das wäre nicht wiederverwendbar.
Shaggy
2

C # (.NET Core) , 69 + 22 = 91 Byte

a=>{var n=a/a;for(var b=n;!(b+"").StartsWith(a+"");b*=++n);return n;}

Probieren Sie es online!

Verwendet, System.Numerics.BigIntegerdie eine usingAussage erfordert .

-1 Byte dank @ExpiredData!

Dana
quelle
1
69 + 22
Abgelaufene Daten
1

Gelee , 16 Bytes

‘ɼ!³;D®ß⁼Lḣ@¥¥/?

Probieren Sie es online!

Erläuterung

‘ɼ                | Increment the register (initially 0)
  !               | Factorial
   ³;             | Prepend the input
     D            | Convert to decimal digits
        ⁼   ¥¥/?  | If the input diguts are equal to...
         Lḣ@      | The same number of diguts from the head of the factorial
      ®           | Return the register
       ß          | Otherwise run the link again
Nick Kennedy
quelle
1

Perl 6 , 23 Bytes

{+([\*](1..*).../^$_/)}

Probieren Sie es online!

Erläuterung

{                     }  # Anonymous code block
   [\*](1..*)            # From the infinite list of factorials
             ...         # Take up to the first element
                /^$_/    # That starts with the input
 +(                  )   # And return the length of the sequence
Scherzen
quelle
1

Kohle , 16 Bytes

⊞υ¹W⌕IΠυθ⊞υLυI⊟υ

Probieren Sie es online!Link ist eine ausführliche Version des Codes. Erläuterung:

⊞υ¹

drücken 1 auf die leere Liste, um mit einem definierten Produkt zu beginnen.

W⌕IΠυθ

Wiederholen, während die Eingabe am Anfang des Produkts der Liste nicht gefunden wird ...

⊞υLυ

... schieben Sie die Länge der Liste auf sich.

I⊟υ

Gibt den zuletzt in die Liste übertragenen Wert aus.

Neil
quelle
1

J , 28 22 Bytes

-6 Bytes dank FrownyFrog

(]+1-0{(E.&":!))^:_&1x

Probieren Sie es online!

ursprüngliche Antwort J , 28 Bytes

>:@]^:(-.@{.@E.&":!)^:_ x:@1

Probieren Sie es online!

  • >:@] ... x:@1Beginnen Sie mit einer erweiterten Genauigkeit 1und erhöhen Sie diese, während Sie ...
  • -.@ Es ist nicht der Fall, dass ...
  • {.@ Die erste Ulme ist ein ...
  • E.&":Alle Teilzeichenfolgen stimmen (nach Eingabe beider Argumente &":) mit der Suche nach der ursprünglichen Eingabe in ... überein.
  • ! Die Fakultät der Zahl, die wir erhöhen
Jonah
quelle
(]+1-0{(E.&":!))^:_&1x
FrownyFrog
Ich liebe die Verwendung von "Fixpunkt", um die traditionelle Zeit zu vermeiden.
Jonah
1

C (gcc) -lgmp, 161 Bytes

#include"gmp.h"
f(a,n,_,b)char*a,*b;mpz_t n,_;{for(mpz_init_set_si(n,1),mpz_init_set(_,n);b=mpz_get_str(0,10,_),strstr(b,a)-b;mpz_add_ui(n,n,1),mpz_mul(_,_,n));}

Probieren Sie es online!

LambdaBeta
quelle
Schlagen Sie strstr(b=mpz_get_str(0,10,_),a)-b;mpz_mul(_,_,n))mpz_add_ui(n,n,1)stattb=mpz_get_str(0,10,_),strstr(b,a)-b;mpz_add_ui(n,n,1),mpz_mul(_,_,n))
Ceilingcat
1

Python 3 , 63 Bytes

f=lambda x,a=2,b=1:str(b).find(str(x))==0and a-1or f(x,a+1,b*a)

Probieren Sie es online!

-24 Bytes dank Jo King

-3 Bytes dank Chas Brown

HyperNeutrino
quelle
@JoKing schön, danke
HyperNeutrino
61 Bytes
Chas Brown
@ChasBrown danke
HyperNeutrino
Ich denke, f=dass das , was Sie in der Kopfzeile haben, für Ihre Bitanzahl zählen soll.
mypetlion
@mypetlion Du bist richtig; Danke, dass du das verstanden hast.
HyperNeutrino
0

Sauber , 88 Bytes

import StdEnv,Data.Integer,Text
$a=hd[n\\n<-[a/a..]|startsWith(""<+a)(""<+prod[one..n])]

Probieren Sie es online!

Definiert $ :: Integer -> Integer.

Verwendet Data.IntegerGanzzahlen beliebiger Größe für E / A.

Οurous
quelle
0

Icon , 65 63 Bytes

procedure f(a);p:=1;every n:=seq()&1=find(a,p*:=n)&return n;end

Probieren Sie es online!

Galen Ivanov
quelle
0

Haskell, 89 Bytes

import Data.List
a x=head$filter(isPrefixOf$show x)$((show.product.(\x->[1..x]))<$>[1..])

Wenn jemand weiß, wie man den erforderlichen Import umgeht, lass es mich wissen.

Mega Man
quelle
Es scheint, dass Sie ausgeben N! und nicht N nach Bedarf.
Fehler