Todos estamos familiarizados con la secuencia de Fibonacci :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
Sin embargo, en lugar de, f(n) = f(n-1) + f(n-2)
tomaremos la suma digital de las 2 entradas anteriores.
La secuencia aún debe comenzar 0, 1
, después de eso, las diferencias son rápidamente aparentes. Esta lista está indexada a 0, puede usar también indexada a 1, estado que utilizó.
f(0) = 0
f(1) = 1
f(2) = 1 # 0 + 1
f(3) = 2 # 1 + 1
f(4) = 3 # 1 + 2
f(5) = 5 # 2 + 3
f(6) = 8 # 3 + 5
f(7) = 13 # 8 + 5
f(8) = 12 # 8 + 1 + 3
f(9) = 7 # 1 + 3 + 1 + 2
f(10) = 10 # 1 + 2 + 7
f(11) = 8 # 7 + 1 + 0
f(12) = 9 # 1 + 0 + 8
f(13) = 17 # 8 + 9
f(14) = 17 # 9 + 1 + 7
f(15) = 16 # 1 + 7 + 1 + 7
f(16) = 15 # 1 + 7 + 1 + 6
f(17) = 13 # 1 + 6 + 1 + 5
f(18) = 10 # 1 + 5 + 1 + 3
f(19) = 5 # 1 + 3 + 1 + 0
f(20) = 6 # 1 + 0 + 5
f(21) = 11 # 5 + 6
f(22) = 8 # 6 + 1 + 1
f(23) = 10 # 1 + 1 + 8
f(24) = 9 # 8 + 1 + 0
f(25) = 10 # 1 + 0 + 9
f(26) = 10 # 9 + 1 + 0
f(27) = 2 # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)
Nota: No noté la repetición hasta que publiqué el desafío en sí, y aquí estaba pensando que sería imposible escribir otro nuevo desafío de Fibonacci.
Su tarea es, dado un número n
, generar el enésimo dígito de esta secuencia.
3 primeros dígitos: [0,1,1]
,
Patrón repetido de 24 dígitos: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]
Sugerencia: puede aprovechar esta repetición para su ventaja.
Este es el código de golf , el conteo de bytes más bajo es el ganador.
BONIFICACIÓN: Si utiliza la repetición en su respuesta, otorgaré la respuesta de conteo de bytes más baja que aproveche la repetición en la secuencia de una recompensa de 100 puntos. Esto debe enviarse como parte de su respuesta original, después de su respuesta original. Vea esta publicación como un ejemplo de lo que estoy hablando: https://codegolf.stackexchange.com/a/108972/59376
Para calificar para este bono su código debe ejecutarse en tiempo constante ( O(1)
) con una explicación.
Ganador de bonificación: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis ganó.
Implementación más exclusiva: https://codegolf.stackexchange.com/a/108970/59376
(También recibirá 100 puntos, finalizados después de elegir la respuesta correcta)
fuente
%24
a una solución "normal"?O(1)
. Su código debe ejecutarse en tiempo constante, si realmente está explotando la repetición.Respuestas:
Oasis , 5 bytes
Código:
Pruébalo en línea!
Versión ampliada:
Explicación:
fuente
JavaScript (ES6), 45 bytes
x
yy
no pueden ser ambos9
, ya que eso requeriría que fuera el número anterior0
, por lo que su suma digital no puede exceder17
. Esto significa que la raíz digital para números mayores que9
es la misma que el módulo restante9
.fuente
Python 2, 53 bytes
Función recursiva. Los casos base
n=0
y eln=1
rendimienton
, los números más grandes calculan el valor llamandof(n-1)
yf(n-2)
convirtiendo cada uno en una cadena, concatenando las dos cadenas, convirtiendo cada carácter en un entero usando amap
con laint
función, y luego suma la lista resultante.Usando la información del módulo 24, actualmente puedo obtener una función sin nombre no recursiva de 56 bytes:
fuente
JavaScript (ES6), 34 bytes
Puede congelar su navegador para entradas superiores a 27, pero funciona para todos los valores de entrada. Esto se puede verificar con un simple caché:
Como se señaló en la brillante respuesta de Neil , la salida nunca puede exceder 17, por lo que la suma digital de cualquier salida superior a 9 es igual a
n%9
. Esto también funciona con salidas por debajo de 9; también podemos hacer que funcione para 9 restando 1~-
antes del módulo y luego volviendo a agregar 1 después.Lo mejor que puedo hacer con el hardcoding es 50 bytes:
fuente
Jalea , 8 bytes
Pruébalo en línea!
Cómo funciona
Solución alternativa, 19 bytes, tiempo constante.
Pruébalo en línea!
Cómo funciona
fuente
JavaScript (ES6),
52 4645 bytesUso
Salida
Explicación
Esta función verifica si la entrada es menor que 2, y si es así, devuelve la entrada. De lo contrario, crea una matriz de dos valores que se agregan entre sí como cadenas. Esos dos valores son el resultado de llamar a la función con
input - 1
yinput - 2
.El
...
operador divide esta cadena en una matriz de caracteres, que luego se convierte de nuevo en una cadena, pero ahora con+
es entre valores. Esta cadena se interpreta como código, por lo que se calcula la suma, que luego se devuelve.Este es un algoritmo de doble recursividad, lo que lo hace bastante ineficiente. Necesita 2
n-2
llamadas de función para la entradan
. Como tal, aquí hay una solución más larga pero más rápida. Gracias a ETHproductions por proponerlo.fuente
[..._(--$)+[_(--$)]]
:-)05AB1E , 8 bytes
Pruébalo en línea!
Explicación
fuente
CJam,
2220 bytesGuardado 2 bytes gracias a Martin Ender
Algoritmo recursivo directo, nada lujoso. 0 indexado.
Pruébalo en línea! o prueba para 0-50 (en realidad se ejecuta bastante rápido).
Explicación
CJam, 42 bytes
Solución usando la repetición. Algoritmo similar a la solución de Jonathan Allan.
Pruébalo en línea!
fuente
Perl 6 ,
4137 bytesIntentalo
Intentalo
fuente
*.comb.sum+*.comb.sum
.MATL , 15 bytes
Pruébalo en línea!
fuente
Python 2 ,
5446 bytesMuy inspirado por la respuesta ESET de @ETHproductions .
Pruébalo en línea!
fuente
C, 96 bytes
o 61 bytes contando códigos de escape como 1 byte cada uno
0 indexado. Similar a algunas de las otras respuestas, estoy indexando una tabla de búsqueda de valores, pero la he comprimido en fragmentos de 4 bytes. No me molesté en investigar la versión mod 24 porque no pensé que fuera tan interesante ya que los otros ya lo han hecho, pero seamos sinceros, C no va a ganar de todos modos.
explicación:
Pruébalo en línea!
fuente
Japt ,
2725 bytesPruébalo en línea!
Ahorró 2 bytes gracias a ETHproductions.
fuente
´
en lugar de--
guardar dos bytes.Haskell , 54 bytes
Pruébalo en línea! Uso:
(g!!) 12
fuente
Mathematica, 49 bytes
Definición recursiva directa. Se vuelve bastante lento después de un tiempo.
Mathematica,
7971 bytesCodificar el patrón periódico. Relámpago rápido y satisfactoriamente abusivo de Mathematica :) ¡ Gracias a JungHwan Min por guardar 8 bytes!
fuente
LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"
es 8 bytes más corto que43626804920391712116157158790~IntegerDigits~18
.LetterNumber
...Python 2 , 56 bytes
Solución iterativa simple.
Pruébalo en línea!
El uso en
(a%9or a)+(b%9or b)
realidad resultó ser más corto quesum(map(int(`a`+`b`)))
!fuente
sum(map(int,a+b))
(no puedo entender cómo usar `en los comentarios)PowerShell , 79 bytes
Pruébalo en línea!
Solución iterativa larga y aburrida que realiza cálculos directos de suma de dígitos en cada
for
ciclo. Al final del ciclo, el número que queremos está dentro$b
, por lo que queda en la tubería y la salida está implícita. Tenga en cuenta que si la entrada es0
, entonces el bucle no entrará ya que el condicional es falso, por lo que$b
permanece0
.fuente
Lote, 85 bytes.
Me preguntaba cómo iba a transferir mi respuesta de JavaScript al lote, pero la pista estaba en la solución Python de @ Dennis.
fuente
Pyth, 20 bytes
Un programa que toma la entrada de un entero indexado a cero e imprime el resultado.
Banco de pruebas (primera parte para formatear)
Cómo funciona
[Explicación más tarde]
fuente
Ruby, 58 bytes
La solución simple codificada.
fuente
apilado , 40 bytes
Esta lambda es equivalente a la siguiente lambda:
Pruébalo en línea!
fuente
Octava, 148 bytes
fuente
Haskell, 151 bytes
Invoque la función con
f 123456789012345678901234567890123456789012345678
, por ejemplo.El código también funciona con índices muy grandes. Debido a la funcionalidad del módulo 24 implementado, es muy rápido.
El código descomprimido:
fuente
R, 90 bytes
Una solución horriblemente larga, pero es mejor que la 108 que tenía originalmente. Sospecho que hay una manera mucho mejor de hacer esto, pero no puedo verlo en este momento.
Esta es una función sin nombre que usa
gsub
yscan(t=
divide los números del vector en dígitos. La suma de estos se agrega al vector mientras se suelta el primer elemento.repeat
se utiliza para recorrer losn
tiempos de secuencia y el resultado es el primer elemento del vector.fuente
PHP, 80 bytes
Versión en línea
fuente
Mathematica, 67 bytes
fuente