Our warmest thanks to Clive Fraser for this problem sequence!
You are strongly advised to solve problem #337 Introducing Zeckendorf before attempting this one.
The Fibonacci series is very well known. Every number in the series (except for the first two numbers) is the
sum of the previous two numbers. The first two numbers are usually taken to be 0 and 1. However, for the
purpose of this problem we will take the first two numbers to be 1 and 2. This creates the Fibonacci series
1, 2, 3, 5, 8, 13, 21, 34, 55, ...
The Belgian mathematician Edouard Zeckendorf formulated an interesting theorem about the representation of integers as sums of Fibonacci numbers.
Zeckendorf's theorem states that every positive integer can be represented uniquely as the sum of one or
more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.
For example, 50 = 3 + 13 + 34 is an allowed representation. Conversely 23 = 5 + 5 + 13 is not an allowed
representation because of the repeated use of 5.
36 = 2 + 5 + 8 + 21 is also not an allowed representation because 5 and 8 are consecutive Fibonacci
numbers. However, for this problem we are going to remove the restriction on consecutive Fibonacci numbers
(creating a Zeckendorf Lite representation) so 36 = 2 + 5 + 8 + 21 is now an allowed Zeckendorf Lite
representation. We will retain the requirement for distinct Fibonacci numbers so 23 = 5 + 5 + 13 is not an
allowed Zeckendorf Lite representation.
Consider the integer 29. This has the following distinct Zeckendorf Lite representations:
1 + 2 + 5 + 8 + 13
1 + 2 + 5 + 21
3 + 5 + 8 + 13
3 + 5 + 21
8 + 21
So there are 5 distinct Zeckendorf Lite representations of the integer 29.
In this problem you will be given some positive integers and are to find the number of distinct ways in which each of the numbers can be represented as a Zeckendorf Lite sum.
Input/Output description: The first line of the input data will contain a single integer N, the number of
integers to process. N lines will follow. Each line contains a single number (less than 10^18). Find the
number of distinct Zeckendorf Lite representations of the integer. Combine all answers into a single string,
separated by spaces.
Example:
input:
10
29
125
1484
9120
55710
1147643
2666190
13841223
118461137
2258433142
answer:
5 5 18 24 65 22 782 1152 2900 10044