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
, 0
y 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,
0853
no es válido. - El ciclo comienza con el número superior en su columna de potencia. por ejemplo,
5803
no es válido ya que la cuarta columna comienza con3
not5
. - Se emite exactamente un ciclo. por ejemplo,
358
o de35803
o35803580
todos 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 .
2^(N-2)
exceptoN = 1
Respuestas:
Python 2,
626158 bytesDe base cero. Supongo que los sufijos L son aceptables.
Salida:
Solución previa:
Explicación:
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:
El
/ 10**n % 10
en 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**n
se puede simplificar aún más de esta manera, lo que da la respuesta actual de 58 bytes.(La división
x/2**n
se puede hacer usando el desplazamiento a la derecha a nivel de bitx>>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:fuente
(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 - n
→n*10/7 - n
→n*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 surange(2**n/2or 1)
lugar le dará una salida consistente.(x>>n)%10
no mejora,x/2**n%10
así que no uso bit shift por ahora, ya que tal vez haya una forma de factorizar lo común2**n
.2**n
embargo, la idea interesante de factorizar parece un poco más larga:int(5**(-~i-n*log(2,5)%1))%10
(he simplificadoint(n*log(2,5))-n*log(2,5)
como-(n*log(2,5)%1)
).2**n
argumento aquí y el rango.cc , 72 bytes
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,
967775 bytes¡Prueba la versión Bash en línea!
fuente
Mathematica,
666052 bytesFunción anónima, 0 indexada. Utiliza aproximación de log5 (10) (≈ 0.7)
¿Cómo funciona?
Tome más grande de 2 ^ (entrada) / 2 y 1. Genere {1 ... ese número}
Añadir entrada / .7
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)
Aplicar el módulo 10, tomando el dígito de uno (la columna deseada).
Versión exacta, 58 bytes.
fuente
JavaScript (ES7),
7876 bytes0 indexado, es decir,
f(0)
da2
.Fragmento de prueba
Mostrar fragmento de código
El fragmento se utiliza en
Math.pow
lugar de**
para la compatibilidad entre navegadores.fuente
CJam, 35
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).
fuente
Jalea ,
2621 bytes-2 bytes usando la idea de aproximación 0.7 de kennytm
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
.7
con5l⁵¤
, para obtener precisión de coma flotante).¿Cómo?
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 .
fuente
Perl 6 , 52 bytes
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
La parte de "omisión de elementos" funciona así:
//
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=1
funciona bien, porque se2**n/4
convierte en0.5
, y^(0.5)
significa0 ..^ 0.5
aka "enteros entre 0 (inclusive) y 0.5 (no incluido)", es decir, una lista con el elemento único 0.fuente
J, 50 bytes
Nota: debe pasar en número extendido
Uso:
fuente
Haskell , 73 bytes
Pruébalo en línea! Utiliza indexación 0.
Explicación:
fuente
Lote, 294 bytes
Emite cada dígito en su propia línea. Funciona calculando las potencias de 5 longhand, pero solo funciona
N=33
debido al uso de enteros de 32 bits para llevar la cuenta de cuántos dígitos imprimir.s
contiene los últimosN
dígitos (invertidos) de la potencia actual de 5, mientras quet
contienex
s utilizados como relleno, aunque losx=0
hace evaluar como cero cuando se calcula la siguiente potencia. Ejemplo paraN=4
:fuente
JavaScript (ES6), 73 bytes
1 indexado. Un poco más corto que la respuesta ES7 , pero falla 3 pasos antes (en N = 13).
Manifestación
Mostrar fragmento de código
fuente
PHP> = 7.1, 104 bytes
PHP Sandbox en línea
fuente