-1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$ Jul 21, 2023 at 7:02
  • $\begingroup$ 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. $\endgroup$
    – john doe
    Jul 21, 2023 at 12:50
  • $\begingroup$ This is not a research-level question. I am not sure where curiosity questions belong, maybe on cs.stackexchange.com? $\endgroup$ Jul 22, 2023 at 8:45

1 Answer 1

-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.