Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
