Is this number secretly Fibonacci?

Question

Background

Most of you know what a Fibonacci number is. Some of you may know that all positive integers can be represented as a sum of one or more distinct Fibonacci numbers, according to Zeckendorf's Theorem. If the number of terms in the optimal Zeckendorf Representation of an integer n is itself a Fibonacci number, we will call n "secretly" Fibonacci.

For example:

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

Notes

• The optimal Zeckendorf Representation can be found using a greedy algorithm. Simply take the largest Fibonacci number <= n and subtract it from n until you reach 0
• All Fibonacci numbers can be represented as a sum of 1 Fibonacci number (itself). Since 1 is a Fibonacci number, all Fibonacci numbers are also secretly Fibonacci.

Challenge

Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.

Input

You may take input in any reasonable format. You may assume the input will be a single positive integer.

Output

Output one of two distinct results for whether the input is secretly Fibonacci. Examples include True/False, 1/0, etc.

Scoring

This is code-golf, so shortest answer in bytes wins! Standard loopholes are forbidden.

Test Cases

Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

Answer 1

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)

Try it online!

Answer 2

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

Try it online!

This makes use of the theorem that the two descriptions of OEIS A003714 are equivalent:

Fibbinary numbers: if \$n = F(i_1) + F(i_2) + \dots + F(i_k) \$ is the Zeckendorf representation of \$n\$ (i.e., write \$n\$ in Fibonacci number system) then \$a(n) = 2^{i_1} + 2^{i_2} + \dots + 2^{i_k}\$. Also numbers whose binary representation contains no two adjacent \$1\$'s.

We generate enough* such numbers, and then use z as a mapping from non-negative integers to “how many terms are in the Zeckendorf representation of \$n\$?” by counting 1s in binary.

Then it remains to check if z[n] is a Fibonacci number, i.e. z[z[n]] == 1.

^{*At least, \$n^2+1\$ feels like enough, and experimentally it seems to be enough. I'll prove this some time later.}

Answer 3

Jelly, 15 bytes

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

A monadic link accepting a non-negative integer which yields 1 if "Secretly Fibonacci" and 0 otherwise.

Try it online! (too inefficient for the larger test cases)

How?

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

Answer 4

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}

Try it online!

Answer 5

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;}

Try it online!

-3 bytes: changed while loop to for (thanks to Olivier Grégoire)
-6 bytes: switched returns to use variable, initialized b and c outside of loops (thanks to Kevin Cruijssen)
-17 bytes: changed condition in second loop to move if out of loop and combine with return, reused b and c variables in last loop (thanks to raznagul)

Ungolfed:

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
}

Answer 6

Perl 6, 58 bytes

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

Try it online!

1, &[+] ... * > $_ is just the Fibonacci sequence, stopped at a convenient non-infinite place (the input number).

$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0 is a sequence of numbers, starting with the input number, and each successive element obtained by subtracting the largest Fibonacci number less than or equal to the previous element from the previous element. The sequence terminates when 0 is reached. For example, if $_ is 140, then this sequence is 140, 51, 17, 4, 1, 0.

Subtracting one from this sequence treats it as a number, its length, and the difference is the number of Fibonacci numbers which, added together, give the input number. Then this number is checked for membership in the first Fibonacci sequence.

Answer 7

Perl 6, 48 bytes

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

Try it online!

Transforms the input to a list of Zeckendorf Representation repeatedly until it reaches a single number and then checks if the length of the sequence was less than 4.

The Zenckendorf function in the middle is mostly from Sean's answer with a couple of improvements.

Explanation:

{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

For example, the sequence for 2 is 2 1 since 2 is already a Fibonacci number. The sequence for 140 is 140 5 1, and since 5 is a Fibonacci number this returns true. The sequence for 33 is 33 4 2 1, and since 4 is not a Fibonacci number the sequence is of length 4.

Answer 8

05AB1E, 14 bytes

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

Try it online. No test suite for all test cases, because the counter_variable cannot be reset to 0.. I verified all by hand though, and they are correct.

Explanation:

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

NOTE: The counter_variable would be 5 for input 139 and 6 for input 140, because in order for the Δ-loop to check the stack remained the same, it does of course an additional iteration.

Answer 9

Haskell, 64 bytes

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

Try it online!

Answer 10

Retina 0.8.2, 61 bytes

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

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

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

Count the number of Fibonacci numbers needed.

The first alternation deals with Fibonacci numbers that are at least 2. On the first pass, \2 does not exist yet, but fortunately it's optional, so we don't have to match it. \1 doesn't exist either, but fortunately we have the alternative of \G. which matches a single character at the start of the match. Both \2 and \1 therefore take on the value 1.

On subsequent passes, \2 exists, so we try to match it. This time if it fails then \1 also fails (since it is bigger than \2), but if it succeeds, the (?>) prevents backtracking, so if \2 matches but \1 does not we don't try just \1. (\G1 always fails since we've advanced past the start of the patch.) Finally \2 takes on the previous value of \1 while \1 takes on the sum of the two values.

We therefore match as many Fibonacci numbers as we can, adding as we go. Since the partial sums of the sequence 1, 2, 3, 5... are 0, 1, 3, 6, 11... i.e. 2 less than the Fibonacci numbers we finish by matching 2 at the end.

This obviously fails to match 1 itself so an alternation handles that case.

.+
$*

Convert to unary.

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

Test whether this is a Fibonacci number. This uses the same idea as the first test but it uses ^ instead of \G and we also need to match exactly, so it uses an optional capture instead of an alternation as that's golfier (but it increases the capture numbers by 1).

Retina, 35 bytes

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

Try it online! Link includes test cases. Explanation:

.+
*

Convert to unary.

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

Count the number of Fibonacci numbers needed. (Looping both the conversion and count saves a whole byte over getting the count in unary in the first place.)

2}

Perform the previous steps twice in total. This takes the count of Fibonacci numbers needed to sum to the count of Fibonacci numbers.

^1$

If the number was secretly Fibonacci then the result is 1.

Answer 11

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)

Try it online!

f() is a recursive function that returns the value of the nth Fibonacci number. Taken from this answer.

g() is a recursive function that returns the Zeckendorf Representation of the given number as a list of integers.

Since all Fibonacci numbers will have a return length of one item from g(), h() checks if the length of the g() of g(n) == 1.

EDIT: Saved 9 bytes thanks to nedla2004. I keep forgetting that lambdas aren't always the best solution...