5, 2, 16, 3580, ¿Qué viene después?

51

Considere las potencias enteras positivas de cinco en decimal. Aquí están los primeros 25, alineados a la derecha:

 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

Observe que la columna más a la derecha de los poderes es todo 5. La segunda columna de la derecha es todo 2. La tercera columna desde la derecha, lee de arriba a abajo, los suplentes 1, 6, 1, 6, etc. Los inicia la próxima columna 3, 5, 8, 0y luego ciclos.

De hecho, cada columna (si vamos hacia abajo lo suficiente) tiene una secuencia de ciclo de dígitos cuya longitud es el doble que el del ciclo anterior, a excepción de la inicial 5's y 2' ciclos s.

Llamando a N el número de columna, comenzando con N = 1 a la derecha, los primeros ciclos son:

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

Desafío

Dado un entero positivo N, genera los dígitos decimales del ciclo en la columna N, como se describió anteriormente. Por ejemplo, la salida para N = 4 sería 3580.

Los dígitos pueden aparecer como una lista como [3, 5, 8, 0]o en otro formato razonable siempre que:

  • Los dígitos están ordenados de arriba a abajo en las columnas de potencia. Por ejemplo, 0853no es válido.
  • El ciclo comienza con el número superior en su columna de potencia. por ejemplo, 5803no es válido ya que la cuarta columna comienza con 3not 5.
  • Se emite exactamente un ciclo. por ejemplo, 358o de 35803o 35803580todos serían válidos.

Su código debe funcionar durante al menos N = 1 a 30.

Si lo desea, puede suponer que las columnas están indexadas en 0 en lugar de indexadas en 1. Entonces N = 0 da 5, N = 1 da 2, N = 2 da 16, N = 3 da 3580, etc.

El código más corto en bytes gana .

Gracias a Downgoat y DJ por su apoyo al desafío.

Pasatiempos de Calvin
fuente
El orden hace que esto sea bastante complicado.
Dennis
99
La duración del ciclo es siempre 2^(N-2)exceptoN = 1
JungHwan Min
1
¿Se pueden usar aproximaciones? La salida es válida hasta N = 72 , que teóricamente imprimiría 2.36E + 21 dígitos.
JungHwan Min
¿Está esta secuencia en el OEIS?
StarWeaver
@StarWeaver Nope.
Mego

Respuestas:

26

Python 2, 62 61 58 bytes

De base cero. Supongo que los sufijos L son aceptables.

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

Salida:

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]

Solución previa:

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

Explicación:

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

El range(2**n/2)utiliza la observación de que cada ciclo tiene una longitud r = 2 n-1 excepto cuando n = 0, por lo que sólo calcular la enésima dígitos para 5 m a 5 m + r - 1 .

El inicio del ciclo 5 m es el primer número mayor que 10 n . Resolver 5 m ≥ 10 n da m ≥ n / log 10 5. Aquí aproximamos log 10 5 ≈ 0.7 que se desglosará cuando n = 72. Podríamos agregar más dígitos para aumentar la precisión:

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

El / 10**n % 10en el bucle simplemente extrae el dígito deseado. Otra solución alternativa utiliza la manipulación de cadenas. Usé el truco~n == -n-1 aquí para eliminar 1 byte.

Como se menciona en el comentario, la expresión 5**(m+i) / 10**nse puede simplificar aún más de esta manera, lo que da la respuesta actual de 58 bytes.

ingrese la descripción de la imagen aquí

(La división x/2**nse puede hacer usando el desplazamiento a la derecha a nivel de bit x>>n. Desafortunadamente, debido a la precedencia del operador de Python, esto no ahorra bytes). La fracción 3/7 también se puede mejorar en un mannar similar:

| 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
fuente
1
(5**(n*3/7-~i)>>n)%10. Debido a que está tomando una potencia de 5 dividida por una potencia (más pequeña) de 10, puede reducir la potencia de 5 y cambiar a la derecha en su lugar. n/.7 - nn*10/7 - nn*3/7. En principio, está extrayendo los dígitos de la potencia más pequeña de 5 mayor que 2ⁿ (con 3/7 una aproximación para 1 / log₂ (5) ). Además, usar en su range(2**n/2or 1)lugar le dará una salida consistente.
primo
1
@primo Gracias, actualizado. (x>>n)%10no mejora, x/2**n%10así que no uso bit shift por ahora, ya que tal vez haya una forma de factorizar lo común 2**n.
kennytm
Sin 2**nembargo, la idea interesante de factorizar parece un poco más larga: int(5**(-~i-n*log(2,5)%1))%10(he simplificado int(n*log(2,5))-n*log(2,5)como -(n*log(2,5)%1)).
primo
@primo Interesante, pero lo que quiero decir es el 2**nargumento aquí y el rango.
kennytm
10

cc , 72 bytes

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

Indexación basada en 0.

Utiliza aritmética de enteros exactos, sin aproximaciones de logaritmo. Funcionará hasta la capacidad de memoria de la computadora.

¡Prueba el programa de cc en línea!


El código de CC se puede convertir en una solución Bash:

Bash + utilidades GNU, 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

¡Prueba la versión Bash en línea!

Mitchell Spector
fuente
9

Mathematica, 66 60 52 bytes

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

Función anónima, 0 indexada. Utiliza aproximación de log5 (10) (≈ 0.7)

¿Cómo funciona?

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

Tome más grande de 2 ^ (entrada) / 2 y 1. Genere {1 ... ese número}

...+#/.7

Añadir entrada / .7

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

Eleve 5 a la potencia del resultado (generando potencias de 5), divida por 10 ^ entrada (eliminando dígitos a la derecha de la columna deseada)

Mod[ ...,10]

Aplicar el módulo 10, tomando el dígito de uno (la columna deseada).

Versión exacta, 58 bytes.

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/5~Log~10]/10^#,10]&
JungHwan Min
fuente
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 indexado, es decir, f(0)da 2.

Fragmento de prueba

El fragmento se utiliza en Math.powlugar de **para la compatibilidad entre navegadores.

ETHproducciones
fuente
4

CJam, 35

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

Pruébalo en línea

Es eficiente en espacio y no es extremadamente lento, tomó varios minutos para la entrada 30 en mi computadora (usando el intérprete de Java).

aditsu
fuente
3

Jalea , 26 21 bytes

-2 bytes usando la idea de aproximación 0.7 de kennytm

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

Pruébalo en línea! (tiempos de espera para n> 15 )

Devuelve una lista de enteros, los dígitos.
Basado en cero. Teóricamente funciona para n <= 72 (reemplazar .7con 5l⁵¤, para obtener precisión de coma flotante).

¿Cómo?

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

A nivel local: la memoria del conjunto de trabajo para n = 17 aumentó a alrededor de 750 MB y luego aumentó a alrededor de 1 GB ; para n = 18 lentamente alcanzó 2.5GB y luego se disparó a alrededor de 5GB .

Jonathan Allan
fuente
3

Perl 6 , 52 bytes

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

Funciona para entradas arbitrariamente altas, con suficiente memoria (es decir, sin aproximación de logaritmo) .
Devuelve una lista de dígitos.

Pruébalo en línea!

Cómo funciona

->\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 parte de "omisión de elementos" funciona así:

  • La indexación de una lista en un índice ilegal devuelve una falla , que cuenta como un valor "indefinido".
  • // es el operador "definido o".
  • |()devuelve un Slip vacío , que se disuelve en la lista externa como 0 elementos, esencialmente asegurándose de que se omita el elemento actual.

El caso de borde n=1funciona bien, porque se 2**n/4convierte en 0.5, y ^(0.5)significa 0 ..^ 0.5aka "enteros entre 0 (inclusive) y 0.5 (no incluido)", es decir, una lista con el elemento único 0.

smls
fuente
2

J, 50 bytes

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

Nota: debe pasar en número extendido

Uso:

   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580
ljeabmreosn
fuente
2
¿Por qué el voto negativo?
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]

Pruébalo en línea! Utiliza indexación 0.

Explicación:

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

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

Emite cada dígito en su propia línea. Funciona calculando las potencias de 5 longhand, pero solo funciona N=33debido al uso de enteros de 32 bits para llevar la cuenta de cuántos dígitos imprimir. scontiene los últimos Ndígitos (invertidos) de la potencia actual de 5, mientras que tcontiene xs utilizados como relleno, aunque los x=0hace evaluar como cero cuando se calcula la siguiente potencia. Ejemplo para 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
fuente
1

JavaScript (ES6), 73 bytes

1 indexado. Un poco más corto que la respuesta ES7 , pero falla 3 pasos antes (en 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)

Manifestación

Arnauld
fuente
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 en línea

Jörg Hülsermann
fuente