# Find the closest Fibonacci Number

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!

• – Mr. Xcoder Jul 19 '17 at 15:01
• 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. – PM 2Ring Jul 20 '17 at 7:56
• Is 0 considered as a positive integer? – Alix Eisenhardt Jul 21 '17 at 12:53
• @AlixEisenhardt No. Positive integer n implies n ≥ 1. – Mr. Xcoder Jul 21 '17 at 12:56

## 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])