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.
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
- 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.
Your challenge is to write a program or function that takes an integer and returns whether that integer is secretly Fibonacci.
You may take input in any reasonable format. You may assume the input will be a single positive integer.
Output one of two distinct results for whether the input is secretly Fibonacci. Examples include
This is code-golf, so shortest answer in bytes wins! Standard loopholes are forbidden.
Truthy (secretly Fibonacci) 1 2 4 50 140 300099 Falsey (NOT secretly Fibonacci) 33 53 54 139 118808