Betrachten Sie die positiven ganzzahligen Potenzen von fünf in Dezimalzahl. Hier sind die ersten 25, rechtsbündig:
X 5^X
1 5
2 25
3 125
4 625
5 3125
6 15625
7 78125
8 390625
9 1953125
10 9765625
11 48828125
12 244140625
13 1220703125
14 6103515625
15 30517578125
16 152587890625
17 762939453125
18 3814697265625
19 19073486328125
20 95367431640625
21 476837158203125
22 2384185791015625
23 11920928955078125
24 59604644775390625
25 298023223876953125
Beachten Sie, dass die rechte Spalte der Mächte alle ist 5
. Die zweite Spalte von rechts ist alles 2
. Die dritte Spalte von rechts, lesen Sie von oben nach unten, wechselt 1
, 6
, 1
, 6
usw. Die nächste Spalte beginnt 3
, 5
, 8
, 0
und dann Zyklen.
Tatsächlich hat jede Spalte (wenn wir weit genug nach unten gehen) eine zyklische Folge von Ziffern, deren Länge doppelt so lang ist wie die des vorherigen Zyklus, mit Ausnahme der ersten 5
und der ersten 2
Zyklen.
N die Spaltennummer beginnend mit N = 1 rechts nennend, sind die ersten paar Zyklen:
N cycle at column N
1 5
2 2
3 16
4 3580
5 17956240
6 3978175584236200
7 19840377976181556439582242163600
8 4420183983595778219796176036355599756384380402237642416215818000
Herausforderung
Geben Sie bei einer positiven Ganzzahl N die Dezimalstellen des Zyklus in Spalte N aus, wie oben beschrieben. Beispielsweise wäre die Ausgabe für N = 4 3580
.
Die Ziffern können als Liste [3, 5, 8, 0]
oder in einem anderen vernünftigen Format ausgegeben werden, solange:
- Die Ziffern sind in der angegebenen Reihenfolge in den Leistungsspalten von oben nach unten angegeben. zB
0853
ist ungültig. - Der Zyklus beginnt mit der höchsten Zahl in seiner Leistungsspalte. zB
5803
ist ungültig, da die 4. Spalte mit3
nicht beginnt5
. - Es wird genau ein Zyklus ausgegeben. zB
358
oder35803
oder35803580
wäre alles ungültig.
Ihr Code muss für mindestens N = 1 bis 30 funktionieren.
Falls gewünscht, können Sie davon ausgehen, dass die Spalten 0-indiziert statt 1-indiziert sind. N = 0 gibt also 5
, N = 1 gibt 2
, N = 2 gibt 16
, N = 3 gibt 3580
usw.
Der kürzeste Code in Bytes gewinnt .
Vielen Dank an Downgoat und DJ für die Herausforderungsunterstützung.
2^(N-2)
außerN = 1
Antworten:
Python 2,
626158 BytesNullbasiert. Ich gehe davon aus, dass die L-Suffixe akzeptabel sind.
Ausgabe:
Vorherige Lösung:
Erläuterung:
Die
range(2**n/2)
verwendet die Beobachtung, dass jeder Zyklus die Länge r = 2 n-1 hat, außer wenn n = 0, so dass wir nur die n-ten Ziffern für 5 m bis 5 m + r - 1 berechnen .Der Start des Zyklus 5 m ist die erste Zahl, die größer als 10 n ist . Das Lösen von 5 m ≥ 10 n ergibt m ≥ n / log 10 5. Hier approximieren wir log 10 5 ≈ 0.7, das zerfällt, wenn n = 72 ist. Wir könnten weitere Ziffern hinzufügen, um die Genauigkeit zu erhöhen:
Die
/ 10**n % 10
in der Schleife extrahieren einfach die gewünschte Ziffer. Eine andere alternative Lösung verwendet die String-Manipulation. Ich habe den Trick~n == -n-1
hier benutzt, um 1 Byte zu entfernen.Ein im Kommentar erwähnter Ausdruck
5**(m+i) / 10**n
kann auf diese Weise weiter vereinfacht werden, was die aktuelle 58-Byte-Antwort ergibt.(Die Division
x/2**n
kann mit bitweiser Rechtsverschiebung erfolgenx>>n
. Aufgrund der Operator-Priorität von Python werden hierdurch leider keine Bytes gespart.) Der Bruch 3/7 kann auch auf ähnliche Weise verbessert werden:quelle
(5**(n*3/7-~i)>>n)%10
. Da Sie eine Potenz von 5 geteilt durch eine (kleinere) Potenz von 10 nehmen, können Sie die Potenz von 5 reduzieren und stattdessen nach rechts verschieben.n/.7 - n
→n*10/7 - n
→n*3/7
. Im Prinzip werden die Ziffern aus der kleinsten Potenz von 5 größer als 2ⁿ extrahiert (mit 3/7 eine Annäherung für 1 / log₂ (5) ). Auch die Verwendungrange(2**n/2or 1)
stattdessen gibt Ihnen konsistente Ausgabe.(x>>n)%10
Es gibt keine Verbesserung gegenüber,x/2**n%10
daher verwende ich derzeit keine Bitverschiebung, da es möglicherweise eine Möglichkeit gibt, das Gemeinsame herauszufiltern2**n
.2**n
, scheint aber etwas länger:int(5**(-~i-n*log(2,5)%1))%10
(habe ichint(n*log(2,5))-n*log(2,5)
als vereinfacht-(n*log(2,5)%1)
).2**n
Argument hier und im Bereich.Gleichstrom , 72 Bytes
0-basierte Indizierung.
Hierbei wird eine exakte Ganzzahlarithmetik verwendet - keine Logarithmus-Annäherungen. Es wird bis zur Speicherkapazität des Computers arbeiten.
Probieren Sie das DC-Programm online!
Der DC-Code kann in eine Bash-Lösung umgewandelt werden:
Bash + GNU-Dienstprogramme,
967775 BytesProbieren Sie die Bash-Version online aus!
quelle
Mathematica,
666052 BytesAnonyme Funktion, 0-indiziert. Verwendet die Approximation von log5 (10) (≈ 0.7)
Wie es funktioniert?
Nehmen Sie einen größeren Wert aus 2 ^ (Eingabe) / 2 und 1. Generieren Sie {1. .diese Zahl}.
Eingabe hinzufügen / .7
Erhöhen Sie 5 zur Potenz des Ergebnisses (Generieren von Potenzen von 5), dividieren Sie durch 10 ^ Eingabe (Entfernen der Ziffern rechts von der gewünschten Spalte).
Übernehmen Sie modulo 10 und nehmen Sie die Ziffer (die gewünschte Spalte).
Genaue Version, 58 Bytes
quelle
JavaScript (ES7),
7876 Bytes0-indiziert, dh
f(0)
gibt2
.Testschnipsel
Code-Snippet anzeigen
Das Snippet wird
Math.pow
anstelle von**
für die browserübergreifende Kompatibilität verwendet.quelle
CJam, 35
Probieren Sie es online aus
Es ist platzsparend und nicht sonderlich langsam. Die Eingabe von 30 auf meinem Computer dauerte mehrere Minuten (mithilfe des Java-Interpreters).
quelle
Jelly ,
2621 Bytes-2 Bytes unter Verwendung der 0,7- Näherungsidee von kennytm
Probieren Sie es online! (Zeitüberschreitung für n> 15 )
Gibt eine Liste mit ganzen Zahlen und Ziffern zurück.
Null basiert. Theoretisch funktioniert für n <= 72 (ersetzen
.7
durch5l⁵¤
, um die Gleitkommagenauigkeit zu erhalten).Wie?
Lokal: Der Arbeitsspeicher für n = 17 stieg auf ca. 750 MB und stieg dann auf ca. 1 GB an . für n = 18 erreichte langsam 2.5GB dann auf rund gespickt 5GB .
quelle
Perl 6 , 52 Bytes
Funktioniert für beliebig hohe Eingaben bei ausreichendem Speicher (dh ohne Logarithmus-Approximation) .
Gibt eine Liste mit Ziffern zurück.
Probieren Sie es online!
Wie es funktioniert
Der Teil "Überspringen von Elementen" funktioniert folgendermaßen:
//
ist der Operator "defined or".|()
Gibt einen leeren Slip zurück , der sich als 0-Elemente in der äußeren Liste auflöst und im Wesentlichen sicherstellt, dass das aktuelle Element übersprungen wird.Der Edge-Case
n=1
funktioniert gut, weil2**n/4
wird0.5
, und^(0.5)
bedeutet0 ..^ 0.5
aka "Ganzzahlen zwischen 0 (inklusive) und 0,5 (nicht inklusive)", dh eine Liste mit dem einzelnen Element 0.quelle
J, 50 Bytes
Hinweis: muss in erweiterter Anzahl übergeben werden
Verwendungszweck:
quelle
Haskell , 73 Bytes
Probieren Sie es online! Verwendet die 0-Indizierung.
Erläuterung:
quelle
Batch, 294 Bytes
Gibt jede Ziffer in einer eigenen Zeile aus. Funktioniert durch Berechnen der Potenzen von 5 Longhands, funktioniert jedoch nur,
N=33
weil 32-Bit-Ganzzahlen verwendet werden, um die Anzahl der zu druckenden Stellen zu ermitteln.s
enthält die (umgekehrt) letztenN
Ziffern der aktuellen Leistung von 5, währendt
enthältx
S als Polsterung verwendet, obwohl diex=0
sie evaluieren als Null macht , wenn die nächste Leistung berechnet wird. Beispiel fürN=4
:quelle
JavaScript (ES6), 73 Byte
1-indiziert. Etwas kürzer als die ES7-Antwort , scheitert jedoch 3 Schritte früher (bei N = 13).
Demo
Code-Snippet anzeigen
quelle
PHP> = 7.1, 104 Bytes
PHP Sandbox Online
quelle