Fondo

La mayoría de ustedes saben qué es un número de Fibonacci . Algunos de ustedes pueden saber que todos los enteros positivos se pueden representar como una suma de uno o más números distintos de Fibonacci, de acuerdo con el Teorema de Zeckendorf . Si el número de términos en la representación óptima de Zeckendorf de un número entero nes en sí mismo un número de Fibonacci, llamaremos a nFibonacci "en secreto".

Por ejemplo:

139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci

140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci

Notas

• La representación óptima de Zeckendorf se puede encontrar utilizando un algoritmo codicioso. Simplemente tome el número de Fibonacci más grande <= n y reste de n hasta llegar a 0
• Todos los números de Fibonacci se pueden representar como la suma de 1 número de Fibonacci (sí mismo). Como 1 es un número de Fibonacci, todos los números de Fibonacci también son secretamente Fibonacci.

Reto

Su desafío es escribir un programa o función que tome un entero y devuelva si ese entero es secretamente Fibonacci.

Entrada

Puede tomar información en cualquier formato razonable. Puede suponer que la entrada será un solo entero positivo.

Salida

Produzca uno de dos resultados distintos para saber si la entrada es secretamente Fibonacci. Los ejemplos incluyen True/ False, 1/ 0, etc.

Tanteo

Este es el código de golf , por lo que la respuesta más corta en bytes gana Las lagunas estándar están prohibidas.

Casos de prueba

Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

JavaScript (Node.js) , 54 bytes

x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)

Pruébalo en línea!

Python 2 , 77 bytes

def f(n):z=[bin(x).count('1')for x in range(n*n+1)if x&2*x<1];print z[z[n]]<2

Pruébalo en línea!

Esto utiliza el teorema de que las dos descripciones de OEIS A003714 son equivalentes:

$n = F(i_1) + F(i_2) + \dots + F(i_k)$$n$$n$$a(n) = 2^{i_1} + 2^{i_2} + \dots + 2^{i_k}$$1$'s.

z$n$

Luego queda comprobar si z[n]es un número de Fibonacci, es decir z[z[n]] == 1.

^{$n^2+1$}

Gelatina , 15 bytes

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị

Un enlace monádico que acepta un número entero no negativo que produce 1 "Secret Fibonacci" y lo 0contrario.

Pruébalo en línea! (demasiado ineficiente para los casos de prueba más grandes)

¿Cómo?

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị - Link: integer, I
        µƬ      - perform the monadic link to the left as a function of the current I,
                - collecting up all the inputs until the results are no longer unique:
‘               -   increment I -> I+1
 ÆḞ€            -   nth Fibonacci number for €ach n in [1,I+1]
     R          -   range from 1 to I
    f           -   filter discard (discard Fibonacci numbers not in the range, i.e. > I)
      Ṫ         -   tail (get the largest)
       ạ        -   absolute difference with I
                - This gives us a list from I decreasing by Fibonacci numbers to 0
                - e.g. for 88 we get [88,33,12,4,1,0]
                -      because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88 
          L     - length (the number of Fibonacci numbers required plus one)
           ’    - decrement (the number of Fibonacci numbers required)
            Ɗ   - treat the last three links (which is everything to the left) as a monad:
             ⁺  - ...and repeat it
                - i.e. get the number of Fibonacci numbers required for the number of
                -      Fibonacci numbers required to represent I.
                -      This is 1 if I is Secretly Fibonacci, and greater if not)
              Ị - insignificant? (is the absolute value of that <= 1?)

R , 83 bytes

function(n){T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n){n=n-T[T<=n][1]
F=F+1}
F%in%T}

Pruébalo en línea!

C # (.NET Core) , 124 115 98 bytes

a=>{int n=0,b,c;for(;a>0;a-=b,n++)for(b=c=1;c<=a;b=c-b)c+=b;for(b=c=1;c<n;c+=b)b=c-b;return c==n;}

Pruébalo en línea!

-3 bytes: cambiado mientras bucle a for (gracias a Olivier Grégoire )
-6 bytes: retornos cambiados para usar variables, inicializadas byc fuera de los bucles (gracias a Kevin Cruijssen )
-17 bytes: condición cambiada en el segundo bucle para mover si fuera de bucle y combinar con retorno, reutilizado byc variables en el último bucle (gracias a raznagul )

Sin golf:

a => {
    int n = 0, b, c;                        // initialize variables

    for(; a > 0; a -= b, n++)               // increase n until a is 0
        for(b = c = 1; c <= a; b = c - b)   // set b and c to 1 for each a; set second largest Fibonacci number until largest Fibonacci number reaches a
            c += b;                         // set largest Fibonacci number of current sequence

    for(b = c = 1; c < n; c += b)           // while e is less than or equal to n, continue incrementing largest (e) Fibonacci number in the sequence
        b = c - b;                          // increment second-largest (d) Fibonacci number

    return c == n;                          // if c equals n, a is a secret Fibonacci number
}

Perl 6 , 58 bytes

{(1,&[+]...*>$_)∋($_,{$^n-(1,&[+]...^*>$n).tail}...0)-1}

Pruébalo en línea!

1, &[+] ... * > $_ es solo la secuencia de Fibonacci, detenida en un lugar conveniente no infinito (el número de entrada).

$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0es una secuencia de números, comenzando con el número de entrada, y cada elemento sucesivo se obtiene restando el número de Fibonacci más grande menor o igual que el elemento anterior del elemento anterior. La secuencia termina cuando 0se alcanza. Por ejemplo, si $_es 140, entonces esta secuencia es140, 51, 17, 4, 1, 0 .

Restar uno de esta secuencia lo trata como un número, su longitud y la diferencia es el número de números de Fibonacci que, sumados, dan el número de entrada. Luego, se verifica la membresía de este número en la primera secuencia de Fibonacci.

Perl 6 , 48 bytes

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}

Pruébalo en línea!

Transforma la entrada en una lista de Representación de Zeckendorf repetidamente hasta que alcanza un solo número y luego verifica si la longitud de la secuencia fue menor a 4.

La función Zenckendorf en el medio proviene principalmente de la respuesta de Sean con un par de mejoras.

Explicación:

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}
{                                              } # Anonymous code block
                                          ...     # Define a sequence:
    $_  # That starts at the input
      ,{                                 }  # Each element is defined by:
                                   ... # Another sequence that:
        $_,   # Starts at the previous element
            $_-   # The previous element minus
                1,&[+]...*     # The Fibonacci sequence
                          >$_  # Ending when it is larger than the previous element
               (             )[*-2]  # The second from last element
          {                        }...^0  # Run until 0, discarding the last element
         # This returns the length of the Zeckendorf Representation
                                         ...1  # Run this until it is length 1
 4>(                                         )  # Return true if the length of the sequence is smaller than 4

Por ejemplo, la secuencia para 2es 2 1ya 2que ya es un número de Fibonacci. La secuencia para 140es 140 5 1, y dado que 5 es un número de Fibonacci, esto devuelve verdadero. La secuencia para 33es33 4 2 1 , y dado 4que no es un número de Fibonacci, la secuencia es de longitud 4.

05AB1E , 14 bytes

ΔDÅFθ-¼}¾ÅF¾<å

Pruébalo en línea . No hay un conjunto de pruebas para todos los casos de prueba, porque counter_variableno se puede restablecer a 0 .. Sin embargo, verifiqué todo a mano y son correctos.

Explicación:

Δ      }          # Loop until the top of the stack no longer changes
 D                #  Duplicate the top of the stack
                  #  (implicitly the input in the first iteration)
  ÅF              #  Get a list of all Fibonacci numbers lower than this number
    θ             #  Get the last item (largest one)
     -            #  Subtract it from the number
      ¼           #  Increase the counter_variable by 1 every iteration
        ¾         # After the loop, push the counter_variable
         ÅF       # Get all Fibonacci numbers below this counter_variable
           ¾<     # Push the counter_variable again, and subtract 1
             å    # Check if this value is in the list of Fibonacci numbers
                  # (and output implicitly)

NOTA: El counter_variablesería 5para entrada 139y 6para entrada140 , porque para que el Δbucle compruebe que la pila permaneció igual, por supuesto, hace una iteración adicional.

Haskell , 64 bytes

s=(<2).r.r
f=1:scanl(+)1f
r 0=0
r z=1+r(z-last(takeWhile(<=z)f))

Pruébalo en línea!

Retina 0.8.2 , 61 bytes

.+
$*
M`((?>\2?)(\1|\G.))*..|.
.+
$*
^(((?>\3?)(\2|^.))*.)?.$

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

.+
$*

Convierte a unario.

M`((?>\2?)(\1|\G.))*..|.

Cuente el número de números de Fibonacci necesarios.

La primera alternancia trata con números de Fibonacci que son al menos 2. En el primer pase, \2todavía no existe, pero afortunadamente es opcional, por lo que no tenemos que igualarlo. \1tampoco existe, pero afortunadamente tenemos la alternativa de \G.que coincida con un solo personaje al comienzo de la partida. Ambos\2 y, \1por lo tanto, toman el valor 1.

En pases posteriores, \2existe, por lo que intentamos igualarlo. Esta vez, si falla, \1también falla (ya que es más grande que \2), pero si tiene éxito, (?>)evita el retroceso, por lo que si \2coincide pero \1no, no lo intentamos solo \1. ( \G1siempre falla porque hemos avanzado más allá del inicio del parche). Finalmente \2adquiere el valor anterior de\1 while\1 toma la suma de los dos valores.

Por lo tanto, combinamos tantos números de Fibonacci como podamos, sumando a medida que avanzamos. Desde las sumas parciales de la secuencia1, 2, 3, 5... son0, 1, 3, 6, 11... ejemplo, 2 menos que los números de Fibonacci, terminamos haciendo coincidir 2 al final.

Obviamente, esto no coincide con 1 en sí mismo, por lo que una alternancia maneja ese caso.

.+
$*

Convierte a unario.

^(((?>\3?)(\2|^.))*.)?.$

Prueba si este es un número de Fibonacci. Esto usa la misma idea que la primera prueba pero usa en ^lugar de\G y también tenemos que coincidir exactamente, por lo que usa una captura opcional en lugar de una alternancia, ya que es más golfista (pero aumenta los números de captura en 1).

Retina , 35 bytes

.+
*
2}C`((?>\2?)(\1|\G.))*..|.
^1$

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

.+
*

Convierte a unario.

C`((?>\2?)(\1|\G.))*..|.

Cuente el número de números de Fibonacci necesarios. (En bucle, tanto la conversión como el recuento ahorran un byte completo al obtener el recuento en unario en primer lugar).

2}

Realice los pasos anteriores dos veces en total. Esto toma el recuento de números de Fibonacci necesarios para sumar el recuento de números de Fibonacci.

^1$

Si el número era secretamente Fibonacci, entonces el resultado es 1.

Python 2 , 146 137 bytes

lambda a:len(g(len(g(a))))<2
f=lambda n:n<3or f(n-2)+f(n-1)
def g(a,n=1):j=f(n-1);return[j]if a-j<1else[j]+g(a-j)if a-f(n)<0else g(a,n+1)

Pruébalo en línea!

f () es una función recursiva que devuelve el valor del enésimo número de Fibonacci. Tomado de esta respuesta .

g () es una función recursiva que devuelve la representación de Zeckendorf del número dado como una lista de enteros.

Dado que todos los números de Fibonacci tendrán una longitud de retorno de un elemento de g (), h () verifica si la longitud de la g () de g (n) == 1.

EDITAR: guardado 9 bytes gracias a nedla2004 . Siempre olvido que las lambdas no siempre son la mejor solución ...