¡Suma mis divisores fibonaccificados!

14

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,

La suma

Entrada : un entero positivo n

Salida : la suma

Por ejemplo, considere n=4. F(4) = 3Los 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) = 8y 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 , la respuesta más corta en bytes gana. Se aplican lagunas estándar .

Neil A.
fuente

Respuestas:

2

Realmente , 5 bytes

F÷♂FΣ

Pruébalo en línea!

Cómo funciona

       (implicit) Read n from STDIN.
F      Compute F(n).
 ÷     Get F(n)'s divisors.
  ♂F   Map F over the divisors.
    Σ  Take the sum.
Dennis
fuente
El nombre del lenguaje hace que parezca pasivo agresivo, ¿es eso lo que se pretende?
Rohan Jhunjhunwala
1
Lo dudo. La primera versión del idioma se llamó en serio debido a este comentario . Para la segunda versión, el autor eligió seguir usando adjetivos.
Dennis
6

Jalea , 7 bytes

ÆḞÆDÆḞS

Pruébalo en línea!

Explicación:

ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum
Erik el Outgolfer
fuente
¡Absolutamente escandaloso! No conozco ninguno de estos lenguajes exóticos, pero me parece sobrenatural cómo puedes escribir un algoritmo completo con unos pocos caracteres.
Bogdan Alexandru
@BogdanAlexandru Puede ver que la mayoría de los componentes internos utilizados aquí consumen 2 bytes, ya que no caben en 1 byte. Vea la respuesta de Dennis en realidad para incluso menos caracteres. Además, Jelly es un "lenguaje de golf", un lenguaje hecho específicamente para el golf de código , y es uno de los más eficientes aquí (aunque no hay un lenguaje "más eficiente").
Erik the Outgolfer
¿Estás diciendo que estos idiomas no se usan en la práctica y solo están destinados a desafíos?
Bogdan Alexandru
4

Mathematica, 29 bytes

f=Fibonacci;f@#~DivisorSum~f&
Martin Ender
fuente
4

Mathematica simplificado , 14 bytes

Fi@#~Div9`~Fi&

Oh, bueno, esto terminó siendo idéntico a la solución de @ MartinEnder ...

JungHwan Min
fuente
Bueno ... Usando una versión más corta del mismo idioma ... Supongo que funciona.
Neil A.
No hay nombres de funciones de letra única en Mathematica, ¿verdad? ¿No podría unir las dos cadenas de caracteres formadas por una letra mayúscula inicial más un solo byte? Si es así, tendría 26 * 256 = 6656 nombres de función simplificados de 2 bytes, suficiente para los nombres 6356 11.1.1 con 300 de sobra.
Jonathan Allan
@ JonathanAllan Buena idea. (pero hay funciones de nombre único, como N)
JungHwan Min
2

05AB1E , 11 bytes

!ÅFDI<èÑ<èO

Pruébalo en línea!

Explicación

!            # factorial of input
 ÅF          # get the list of fibonacci numbers (starting at 1)
             # smaller than or equal to this
   D         # duplicate list of fibonacci number
    I<è      # get the element at index (input-1)
       Ñ     # get the list of its divisors
        <    # decrement each
         è   # get the fibonacci numbers at those indices
          O  # sum
Emigna
fuente
2

Haskell, 54 bytes

f=0:scanl(+)1f
g x=sum[f!!d|d<-[1..f!!x],mod(f!!x)d<1]

Ejemplo de uso: g 6-> 26. Pruébalo en línea!

nimi
fuente
2

Alice , 38 36 bytes

Gracias a Leo por guardar 2 bytes.

/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+

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 jempuje la dirección IP actual al RAS antes de saltar. El comando de retorno kluego 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:

  • wempuja 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.
  • Jes como jpero 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 ksiempre 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 el jow de que empujó la dirección IP en el primer lugar.

Una vez dicho esto, comencemos analizando la subrutina en el programa anterior:

01dt,t&w.2,+k

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...kbucles 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:

                                                          Stack
01    Push 0 and 1, to initialise Fibonacci sequence.     [n ... 0 1]
dt,   Pull bottom element n to top.                       [... 0 1 n]
t&w   Run this loop n times...                            [... F(i-2) F(i-1)]

  .     Duplicate F(i-1).                                 [... F(i-2) F(i-1) F(i-1)]
  2,    Pull up F(i-2).                                   [... F(i-1) F(i-1) F(i-2)]
  +     Add them together to get F(i).                    [... F(i-1) F(i)]

k     End of loop.

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

/o....
\i@...

Estas son solo dos excursiones rápidas al modo Ordinal para leer e imprimir enteros decimales.

Después de la i, hay una wque recuerda la posición actual antes de pasar a la subrutina, debido a la segunda /. Esta primera invocación de la subrutina se calcula F(n)y F(n+1)en la entrada n. 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í:

;B1dt&w;31J;d&+
        ^^^

Aquí, 31Jhay otra llamada a la subrutina y, por lo tanto, calcula un número de Fibonacci.

                                              Stack
                                              [F(n) F(n+1)]
;     Discard F(n+1).                         [F(n)]
B     Push all divisors of F(n).              [d_1 d_2 ... d_p]
1     Push 1. This value is arbitrary.        [d_1 d_2 ... d_p 1]
      The reason we need it is due to
      the fact that we don't want to run
      any code after our nested loops, so
      the upcoming outer loop over all
      divisors will *start* with ';' to
      discard F(d+1). But on the first
      iteration we haven't called the
      subroutine yet, so we need some 
      dummy value we can discard.
dt&w  Run this loop once for each element     [d_1 d_2 ... d_p 1]
      in the stack. Note that this is once    OR
      more than we have divisors. But since   [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)] 
      we're treating the stack as a queue,
      the last iteration will process the 
      first divisor for a second time. 
      Luckily, the first divisor is always 
      1 and F(1) = 1, so it doesn't matter 
      how often we process this one.

  ;     Discard the dummy value on the        [d_1 d_2 ... d_p]
        first iteration and F(d+1) of         OR
        the previous divisor on subsequent    [d_i d_(i+1) ... F(d_(i-1))]
        iterations.
  31J   Call the subroutine without pushing   [d_(i+1) ... F(d_i) F(d_i+1)]
        the current address on the RAS.
        Thereby, this doubles as our outer
        loop end. As long as there's an
        address left from the 'w', the end
        of the subroutine will jump there
        and start another iteration for the
        next divisor. Once that's done, the
        'k' at the end of the subroutine will
        simply do nothing and we'll continue
        after it.

;     Discard the final F(d_i+1).
d&+   Get the stack depth D and add the top   [final result]
      D+2 values. Of course that's two more
      than we have divisors, but the stack is
      implicitly padded with zeros, so that
      doesn't matter.
Martin Ender
fuente
1

Axioma, 68 bytes

g==>fibonacci;f(x:NNI):NNI==(x<3=>1;reduce(+,map(g,divisors(g(x)))))

alguna prueba

(46) -> [[i,f(i)] for i in [0,1,2,3,4,5,6,10,15] ]
   (46)
   [[0,1], [1,1], [2,1], [3,2], [4,3], [5,6], [6,26], [10,139583862540],
     [15,
      135823697912782666169062844948067355657769395021071830756126284114988028_
       12823029319917411196081011510136735503204397274473084444
     ]
   ]
                                       Type: List List NonNegativeInteger
RosLuP
fuente
1

Python 2 , 89 84 bytes

-5 bytes gracias a los ovs

lambda n:sum(f(i)for i in range(1,f(n)+1)if f(n)%i<1)
f=lambda x:x<3or f(x-1)+f(x-2)

Pruébalo en línea!

varilla
fuente
1

R, 77 bytes

F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)

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

F=gmp::fibnum;               # Set F as fibnum function
N=F(scan());                 # get input and set N to the fibonacci number of that index
i=n=N-N;                     # set i and n to 0 with data type bigz
while(i<N)                   # loop while i < N
   if(N%%(i=i+1)<1)          # if incremented i is divisor of N 
       n=n+F(i);             # add F(i) to rolling sum
print(n)                     # output final result

Prueba

> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 6
2: 
Read 1 item
Big Integer ('bigz') :
[1] 26
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 10
2: 
Read 1 item
Big Integer ('bigz') :
[1] 139583862540
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 15
2: 
Read 1 item
Big Integer ('bigz') :
[1] 13582369791278266616906284494806735565776939502107183075612628411498802812823029319917411196081011510136735503204397274473084444

Sin usar gmp

81 bytes , función recursiva que es irremediablemente lenta cuando se seleccionan números grandes (9+)

F=function(n)`if`(n<2,n,F(n-1)+F(n-2));sum(sapply(which((N=F(scan()))%%1:N<1),F))

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

F=function(n)round(((5+5^.5)/10)*((1+5^.5)/2)^(n-1));sum(F(which(F(N<-scan())%%1:N<1)))
MickyT
fuente
0

Perl 6 , 49 bytes

{my \f=0,1,*+*...*;sum f[grep f[$_]%%*,1..f[$_]]}
Sean
fuente
0

CJam , 26 bytes

qi_[XY@{_2$+}*]_@\f%:!.*:+

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.

qi                                 Read the input (n)
   [XY        ]                    Array starting with [1,2,...]
  _   @{_2$+}*                     Append n times the sum of the previous two
               _                   Duplicate the array
                @\f%               Modulo each item with n (0 if divisor, a number otherwise)
                    :!             Logical NOT everything (1 if divisor, 0 otherwise) 
                      .*:+         Dot product those two arrays
FrodCube
fuente
0

JavaScript (ES6), 76 65 bytes

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

Casos de prueba

Arnauld
fuente
0

JavaScript (ES6), 105 104 103 101 97 bytes

i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s

Intentalo

f=
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s
o.innerText=f(j.value=4)
oninput=_=>o.innerText=f(+j.value)
<input id=j type=number><pre id=o>

Lanudo
fuente
Yo creo que se puede cambiar (z=g(i)/y)>~~za (z=g(i)/y)%1, si usted está mirando que zes un entero.
ETHproductions
@ETHproductions, que crea un desbordamiento que puede resolverse cambiando g(z)a, g(z|0)pero nos devuelve al mismo número de bytes.
Shaggy
0

Q, 75 bytes

{f:{$[x<2;x;.z.s[x-1]+.z.s[x-2]]};sum f each m where(~)b mod m:1+til b:f x}
Daniel Plainview
fuente