5, 2, 16, 3580, Was kommt als nächstes?

51

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, 6usw. Die nächste Spalte beginnt 3, 5, 8, 0und 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 5und der ersten 2Zyklen.

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 0853ist ungültig.
  • Der Zyklus beginnt mit der höchsten Zahl in seiner Leistungsspalte. zB 5803ist ungültig, da die 4. Spalte mit 3nicht beginnt 5.
  • Es wird genau ein Zyklus ausgegeben. zB 358oder 35803oder 35803580wä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 3580usw.

Der kürzeste Code in Bytes gewinnt .

Vielen Dank an Downgoat und DJ für die Herausforderungsunterstützung.

Calvins Hobbys
quelle
Die Reihenfolge macht dies ziemlich schwierig.
Dennis
9
Die Zykluslänge ist immer 2^(N-2)außerN = 1
JungHwan Min 25.02.17
1
Können Annäherungen verwendet werden? Die Ausgabe ist gültig bis N = 72 , was theoretisch 2,36E + 21 Stellen ergeben würde.
JungHwan Min
Ist diese Reihenfolge im OEIS?
StarWeaver
@ StarWeaver Nope.
Mego

Antworten:

26

Python 2, 62 61 58 Bytes

Nullbasiert. Ich gehe davon aus, dass die L-Suffixe akzeptabel sind.

lambda n:[5**(n*3/7-~i)/2**n%10for i in range(2**n/2or 1)]

Ausgabe:

0 [5]
1 [2]
2 [1, 6]
3 [3, 5, 8, 0]
4 [1, 7, 9, 5, 6, 2, 4, 0]
5 [3, 9, 7, 8, 1, 7, 5, 5, 8, 4, 2, 3, 6, 2, 0, 0]
6 [1, 9, 8, 4, 0, 3, 7, 7, 9, 7, 6, 1, 8, 1, 5, 5, 6, 4, 3, 9, 5, 8, 2, 2, 4, 2L, 1L, 6L, 3
L, 6L, 0L, 0L]
7 [4, 4, 2, 0, 1, 8, 3, 9, 8, 3, 5, 9, 5, 7, 7, 8, 2, 1, 9, 7, 9, 6, 1, 7, 6L, 0L, 3L, 6L,
3L, 5L, 5L, 5L, 9L, 9L, 7L, 5L, 6L, 3L, 8L, 4L, 3L, 8L, 0L, 4L, 0L, 2L, 2L, 3L, 7L, 6L, 4L,
 2L, 4L, 1L, 6L, 2L, 1L, 5L, 8L, 1L, 8L, 0L, 0L, 0L]

Vorherige Lösung:

lambda n:[5**int(n/.7-~i)/10**n%10for i in range(2**n/2or 1)]
lambda n:[str(5**int(n/.7-~i))[~n]for i in range(2**n/2)]or 5

Erläuterung:

def f(n):
    r = max(2**n / 2, 1)
    m = int(n/0.7 + 1)
    for i in range(r):
        yield (5**(m+i) / 10**n) % 10

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:

| approximation             | valid until        | penalty   |
|---------------------------|--------------------|-----------|
| .7                        | n = 72             | +0 bytes  |
| .699                      | n = 137            | +2 bytes  |
| .69897                    | n = 9297           | +4 bytes  |
| .698970004                | n = 29384          | +8 bytes  |
| .6989700043               | n = 128326         | +9 bytes  |
| .6989700043360189         | too large to check | +15 bytes |
| import math;math.log10(5) | same as above      | +23 bytes |

Die / 10**n % 10in 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**nkann auf diese Weise weiter vereinfacht werden, was die aktuelle 58-Byte-Antwort ergibt.

Bildbeschreibung hier eingeben

(Die Division x/2**nkann mit bitweiser Rechtsverschiebung erfolgen x>>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:

| approximation                   | valid until         | penalty   |
|---------------------------------|---------------------|-----------|
| n*3/7                           | n = 72              | +0 bytes  |
| n*31/72                         | n = 137             | +2 bytes  |
| n*59/137                        | n = 476             | +3 bytes  |
| n*351/815                       | n = 1154            | +4 bytes  |
| n*643/1493                      | n = 10790           | +5 bytes  |
| n*8651/20087                    | n = 49471           | +7 bytes  |
| int(n*.43067655807339306)       | too large to check  | +20 bytes |
| import math;int(n/math.log2(5)) | same as above       | +26 bytes |
kennytm
quelle
1
(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 - nn*10/7 - nn*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 Verwendung range(2**n/2or 1)stattdessen gibt Ihnen konsistente Ausgabe.
Primo
1
@primo Danke, aktualisiert. (x>>n)%10Es gibt keine Verbesserung gegenüber, x/2**n%10daher verwende ich derzeit keine Bitverschiebung, da es möglicherweise eine Möglichkeit gibt, das Gemeinsame herauszufiltern 2**n.
Kennytm
interessante Idee ausklammern 2**n, scheint aber etwas länger: int(5**(-~i-n*log(2,5)%1))%10(habe ich int(n*log(2,5))-n*log(2,5)als vereinfacht -(n*log(2,5)%1)).
Primo
@primo Interessant, aber was ich meine, ist das 2**nArgument hier und im Bereich.
Kennytm
10

Gleichstrom , 72 Bytes

[3Q]sq2?dsa^1+2/dsusk[Ola^/O%plk1-dsk1>q]sp1[d5r^dOla^<psz1+d4/lu>t]dstx

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, 96 77 75 Bytes

u=$[(2**$1+1)/2]
dc -e "[O$1^/O%p]sp1[d5r^dO$1^<psz1+d4/$u>t]dstx"|head -$u

Probieren Sie die Bash-Version online aus!

Mitchell Spector
quelle
9

Mathematica, 66 60 52 Bytes

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/.7]/10^#,10]&

Anonyme Funktion, 0-indiziert. Verwendet die Approximation von log5 (10) (≈ 0.7)

Wie es funktioniert?

Range@Max[2^#/2,1]

Nehmen Sie einen größeren Wert aus 2 ^ (Eingabe) / 2 und 1. Generieren Sie {1. .diese Zahl}.

...+#/.7

Eingabe hinzufügen / .7

5^Floor[...]/10^#

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).

Mod[ ...,10]

Übernehmen Sie modulo 10 und nehmen Sie die Ziffer (die gewünschte Spalte).

Genaue Version, 58 Bytes

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/5~Log~10]/10^#,10]&
JungHwan min
quelle
5

JavaScript (ES7), 78 76 Bytes

f=(N,z=5,s,X=2**N,q=z/10**N|0)=>s|q?X>0?q+f(N,z*5%10**-~N,1,X-2):"":f(N,z*5)

0-indiziert, dh f(0)gibt2 .

Testschnipsel

Das Snippet wird Math.powanstelle von **für die browserübergreifende Kompatibilität verwendet.

ETHproductions
quelle
4

CJam, 35

5ri(:N.7/i)#2N(#mo{_AN#/o5*AN)#%}*;

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).

aditsu
quelle
3

Jelly , 26 21 Bytes

-2 Bytes unter Verwendung der 0,7- Näherungsidee von kennytm

2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵

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 .7durch5l⁵¤ , um die Gleitkommagenauigkeit zu erhalten).

Wie?

2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵ - Main link: n
2*                    - 2 raised to the power of n
  H                   - halved: 2 raised to the power of n-1
   Ċ                  - ceiling: adjust 2**-1 = 0.5 up to 1 for the n=0 edge case
    R                 - range: [1,2,...,ceiling(2**(n-1))] - has length of the period
         $            - last two links as a monad:
      ÷.7             -     divide by 0.7 (approximation of log(5, 10), valid up to n=72)
     +                - add (vectorises)
          Ḟ           - floor (vectorises)
             5        - 5
           *@         - exponentiate (vectorises) with reversed @arguments
                  ¤   - nilad followed by link(s) as a nilad
               ⁵      -     10
                 ⁸    -     left argument, n
                *     -     exponentiate: 10 raised to the power of n
              :       - integer division: strips off last n digits
                   %⁵ - mod 10: extracts the last digit

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 .

Jonathan Allan
quelle
3

Perl 6 , 52 Bytes

->\n{(map {.comb[*-n]//|()},(5 X**1..*))[^(2**n/4)]}

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

->\n{                                              }  # A lambda with argument n.
                            (5 X**1..*)               # The sequence 5, 25, 125, 625...
      map {               },                          # Transform each element as such:
           .comb[*-n]                                 #   Extract the n'th last digit,
                     //|()                            #   or skip it if that doesn't exist.
     (                                 )[^(2**n/4)]   # Return the first 2^(n-2) elements.

Der Teil "Überspringen von Elementen" funktioniert folgendermaßen:

  • Das Indizieren einer Liste mit einem unzulässigen Index gibt einen Fehler zurück , der als "undefinierter" Wert gilt.
  • // 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=1funktioniert gut, weil 2**n/4wird 0.5, und ^(0.5)bedeutet 0 ..^ 0.5aka "Ganzzahlen zwischen 0 (inklusive) und 0,5 (nicht inklusive)", dh eine Liste mit dem einzelnen Element 0.

smls
quelle
2

J, 50 Bytes

(2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]

Hinweis: muss in erweiterter Anzahl übergeben werden

Verwendungszweck:

   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580
ljeabmreosn
quelle
2
Warum die Gegenstimme?
Ljeabmreosn
2

Haskell , 73 Bytes

f 0="5"
f n=take(2^(n-1))[reverse x!!n|x<-show<$>iterate(*5)1,length x>n]

Probieren Sie es online! Verwendet die 0-Indizierung.

Erläuterung:

f 0="5"              -- if the input is 0, return "5"
f n=                 -- otherwise for input n
  take(2^(n-1))      -- return the first 2^(n-1) elements of the list
    [reverse x!!n    -- of the nth column of x
      |x<-show<$>    --    where x is the string representation
        iterate(*5)1 --    of the elements of the infinite list [5,25,125,...]
      ,length x>n    -- if x has at least n+1 columns
    ]                -- this yields a list of characters, which is equivalent to a string
Laikoni
quelle
1

Batch, 294 Bytes

@echo off
if %1==1 echo 5
set/a"l=1<<%1-2,x=0,s=1
set t=
for /l %%i in (2,1,%1)do call set t=%%t%%x
:l
if %l%==0 exit/b
set t=%s%%t%
set s=
set c=
:d
set/ac+=%t:~,1%*5,r=c%%10,c/=10
set s=%s%%r%
set t=%t:~1%
if "%t%"=="" echo %r%&set/al-=1&goto l
if %c%%t:~,1%==0x goto l
goto d

Gibt jede Ziffer in einer eigenen Zeile aus. Funktioniert durch Berechnen der Potenzen von 5 Longhands, funktioniert jedoch nur, N=33weil 32-Bit-Ganzzahlen verwendet werden, um die Anzahl der zu druckenden Stellen zu ermitteln. senthält die (umgekehrt) letzten NZiffern der aktuellen Leistung von 5, während tenthält xS als Polsterung verwendet, obwohl die x=0sie evaluieren als Null macht , wenn die nächste Leistung berechnet wird. Beispiel für N=4:

s   t
1   xxx (initial values before the first power of 5 is calculated)
5   xxx
52  xx
521 x
526 x
5213    (print 3)
5265    (print 5)
5218    (print 8)
5260    (print 0)
Neil
quelle
1

JavaScript (ES6), 73 Byte

1-indiziert. Etwas kürzer als die ES7-Antwort , scheitert jedoch 3 Schritte früher (bei N = 13).

n=>(g=x=>k>>n?'':(s=''+x*5%1e15)[n-1]?s.substr(-n,1)+g(s,k+=4):g(s))(k=1)

Demo

Arnauld
quelle
0

PHP> = 7.1, 104 Bytes

for($s=1;$i++<2**(-1+$a=$argn);)~($s=bcmul($s,5))[-$a]?$g.=$s[-$a]:0;echo substr($g,0,max(2**($a-2),1));

PHP Sandbox Online

Jörg Hülsermann
quelle