How to efficiently turn integers into Fibonacci coding?

Question

The Fibonacci sequence is obtained starting from 0 and 1, and then adding the last two numbers to get the next one.

All positive integers can be represented as the sum of a set of Fibonacci numbers without repetition. For example: 13 may be the sum of the sets {13}, {5.8} or {2,3,8}. But, as we have seen, some numbers have more than one set, the sum of which is equal to the number. If we add the restriction that sets cannot have two consecutive Fibonacci numbers, then we have a unique representation for each number.

We will use a binary sequence (only zeros and ones) for this. For example, 17 = 1 + 3 + 13. Then 17 = 100101. For a detailed explanation, see Figure 2.

I want to turn some integers into this representation, but integers can be very large. How to do it effectively.

Answer 1

First I want to tell you that I really liked this question, I did not know that all positive integers can be represented as the sum of a set of Fibonacci numbers without repetition, I saw the proof by induction, and it was amazing,
To answer your question, I think we need to understand how a presentation is created. I think a simple way to find this is that from the number we found the closest fibonacci element.
For example, if we want to represent 40:
We have Fib (9) = 34 and Fib (10) = 55, so the first element in the view is Fib (9)
since 40 is Fib (9) = 6 and (Fib (5) = 5 and Fib (6) = 8), the next element is Fib (5). So we have 40 = Fib (9) + Fib (5) + Fib (2)
Let me write this in C #

class Program { static void Main(string[] args) { List<int> fibPresentation = new List<int>(); int numberToPresent = Convert.ToInt32(Console.ReadLine()); while (numberToPresent > 0) { int k =1; while (CalculateFib(k) <= numberToPresent) { k++; } numberToPresent = numberToPresent - CalculateFib(k-1); fibPresentation.Add(k-1); } } static int CalculateFib(int n) { if (n == 1) return 1; int a = 0; int b = 1; // In N steps compute Fibonacci sequence iteratively. for (int i = 0; i < n; i++) { int temp = a; a = b; b = temp + b; } return a; } } 

Your result will be in fibPresentation

Answer 2

The problem itself is simple. You always choose the largest number of fibonacci less than the rest. You can ignore the restriction with consecutive numbers (since if you need both, the next is the sum of both, so you should have chosen this instead of the two initial ones).

Thus, the problem remains how to quickly find the largest Fibonacci number less than the number X. There is a trick that starts with the matrix (let's call it M)

 1 1 1 0 

You can calculate the Fibonacci number using matrix multiplications (xth number is M ^ x). More details here: https://www.nayuki.io/page/fast-fibonacci-algorithms . The end result is that you can calculate the number that you look at in the matrix multiplication O (logN).

You will need large calculations (multiplications and additions) if they do not fit into existing types. Also save the matrices corresponding to the forces of the two that you are calculating for the first time, since you will need them again for the results.

In general, this should be O ((logN) ^ 2 * large_number_multiplications / additions)).

Answer 3

This encoding is more accurately called the Zeckendorf view: see https://en.wikipedia.org/wiki/Fibonacci_coding

The greedy approach works (see https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem ), and here is the Python code that converts the number to this representation. It uses the first 100 Fibonacci numbers and works correctly for all inputs up to 927372692193078999175 (and incorrect for any larger inputs).

 fibs = [0, 1] for _ in xrange(100): fibs.append(fibs[-2] + fibs[-1]) def zeck(n): i = len(fibs) - 1 r = 0 while n: if fibs[i] <= n: r |= 1 << (i - 2) n -= fibs[i] i -= 1 return r print bin(zeck(17)) 

Output:

 0b100101 

Answer 4

It seems that the greedy approach works, it is enough to be able to invert the ratio N=Fn .

According to Binet's formula, Fn=[φ^n/√5] , where the brackets denote the nearest integer. Then with n=floor(lnφ(√5N)) you are very close to the solution.

 17 => n = floor(7.5599...) => F7 = 13 4 => n = floor(4.5531) => F4 = 3 1 => n = floor(1.6722) => F1 = 1 

(I do not exclude that some values ​​of n may be disabled by one.)

Answer 5

I'm not sure if this is effective enough for you, but you can just use Backtracking to find a (valid) view.

I would try to start the backtracking steps by taking as many chips as possible and switch only to smaller ones if the restriction is violated sequentially or only once .