Contexte

La plupart d'entre vous savent ce qu'est un numéro de Fibonacci . Certains d'entre vous savent peut-être que tous les nombres entiers positifs peuvent être représentés comme la somme d'un ou plusieurs nombres de Fibonacci distincts, selon le théorème de Zeckendorf . Si le nombre de termes dans la représentation optimale de Zeckendorf d'un entier nest lui-même un nombre de Fibonacci, nous appellerons n"secrètement" Fibonacci.

Par exemple:

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

Remarques

• La représentation optimale de Zeckendorf peut être trouvée en utilisant un algorithme gourmand. Prenez simplement le plus grand nombre de Fibonacci <= n et soustrayez-le de n jusqu'à ce que vous atteigniez 0
• Tous les nombres de Fibonacci peuvent être représentés comme une somme de 1 nombre de Fibonacci (lui-même). Puisque 1 est un nombre de Fibonacci, tous les nombres de Fibonacci sont également secrètement Fibonacci.

Défi

Votre défi est d'écrire un programme ou une fonction qui prend un entier et retourne si cet entier est secrètement Fibonacci.

Contribution

Vous pouvez prendre des contributions dans n'importe quel format raisonnable. Vous pouvez supposer que l'entrée sera un seul entier positif.

Sortie

Sortie l'un des deux résultats distincts pour savoir si l'entrée est secrètement Fibonacci. Les exemples incluent True/ False, 1/ 0, etc.

Notation

C'est le golf de code , donc la réponse la plus courte en octets gagne! Les failles standard sont interdites.

Cas de test

Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

JavaScript (Node.js) , 54 octets

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

Essayez-le en ligne!

Python 2 , 77 octets

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

Essayez-le en ligne!

Cela utilise le théorème que les deux descriptions d' OEIS A003714 sont équivalentes:

Nombres fibinaires: si est la représentation de Zeckendorf de (c'est-à-dire écrire dans le système de nombres de Fibonacci) alors . Également des nombres dont la représentation binaire ne contient pas deux adjacents .$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$1$

Nous générons suffisamment * de tels nombres, puis les utilisons zcomme mappage à partir d'entiers non négatifs sur «combien de termes sont dans la représentation de Zeckendorf de ?» En comptant 1s en binaire.$n$

Il reste alors à vérifier s'il z[n]s'agit d'un nombre de Fibonacci, c'est-à-dire z[z[n]] == 1.

^{* Au moins, semble suffisant, et expérimentalement cela semble suffisant. Je le prouverai un peu plus tard.$n^2+1$}

Gelée , 15 octets

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

Un lien monadique acceptant un entier non négatif qui donne 1si "Secretly Fibonacci" et 0autrement.

Essayez-le en ligne! (trop inefficace pour les cas de test plus importants)

Comment?

‘ÆḞ€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 octets

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}

Essayez-le en ligne!

C # (.NET de base) , 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;}

Essayez-le en ligne!

-3 octets: changé pendant la boucle en for (grâce à Olivier Grégoire )
-6 octets: les retours commutés utilisent une variable, b et c initialisés en dehors des boucles (merci à Kevin Cruijssen )
-17 octets: condition changée dans la deuxième boucle pour se déplacer si hors boucle et combiner avec retour, variables b et c réutilisées dans la dernière boucle (merci à raznagul )

Non 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 octets

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

Essayez-le en ligne!

1, &[+] ... * > $_ n'est que la séquence de Fibonacci, arrêtée à un endroit non infini pratique (le numéro d'entrée).

$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0est une séquence de nombres, en commençant par le numéro d'entrée, et chaque élément successif obtenu en soustrayant le plus grand nombre de Fibonacci inférieur ou égal à l'élément précédent de l'élément précédent. La séquence se termine quand 0est atteinte. Par exemple, si $_est 140, alors cette séquence est 140, 51, 17, 4, 1, 0.

Soustraire un de cette séquence le traite comme un nombre, sa longueur et la différence est le nombre de nombres de Fibonacci qui, additionnés, donnent le numéro d'entrée. Ensuite, ce numéro est vérifié pour l'appartenance à la première séquence de Fibonacci.

Perl 6 , 48 octets

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

Essayez-le en ligne!

Transforme l'entrée en une liste de représentations Zeckendorf à plusieurs reprises jusqu'à ce qu'elle atteigne un seul nombre, puis vérifie si la longueur de la séquence était inférieure à 4.

La fonction Zenckendorf au milieu provient principalement de la réponse de Sean avec quelques améliorations.

Explication:

{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

Par exemple, la séquence de 2est 2 1puisque 2est déjà un nombre de Fibonacci. La séquence de 140est 140 5 1et puisque 5 est un nombre de Fibonacci, cela renvoie vrai. La séquence de 33est 33 4 2 1, et comme ce 4n'est pas un nombre de Fibonacci, la séquence est de longueur 4.

05AB1E , 14 octets

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

Essayez-le en ligne . Pas de suite de tests pour tous les cas de test, car le counter_variablene peut pas être réinitialisé à 0 .. J'ai tout vérifié à la main et ils sont corrects.

Explication:

Δ      }          # 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)

REMARQUE: le counter_variableserait 5pour l'entrée 139et 6pour l'entrée 140, car pour que la Δboucle vérifie la pile reste la même, elle fait bien sûr une itération supplémentaire.

Haskell , 64 octets

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

Essayez-le en ligne!

Retina 0.8.2 , 61 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. Explication:

.+
$*

Convertissez en unaire.

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

Comptez le nombre de numéros de Fibonacci nécessaires.

La première alternance concerne les nombres de Fibonacci qui sont au moins 2. Lors de la première passe, \2n'existe pas encore, mais heureusement c'est facultatif, donc nous n'avons pas à le faire correspondre. \1n'existe pas non plus, mais heureusement, nous avons l'alternative \G.qui correspond à un seul caractère au début du match. Les deux \2et \1donc prendre la valeur 1.

Lors des passes suivantes, \2existe, nous essayons donc de le faire correspondre. Cette fois, si elle échoue, elle échoue \1également (car elle est plus grande que \2), mais si elle réussit, elle (?>)empêche le retour en arrière, donc si elle \2correspond, mais \1pas, nous n'essayons pas simplement \1. ( \G1échoue toujours depuis que nous avons avancé après le début du patch.) Finalement \2prend la valeur précédente de \1while \1prend la somme des deux valeurs.

Nous faisons donc correspondre autant de numéros de Fibonacci que possible, en ajoutant au fur et à mesure. Puisque les sommes partielles de la séquence 1, 2, 3, 5...sont à 0, 1, 3, 6, 11...savoir 2 de moins que les nombres de Fibonacci, nous terminons en faisant correspondre 2 à la fin.

Cela ne correspond évidemment pas à 1 lui-même, donc une alternance gère ce cas.

.+
$*

Convertissez en unaire.

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

Testez s'il s'agit d'un numéro de Fibonacci. Cela utilise la même idée que le premier test, mais il utilise à la ^place de \Get nous devons également correspondre exactement, donc il utilise une capture facultative au lieu d'une alternance car c'est golfier (mais cela augmente les nombres de capture de 1).

Rétine , 35 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. Explication:

.+
*

Convertissez en unaire.

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

Comptez le nombre de numéros de Fibonacci nécessaires. (En bouclant à la fois la conversion et le nombre, vous économisez un octet entier au lieu d'obtenir le nombre en unaire en premier lieu.)

2}

Effectuez les étapes précédentes deux fois au total. Cela prend le nombre de nombres de Fibonacci nécessaires pour additionner le nombre de nombres de Fibonacci.

^1$

Si le nombre était secrètement Fibonacci, le résultat est 1.

Python 2 , 146 137 octets

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)

Essayez-le en ligne!

f () est une fonction récursive qui renvoie la valeur du nième nombre de Fibonacci. Tiré de cette réponse .

g () est une fonction récursive qui renvoie la représentation de Zeckendorf du nombre donné sous la forme d'une liste d'entiers.

Étant donné que tous les nombres de Fibonacci auront une longueur de retour d'un élément de g (), h () vérifie si la longueur de g () de g (n) == 1.

EDIT: 9 octets enregistrés grâce à nedla2004 . J'oublie toujours que les lambdas ne sont pas toujours la meilleure solution ...