Here comes the third part of a series kindly created by Clive Fraser!
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.
Note that the unique Zeckendorf representation of the integer 50 consists of 3 Fibonacci numbers. We will
call this the SIZE of the Zeckendorf representation of 50. In this problem you will be given a range of
positive integers and are to find the SIZE of the Zeckendorf representation for each integer in the range and
then to give the DISTRIBUTION of these SIZEs as the answer to the problem. The DISTRIBUTION is a series
of integers, separated by spaces. The first is the number of Zeckendorf representations with SIZE = 1,
the second is the number with SIZE = 2 and so on, until the largest SIZE in the DISTRIBUTION has been
included.
Consider the range of integers from 20 to 40 (inclusive). If we find the SIZE of the Zeckendorf
representation for each of the 21 integers in this range we get the following results:
SIZE = 1 2 integers (21, 34)
SIZE = 2 9 integers (22, 23, 24, 26, 29, 35, 36, 37, 39)
SIZE = 3 9 integers (20, 25, 27, 28, 30, 31, 32, 38, 40)
SIZE = 4 1 integer (33)
The DISTRIBUTION of SIZEs for this range is 2 9 9 1. The DISTRIBUTION has no SIZE values greater than
4 so only 4 values are included in it. In the example below, the SIZE values range from 1 to 12.
There are 10 instances of SIZE = 1 and 13 instances of SIZE = 12.
Input/Output description: The first and only line of the input data will contain 2 integers A and B
(not greater than 10^18). These represent the first and last numbers of the given range. Both A and B are
included in the range. Find the DISTRIBUTION of SIZEs for the integers in this range. Give the answer as a
single string, with values separated by spaces.
Example:
input:
1234 123456
answer:
10 179 1373 5916 15824 27650 32096 24354 11441 3003 364 13