29
\$\begingroup\$

We are all familiar with the famous Fibonacci sequence, that starts with 0 and 1, and each element is the sum of the previous two. Here are the first few terms (OEIS A000045):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584

Given a positive integer, return the closest number of the Fibonacci sequence, under these rules:

  • The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer. For example, 34 is the closest Fibonacci number to 30, because |34 - 30| = 4, which is smaller than the second closest one, 21, for which |21 - 30| = 9.

  • If the given integer belongs to the Fibonacci sequence, the closest Fibonacci number is exactly itself. For example, the closest Fibonacci number to 13 is exactly 13.

  • In case of a tie, you may choose to output either one of the Fibonacci numbers that are both closest to the input or just output them both. For instance, if the input is 17, all of the following are valid: 21, 13 or 21, 13. In case you return them both, please mention the format.

Default Loopholes apply. You can take input and provide output through any standard method. Your program / function must only handle values up to 108.


Test Cases

Input -> Output

1    -> 1
3    -> 3
4    -> 3 or 5 or 3, 5
6    -> 5
7    -> 8
11   -> 13
17   -> 13 or 21 or 13, 21
63   -> 55
101  -> 89
377  -> 377
467  -> 377
500  -> 610
1399 -> 1597

Scoring

This is , so the shortest code in bytes in every language wins!

\$\endgroup\$
  • \$\begingroup\$ Sandbox. \$\endgroup\$ – Mr. Xcoder Jul 19 '17 at 15:01
  • \$\begingroup\$ FWIW, here is some Python code on SO for doing this efficiently for large inputs, along with a script that can be used for timing various algorithms. \$\endgroup\$ – PM 2Ring Jul 20 '17 at 7:56
  • \$\begingroup\$ Is 0 considered as a positive integer? \$\endgroup\$ – Alix Eisenhardt Jul 21 '17 at 12:53
  • \$\begingroup\$ @AlixEisenhardt No. Positive integer n implies n ≥ 1. \$\endgroup\$ – Mr. Xcoder Jul 21 '17 at 12:56

31 Answers 31

1
2
0
\$\begingroup\$

Pyth, 27 bytes

J[Z1)WgQeJ=aJ+eJ@J_2)hoaNQJ

Test suite.

Python 3 translation:
Q=eval(input())
def a(x):
    return abs(Q-x)
J=[0,1]
while Q>=J[-1]:
    J.append(J[-1]+J[-2])
print(sorted(J,key=a)[0])
|improve this answer|||||
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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