<p>If we iterate over all possible values for <span class="math-container">$D$</span>, we want to calculate for each the maximum <span class="math-container">$n \leq xD$</span> which is a sum of three Fibonacci numbers, and the minimum such <span class="math-container">$n \geq xD$</span>. 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 <span class="math-container">$\lfloor xD \rfloor$</span> 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 <span class="math-container">$n$</span>, and then we can do something similar for <span class="math-container">$\lceil xD \rceil$</span> and for bigger values.</p>
<p>I believe this algorithm can be implemented in <span class="math-container">$O(n^2)$</span>, but this is tricky because the Fibonacci numbers have length of <span class="math-container">$O(n)$</span> bits.</p>

CC BY-SA 4.0
2023-07-22T04:05:30.693Z
2023-07-22T04:05:30.693Z
Command Master
<p>I am able to solve this using brute force but curious if there is a better approach.</p>
<p>Given the function <span class="math-container">$F(A,B,C,D) = (A + B + C) / D$</span> where each variable is in the first 7 distinct values of the Fibonacci sequence, i.e. <span class="math-container">$[1,2,3,5,8,13,21]$</span>,determine the values which most closely approximate any given target value.</p>
<p>the values can be repetitions, so <span class="math-container">$[1,1,1,1]$</span> is a valid combination.</p>

CC BY-SA 4.0
2023-07-21T07:02:43.880Z
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?
Command Master
CC BY-SA 4.0
2023-07-21T12:50:48.643Z
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.
john doe
CC BY-SA 4.0
2023-07-22T08:45:26.753Z
This is not a research-level question. I am not sure where curiosity questions belong, maybe on https://cs.stackexchange.com?
Andrej Bauer
<approximation-algorithms><optimization><combinatorics>
Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$
john doe
# Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$

(Asked by: username_0 on 2023-07-20)

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.

**Tags:** approximation-algorithms, optimization, combinatorics
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: This is not a research-level question. I am not sure where curiosity questions belong, maybe on https://cs.stackexchange.com?  

---

## 1 answers

### Answer by username_1 on 2023-07-22. Score: -1

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.


---

