# Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$

I am able to solve this using brute force but curious if there is a better approach.

Given the function $$F(A,B,C,D) = (A + B + C) / D$$ where each variable is in the first 7 distinct values of the Fibonacci sequence, i.e. $$[1,2,3,5,8,13,21]$$,determine the values which most closely approximate any given target value.

the values can be repetitions, so $$[1,1,1,1]$$ is a valid combination.

• For 7 values it's quite likely brute-force will be better in practice than anything else, particularly if you precalculate all possible values and then you can do a binary search. Are you interested in solutions for the first $N$ fibonacci values? Jul 21 at 7:02
• Yes in practice you're right and I get a solution in under a second, this is more of a curiosity thing if there's a more generalized approach if I were to add an arbitrary number of variables in the numerator or extend the domain to an arbitrary number of fibonacci values. Jul 21 at 12:50
• This is not a research-level question. I am not sure where curiosity questions belong, maybe on cs.stackexchange.com? Jul 22 at 8:45

If we iterate over all possible values for $$D$$, we want to calculate for each the maximum $$n \leq xD$$ which is a sum of three Fibonacci numbers, and the minimum such $$n \geq xD$$. It isn't hard to see that a number can be represented as a sum of three Fibonacci numbers iff its Zeckendorf representation has at most 3 ones. Since lexicographical order on the Zeckendorf representations (assuming they are padded with zeros to be the same length) is the same a the normal order of integers, so once we find the Zechendorf representation of $$\lfloor xD \rfloor$$ we can find the biggest string less than it with no two consecutive zeros and at most three 1s, and that will be our first $$n$$, and then we can do something similar for $$\lceil xD \rceil$$ and for bigger values.
I believe this algorithm can be implemented in $$O(n^2)$$, but this is tricky because the Fibonacci numbers have length of $$O(n)$$ bits.