5, 2, 16, 3580, qu'est-ce qui vient ensuite?

51

Considérons les puissances entières positives de cinq en décimal. Voici les 25 premiers, alignés à droite:

 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

Notez que la colonne la plus à droite des puissances est tout 5. La deuxième colonne à droite est tout 2. La troisième colonne de droite, lecture de haut en bas, en alternance 1, 6, 1, 6, etc. La colonne suivante commence 3, 5, 8, 0et puis cycles.

En fait, chaque colonne (si nous descendons assez loin) a une séquence cyclique de chiffres dont la longueur est le double de celle du cycle précédent, à l’exception des cycles initial 5et initial 2.

En appelant N le numéro de colonne, en commençant par N = 1 à droite, les premiers cycles sont les suivants:

N cycle at column N
1 5
2 2
3 16
4 3580
5 17956240
6 3978175584236200
7 19840377976181556439582242163600
8 4420183983595778219796176036355599756384380402237642416215818000

Défi

Avec un entier positif N, indiquez les chiffres décimaux du cycle dans la colonne N, comme décrit ci-dessus. Par exemple, la sortie pour N = 4 serait 3580.

Les chiffres peuvent être générés sous forme de liste [3, 5, 8, 0]ou dans un autre format raisonnable, à condition que:

  • Les chiffres sont dans l'ordre, tels qu'ils sont lus de haut en bas dans les colonnes de puissance. par exemple 0853est invalide.
  • Le cycle commence par le chiffre du haut dans sa colonne de puissance. Par exemple, 5803est invalide car la 4ème colonne commence par 3not 5.
  • Exactement un cycle est sorti. par exemple 358ou 35803ou 35803580seraient tous invalides.

Votre code doit fonctionner pour au moins N = 1 à 30.

Si vous le souhaitez, vous pouvez supposer que les colonnes sont indexées par 0 au lieu d'être indexées par 1. Donc N = 0 donne 5, N = 1 donne 2, N = 2 donne 16, N = 3 donne 3580, etc.

Le code le plus court en octets gagne .

Merci à Downgoat et à DJ pour le support des challenges.

Les passe-temps de Calvin
la source
L'ordre rend cela assez délicat.
Dennis
9
La durée du cycle est toujours 2^(N-2)saufN = 1
JungHwan Min
1
Peut-on utiliser des approximations? La sortie est valide jusqu’à N = 72 , ce qui serait théoriquement une valeur de 2,36E + 21 chiffres.
JungHwan Min
Cette séquence est-elle dans l'OEIS?
StarWeaver
@ StarWeaver Nope.
Mego

Réponses:

26

Python 2, 62 61 58 octets

Base zéro. Je suppose que les suffixes L sont acceptables.

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

Sortie:

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]

Solution précédente:

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

Explication:

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

Le range(2**n/2)utilise l'observation que chaque cycle a une longueur r = 2 n-1 sauf lorsque n = 0, nous calculons donc les nièmes chiffres de 5 m à 5 m + r - 1 .

Le début du cycle 5 m est le premier nombre supérieur à 10 n . La résolution de 5 m ≥ 10 n donne m ≥ n / log 10 5. Ici, nous approchons le log 10 5 0,7 qui sera décomposé lorsque n = 72. Nous pourrions ajouter plus de chiffres pour augmenter la précision:

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

Dans / 10**n % 10la boucle, extrayez simplement le chiffre souhaité. Une autre solution alternative utilise la manipulation de chaîne. J'ai utilisé le truc~n == -n-1 ici pour supprimer 1 octet.

Une mention dans le commentaire, l'expression 5**(m+i) / 10**npeut être encore simplifiée de cette façon, ce qui donne la réponse actuelle de 58 octets.

entrez la description de l'image ici

(La division x/2**npeut être effectuée en utilisant un décalage à droite au niveau du bit x>>n. Malheureusement, en raison de la priorité des opérateurs Python, cela ne sauvegarde aucun octet.) La fraction 3/7 peut également être améliorée de manière similaire:

| 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
la source
1
(5**(n*3/7-~i)>>n)%10. Étant donné que vous prenez une puissance de 5 divisée par une puissance (plus petite) de 10, vous pouvez réduire la puissance de 5 et passer à la place. n/.7 - nn*10/7 - nn*3/7. En premier lieu, il extrait les chiffres de la plus petite puissance de 5 supérieure à 2ⁿ (avec 3/7 approximativement pour 1 / log₂ (5) ). En outre, utiliser à la range(2**n/2or 1)place vous donnera une sortie cohérente.
Primo
1
@primo Merci, mis à jour. (x>>n)%10n'apporte aucune amélioration x/2**n%10, je n'utilise donc pas de décalage pour le moment, car il existe peut-être un moyen d'éliminer le commun 2**n.
Kennytm
out intéressant d'affacturage idée 2**n, semble un peu plus si: int(5**(-~i-n*log(2,5)%1))%10(je l' ai simplifié int(n*log(2,5))-n*log(2,5)comme -(n*log(2,5)%1)).
Primo
@primo Intéressant, mais ce que je veux dire, c'est l' 2**nargument here and the range.
Kenneth
10

dc , 72 octets

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

Indexation basée sur 0.

Ceci utilise l'arithmétique entière exacte - pas d'approximations logarithmiques. Cela fonctionnera jusqu'à la capacité de mémoire de l'ordinateur.

Essayez le programme en ligne!


Le code continu peut être transformé en une solution Bash:

Utilitaires Bash + GNU, 96 77 75 octets

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

Essayez la version Bash en ligne!

Mitchell Spector
la source
9

Mathematica, 66 60 52 octets

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

Fonction anonyme, indexé 0. Utilise l'approximation de log5 (10) (0,7)

Comment ça fonctionne?

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

Prenez le plus grand de 2 ^ (entrée) / 2 et 1. Générez {1.that number}

...+#/.7

Ajouter entrée / .7

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

Augmenter 5 à la puissance du résultat (générer des puissances de 5), diviser par 10 ^ entrée (supprimer les chiffres à droite de la colonne désirée)

Mod[ ...,10]

Appliquez le modulo 10 en prenant le chiffre correspondant (la colonne souhaitée).

Version exacte, 58 octets

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

JavaScript (ES7), 78 76 octets

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 indexé, c'est à dire f(0)donne 2.

Extrait de test

Le fragment utilise à la Math.powplace de la **compatibilité entre navigateurs.

ETHproductions
la source
4

CJam, 35

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

Essayez-le en ligne

C'est peu encombrant et pas très lent, cela a pris plusieurs minutes pour entrer 30 sur mon ordinateur (avec l'interpréteur java).

Aditsu
la source
3

Gelée , 26 21 octets

-2 octets en utilisant 0,7 kennytm idée d'approximation

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

Essayez-le en ligne!(temps mort pour n> 15 )

Retourne une liste d'entiers, les chiffres.
Base zéro. Fonctionne théoriquement pour n <= 72 (remplacez .7par 5l⁵¤, pour obtenir une précision en virgule flottante).

Comment?

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

Localement: la mémoire du groupe de travail pour n = 17 a grimpé à environ 750 Mo, puis à environ 1 Go ; pour n = 18, il a lentement atteint 2,5 Go, puis a atteint environ 5 Go .

Jonathan Allan
la source
3

Perl 6 , 52 octets

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

Fonctionne pour des entrées arbitrairement élevées, avec suffisamment de mémoire (c'est-à-dire sans approximation logarithmique) .
Retourne une liste de chiffres.

Essayez-le en ligne!

Comment ça fonctionne

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

La partie "sauts d'élément" fonctionne comme ceci:

  • L'indexation d'une liste sur un index illégal renvoie un échec , qui compte comme une valeur "non définie".
  • // est l'opérateur "défini ou".
  • |()renvoie un bordereau vide , qui se dissout dans la liste externe en tant qu'éléments 0, essentiellement en s'assurant que l'élément actuel est ignoré.

Le cas d'extrémité n=1fonctionne très bien, car 2**n/4devient 0.5et ^(0.5)signifie 0 ..^ 0.5aussi "entiers compris entre 0 (inclus) et 0.5 (non inclus)", c'est-à-dire une liste avec l'élément unique 0.

smls
la source
2

J, 50 octets

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

Remarque: doit passer en numéro étendu

Usage:

   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580
ljeabmreosn
la source
2
pourquoi le vote négatif?
Ljeabmreosn
2

Haskell , 73 octets

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

Essayez-le en ligne! Utilise l'indexation 0.

Explication:

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
la source
1

Lot, 294 octets

@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

Affiche chaque chiffre sur sa propre ligne. Fonctionne en calculant les puissances de 5 longueurs, mais ne fonctionne que jusqu’à N=33cause de l’utilisation d’entiers 32 bits pour conserver le nombre de chiffres à imprimer. scontient les derniers Nchiffres (inversés) de la puissance actuelle de 5, alors que s tcontient des caractères xde remplissage, bien x=0qu'ils soient évalués à zéro lors du calcul de la puissance suivante. Exemple pour 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
la source
1

JavaScript (ES6), 73 octets

1 indexé. Légèrement plus court que la réponse ES7 , mais échoue 3 étapes plus tôt (à 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)

Démo

Arnauld
la source
0

PHP> = 7.1, 104 octets

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 en ligne

Jörg Hülsermann
la source