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

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!

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!

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?)