La famosa secuencia de Fibonacci es F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1)
(para este desafío comenzamos con 0).
Su reto: Dada n , salida de la suma de todos los d º números de Fibonacci para todos los divisores d del n ésimo número de Fibonacci. Si prefieres una notación más formal,
Entrada : un entero positivo n
Salida : la suma
Por ejemplo, considere n=4
. F(4) = 3
Los divisores de 3 son 1 y 3, por lo que la salida debería ser F(1) + F(3) = 1 + 2 = 3
.
Para n=6
, F(6) = 8
y los divisores de 8 son 1, 2, 4, 8, entonces la salida es F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26
.
Casos de prueba:
1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26
Este es el código de golf , la respuesta más corta en bytes gana. Se aplican lagunas estándar .
code-golf
number-theory
fibonacci
division
Neil A.
fuente
fuente
Jalea , 7 bytes
Pruébalo en línea!
Explicación:
fuente
Mathematica, 29 bytes
fuente
Mathematica simplificado , 14 bytes
Oh, bueno, esto terminó siendo idéntico a la solución de @ MartinEnder ...
fuente
N
)Japt , 11 bytes
Pruébalo en línea!
fuente
05AB1E , 11 bytes
Pruébalo en línea!
Explicación
fuente
Haskell, 54 bytes
Ejemplo de uso:
g 6
->26
. Pruébalo en línea!fuente
Alice ,
3836 bytesGracias a Leo por guardar 2 bytes.
Pruébalo en línea!
Casi seguro que no es óptimo. El flujo de control es bastante elaborado y, si bien estoy bastante contento con la cantidad de bytes que se guardaron en las versiones anteriores, tengo la sensación de que estoy complicando demasiado las cosas de que podría haber una solución más simple y más corta.
Explicación
Primero, necesito elaborar un poco sobre la pila de direcciones de retorno de Alice (RAS). Al igual que muchos otros fungeoides, Alice tiene un comando para saltar en el código. Sin embargo, también tiene comandos para regresar al lugar de donde vino, lo que le permite implementar subrutinas de manera bastante conveniente. Por supuesto, al tratarse de un lenguaje 2D, las subrutinas solo existen por convención. No hay nada que le impida ingresar o salir de una subrutina a través de otros medios que no sean un comando de retorno (o en cualquier punto de la subrutina), y dependiendo de cómo use el RAS, puede que no haya una jerarquía de salto / retorno limpia de todos modos.
En general, esto se implementa haciendo que el comando de salto
j
empuje la dirección IP actual al RAS antes de saltar. El comando de retornok
luego muestra una dirección del RAS y salta allí. Si el RAS está vacío,k
no hace nada en absoluto.También hay otras formas de manipular el RAS. Dos de estos son relevantes para este programa:
w
empuja la dirección IP actual al RAS sin saltar a ningún lado. Si repite este comando, puede escribir bucles simples de manera bastante conveniente&w...k
, como ya lo hice en respuestas anteriores.J
es comoj
pero no recuerda la dirección IP actual en el RAS.También es importante tener en cuenta que el RAS no almacena información sobre la dirección de la IP. Por lo tanto, volver a una dirección con
k
siempre conservará la dirección IP actual (y, por lo tanto, también si estamos en modo Cardinal u Ordinal) independientemente de cómo pasamos por elj
ow
de que empujó la dirección IP en el primer lugar.Una vez dicho esto, comencemos analizando la subrutina en el programa anterior:
Esta subrutina tira del elemento inferior de la pila, n , hacia la parte superior y luego calcula los números de Fibonacci F (n) y F (n + 1) (dejándolos en la parte superior de la pila). Nunca necesitamos F (n + 1) , pero se descartará fuera de la subrutina, debido a cómo los
&w...k
bucles interactúan con el RAS (que requiere que estos bucles estén al final de una subrutina). La razón por la que estamos tomando elementos de la parte inferior en lugar de la parte superior es que esto nos permite tratar la pila más como una cola, lo que significa que podemos calcular todos los números de Fibonacci de una sola vez sin tener que almacenarlos en otro lugar.Así es como funciona esta subrutina:
El final del ciclo es un poco complicado. Mientras haya una copia de la dirección 'w' en la pila, esto iniciará la próxima iteración. Una vez que se agotan, el resultado depende de cómo se invocó la subrutina. Si se llamó a la subrutina con 'j', la última 'k' regresa allí, por lo que el final del ciclo se duplica como el retorno de la subrutina. Si se llamó a la subrutina con 'J', y todavía hay una dirección anterior en la pila, saltamos allí. Esto significa que si la subrutina se llamó en un bucle externo en sí, esta 'k' regresa al comienzo de ese bucle externo . Si se llamó a la subrutina con 'J' pero el RAS está vacío ahora, entonces esta 'k' no hace nada y la IP simplemente sigue moviéndose después del ciclo. Usaremos los tres casos en el programa.
Finalmente, al programa en sí.
Estas son solo dos excursiones rápidas al modo Ordinal para leer e imprimir enteros decimales.
Después de la
i
, hay unaw
que recuerda la posición actual antes de pasar a la subrutina, debido a la segunda/
. Esta primera invocación de la subrutina se calculaF(n)
yF(n+1)
en la entradan
. Luego saltamos de regreso aquí, pero ahora nos estamos moviendo hacia el este, por lo que el resto de los operadores del programa están en modo Cardinal. El programa principal se ve así:Aquí,
31J
hay otra llamada a la subrutina y, por lo tanto, calcula un número de Fibonacci.fuente
Axioma, 68 bytes
alguna prueba
fuente
Pari / GP , 34 bytes
Pruébalo en línea!
fuente
Python 2 ,
8984 bytes-5 bytes gracias a los ovs
Pruébalo en línea!
fuente
R, 77 bytes
Hace uso de la biblioteca 'gmp'. Esto tiene una función incorporada de Fibonacci y proporciona la capacidad de hacer grandes cantidades. Causó algunos problemas con las seqs y aplica, aunque todavía es más pequeño que crear mi propia función Fibonacci.
Explicación
Prueba
Sin usar gmp
81 bytes , función recursiva que es irremediablemente lenta cuando se seleccionan números grandes (9+)
88 bytes , la fórmula de Binet que funcionará razonablemente bien con números más grandes, pero aún así alcanza el límite entero con bastante rapidez
fuente
Perl 6 , 49 bytes
fuente
CJam , 26 bytes
Pruébalo en línea!
Estoy seguro de que se puede hacer mejor. Explicación:
La idea es tener una matriz de números de Fibonacci y un producto de puntos con una matriz con 1s y 0s si ese número es o no un divisor de la entrada.
fuente
JavaScript (ES6),
7665 bytesCasos de prueba
Mostrar fragmento de código
fuente
JavaScript (ES6),
10510410310197 bytesIntentalo
fuente
(z=g(i)/y)>~~z
a(z=g(i)/y)%1
, si usted está mirando quez
es un entero.g(z)
a,g(z|0)
pero nos devuelve al mismo número de bytes.Q, 75 bytes
fuente
C (gcc) ,
939080 bytesPruébalo en línea!
fuente
Agregar ++ , 89 bytes
Pruébalo en línea!
fuente