Herausforderungsbeschreibung
Für jede positive ganze Zahl ngibt es eine Zahl, deren Form 111...10...000durch neine Dezimalzahl teilbar ist , die mit allen beginnt und mit allen 1endet 0. Dies ist sehr einfach zu beweisen: Wenn wir eine Reihe n+1verschiedener Zahlen in Form von 111...111(allen 1) nehmen, geben mindestens zwei von ihnen den gleichen Rest nach der Division durch n(nach dem Taubenprinzip). Die Differenz dieser beiden Zahlen ist teilbar durch nund hat die gewünschte Form. Ihr Ziel ist es, ein Programm zu schreiben, das diese Nummer findet.
Eingabebeschreibung
Eine positive ganze Zahl.
Ausgabebeschreibung
Eine Zahl pin Form von 111...10...000, so dass p ≡ 0 (mod n). Wenn Sie mehr als eine finden - zeigen Sie eine davon an (muss nicht die kleinste sein).
Anmerkungen
Ihr Programm muss die Antwort innerhalb eines angemessenen Zeitraums geben. Was bedeutet, dass Brute-Forcing nicht erlaubt ist:
p = 0
while (p != 11..10.00 and p % n != 0)
p++
Weder ist dies:
do
p = random_int()
while (p != 11..10.00 and p % n != 0)
Das Durchlaufen der Zahlen in Form von 11..10..00ist erlaubt.
Ihr Programm muss keine willkürlich großen Eingaben verarbeiten - die Obergrenze ist die Obergrenze Ihrer Sprache.
Beispielausgaben
2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110
quelle
1mindestens eine enthalten0, sonst0ist eine Lösung für jede Eingabe. (Wäre aber gut, dies zu klären.)1sollte funktionieren.Antworten:
Mathematica, 29 Bytes
Code von Martin Büttner .
Bei der Eingabe
nwird die Zahl mit9*ϕ(n)Einsen gefolgt vonnNullen ausgegeben , wobeiϕes sich um die Euler-Totientenfunktion handelt . Mit einer Funktionphikönnte dies in Python ausgedrückt werden alsEs würde ausreichen,
n!stattdessen die Fakultät zu verwendenϕ(n), aber das Drucken, das viele nicht hat, hat eine angemessene Laufzeit.Behauptung:
9*ϕ(n)Einsen gefolgt vonnNullen ist ein Vielfaches vonn.Beweis: Zunächst wollen wir beweisen dies für den Fall , dass
nnicht ein Vielfaches von ist2,3oder5. Wir werden zeigen, dass die Zahl, die ausϕ(n)Einsen besteht, ein Vielfaches von `n ist.Die Anzahl der
kEinsen ist gleich(10^k-1)/9. Danes sich nicht um ein Vielfaches von handelt3, ist dies ein Vielfaches vonn, solange10^k-1es ein Faktor vonnoder gleichwertig mit if ist10^k = 1 (mod n). Beachten Sie, dass diese Formulierung deutlich macht, dass, wenn siekfür die Anzahl von Einsen funktioniert, dies auch für ein Vielfaches von funktioniertk.Wir wollen
kalso ein Vielfaches der Ordnung vonkin der multiplikativen Gruppe modulo n sein . Nach dem Satz von Lagrange ist jede solche Ordnung ein Teiler der Größe der Gruppe. Da es sich bei den Elementen der Gruppe um die Zahl von1bis handeltn, die relativ hochnist, ist ihre Größe die Euler-Totientenfunktionϕ(n). Wir haben also gezeigt10^ϕ(n) = 1 (mod n), dass die Anzahl derϕ(n)Einsen ein Vielfaches von `n ist.Lassen Sie uns nun mögliche Faktoren von
3in behandelnn. Wir wissen, dass dies10^ϕ(n)-1ein Vielfaches von istn, aber(10^ϕ(n)-1)/9möglicherweise nicht. Ist(10^(9*ϕ(n))-1)/9aber ein Vielfaches von,9weil es aus9*ϕ(n)Einsen besteht , also ist die Summe seiner Ziffern ein Vielfaches von9. Und wir haben festgestellt, dass das Multiplizieren des Exponentenkmit einer Konstanten die Teilbarkeit bewahrt.Wenn Sie
nnun die Faktoren2's und5' s haben, müssen Sie am Ende der Ausgabe Nullen hinzufügen. Es ist weit mehr als ausreichend,nNullen zu verwenden (log_2(n)würde tatsächlich reichen). Wenn also unsere Eingabenso aufgeteilt wirdn = 2^a * 5^b * m, genügt es, wenn9*ϕ(m)diejenigen ein Vielfaches von sindn, multipliziert mit10^neinem Vielfachen von2^a * 5^b. Und danes sich um ein Vielfaches von handeltm, ist es ausreichend,9*ϕ(n)solche zu verwenden . Es funktioniert also,9*ϕ(n)Einsen gefolgt vonnNullen zu haben.quelle
EulerPhiFunktion hat. Die eigentliche Implementierung hat nichts Verblüffendes an sich, daher würde ich dies voll und ganz für seine eigene Arbeit halten.Python 2, 44 Bytes
Wenn
jeine Potenz von 10 wie 1000 istj/9,j/9*jgibt die Bodenteilung eine Zahl aus Einsen wie 111 an. Geben Sie also Einsen gefolgt von einer gleichen Zahl von Nullen wie 111000 an.Die Funktion testet rekursiv Zahlen dieser Form und probiert immer höhere Potenzen von 10 aus, bis wir eine finden, die ein Vielfaches der gewünschten Zahl ist.
quelle
Pyth, 11 Bytes
Testsuite
Grundsätzlich setzt es immer wieder eine 1 vor und eine 0 zurück, bis die Zahl durch die Eingabe teilbar ist.
Erläuterung:
quelle
Haskell, 51 Bytes
Mit xnors Ansatz. nimi hat ein byte gespeichert!
quelle
CJam,
282519 Bytes6 Bytes gespart mit der Beobachtung von xnor, dass wir nur die Nummern des Formulars betrachten müssen .
1n0nTeste es hier.
Erläuterung
quelle
Mathematica,
140-55BytesDank des 1 ^ n0 ^ n-Tricks von xnor wurden viele Bytes entfernt.
Minimalwert,
140156 Bytes Dies ergibt die kleinstmögliche Lösung.Es berechnet, wie viele Nullen erforderlich sind, und überprüft dann alle möglichen
1Zählungen, bis es funktioniert. Es kann eine Zahl ohne 0 ausgegeben werden, dies kann jedoch durch Hinzufügen eines<>"0"Rechts vor dem Finale behoben werden&.quelle
Haskell, 37 Bytes
Dies nutzt die Tatsache dass es funktioniert, um
9*phi(n)diejenigen zu haben , wophidie Euler-Totientenfunktion ist. Hier wird es unter Verwendunggcdund Filtern implementiert , wobei eine Ziffer für jeden Wert erzeugt wirdi, der im Bereich1und relativ hoch ist9*n. Es reicht auch aus, so viele Nullen zu verwenden.quelle
JavaScript (ES6), 65 Byte
Bearbeiten 2 Bytes, die dank @Neil gespeichert wurden
Es funktioniert innerhalb der Grenzen des numerischen Javascript-Typs mit 17 signifikanten Ziffern. (Also ziemlich begrenzt)
Weniger golfen
quelle
for(m=n;?for(m=n;!m[16];)if(!((m+=0)%a)).Perl 5, 26 Bytes
Beinhaltet ein Byte für
-n(-M5.01ist kostenlos)quelle
Salbei, 33 Bytes
Dies verwendet die Methode von xnor , um die Ausgabe zu erzeugen.
Probieren Sie es online aus
quelle
bc, 58 bytes
Probenergebnisse
quelle
Gleichstrom, 27 Bytes
Dies definiert eine Funktion
f, die ihr Argument in der Variablen erwartetn. Um es als Programm?sn lfx pzu verwenden, aus stdin zu lesen, die Funktion aufzurufen und das Ergebnis in stdout auszugeben. Variablemund Stapeloberseite müssenOdsmzuvor (durch Wiederholen ) auf 10 zurückgesetzt werdenfsie wieder verwendet werden können.Ergebnisse:
quelle