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

Neim, 5 bytes

f𝐖𝕖S𝕔


Explanation:

f       Push infinite Fibonacci list
𝐖                     93
𝕖     Select the first ^ elements
This is the maximum amount of elements we can get before the values overflow
which means the largest value we support is 7,540,113,804,746,346,429
S𝕔   Closest value to the input in the list


In the newest version of Neim, this can be golfed to 3 bytes:

fS𝕔


As infinite lists have been reworked to only go up to their maximum value.

Try it online!

• How is this 5 bytes when there are 2 characters there? And what is the difference between the first and second solution? – caird coinheringaahing Jul 19 '17 at 23:32
• Are you counting bytes or characters? It appears the first is 15 bytes, and the second 7 bytes. – Nateowami Jul 20 '17 at 3:33
• This probably has some kind of own codepage in which each character is own byte meaning the first one is 5 bytes ans the second is 3 bytes. The difference between the two is that the first one selects the first 93 elements manual while the second snipet in a newer version automatically selects the highest possible value that the languages int size can handle – Roman Gräf Jul 20 '17 at 6:13
• @cairdcoinheringaahing I've often had issues with people not being able to see my programs. Screenshot – Okx Jul 20 '17 at 9:34
• @Okx Oh OK, interesting, I would not have guessed. – Nateowami Jul 20 '17 at 14:38

Mathematica, 30 bytes

Array[Fibonacci,2#]~Nearest~#&


Try it online!

Jelly, 9 7 bytes

-2 bytes thanks to @EriktheOutgolfer

‘RÆḞạÐṂ


Try it online!

Golfing tips welcome :). Takes an int for input and returns an int-list.

            ' input -> 4
‘           ' increment -> 5
R          ' range -> [1,2,3,4,5]
ÆḞ        ' fibonacci (vectorizes) -> [1,1,2,3,5,8]
ÐṂ     ' filter and keep the minimum by:
ạ       ' absolute difference -> [3,3,2,1,1,4]
' after filter -> [3,5]

• You can remove µḢ. – Erik the Outgolfer Jul 19 '17 at 17:12
• @EriktheOutgolfer as in: "There is a way to do it if you think about it", or as in "If you literally just backspace them it still works"? – nmjcman101 Jul 19 '17 at 17:14
• As in "it's allowed by the rules". :P – Erik the Outgolfer Jul 19 '17 at 17:17
• Ah. Thank you! (Filler text) – nmjcman101 Jul 19 '17 at 17:18

R, 70676462 60 bytes

-2 bytes thanks to djhurio!

-2 more bytes thanks to djhurio (boy can he golf!)

F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]


Since we only have to handle values up to 10^8, this works.

Try it online!

Reads n from stdin. the while loop generates the fibonacci numbers in F (in decreasing order); in the event of a tie, the larger is returned. This will trigger a number of warnings because while(F<1e8) only evaluates the statement for the first element of F with a warning

Originally I used F[which.min(abs(F-n))], the naive approach, but @djhurio suggested (F-n)^2 since the ordering will be equivalent, and order instead of which.min. order returns a permutation of indices to put its input into increasing order, though, so we need [1] at the end to get only the first value.

faster version:

F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][‌​1]


only stores the last two fibonacci numbers

• Nice one. -2 bytes F=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1] – djhurio Jul 19 '17 at 16:37
• And the fast version with the same number of bytes F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1] – djhurio Jul 19 '17 at 16:47
• @djhurio nice! thank you very much. – Giuseppe Jul 19 '17 at 17:08
• I like this. -2 bytes again F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1] – djhurio Jul 19 '17 at 18:21
• Using a builtin to generate the fibnums is shorter: numbers::fibonacci(x<-scan(),T) – JAD Jul 20 '17 at 11:42

Python 3, 84 bytes

lambda k:min(map(f,range(2*k)),key=lambda n:abs(n-k))
f=lambda i:i<3or f(i-1)+f(i-2)


Try it online!

It may work, but it's certainly not fast...

Outputs True instead of 1, but in Python these are equivalent.

05AB1E, 6 bytes

nÅFs.x


Try it online!

PowerShell, 80 74 bytes

param($n)for($a,$b=1,0;$a-lt$n;$a,$b=$b,($a+$b)){}($b,$a)[($b-$n-gt$n-$a)]


(Try it online! temporarily unresponsive)

Iterative solution. Takes input $n, sets $a,$b to be 1,0, and then loops with Fibonacci until $a is larger than the input. At that point, we index into ($b,$a) based on Boolean of whether the difference between the first element and $n is greater than between $n and the second element. That's left on the pipeline, output is implicit.

Python, 55 52 bytes

f=lambda x,a=1,b=1:[a,b][b-x<x-a]*(b>x)or f(x,b,a+b)


Try it online!

Java 7, 244 234 Bytes

 String c(int c){for(int i=1;;i++){int r=f(i);int s=f(i-1);if(r>c && s<c){if(c-s == r-c)return ""+r+","+s;else if(s-c > r-c)return ""+r;return ""+s;}}} int f(int i){if(i<1)return 0;else if(i==1)return 1;else return f(i-2)+f(i-1);}

• Why don't you use Java 8 and turn this into a lambda? You can also remove static if you want to stick with Java 7. – Okx Jul 19 '17 at 15:54
• You have two errors in your code (r>c&&s<c should be r>=c&&s<=c, s-c should be c-s), You could remove not required whitespace, use int f(int i){return i<2?i:f(--i)+f(--i);}, use a single return statement with ternary operator in c and remove the special handling for c-s==r-c as returning either value is allowed. – Nevay Jul 19 '17 at 20:58
• @Nevay I don't see the error, I've tested it without fails – 0x45 Jul 20 '17 at 7:10

JavaScript (ES6), 67 bytes

f=(n,k,y)=>(g=k=>x=k>1?g(--k)+g(--k):k)(k)>n?x+y>2*n?y:x:f(n,-~k,x)


Test cases

f=(n,k,y)=>(g=k=>x=k>1?g(--k)+g(--k):k)(k)>n?x+y>2*n?y:x:f(n,-~k,x)

console.log(f(1   )) // -> 1
console.log(f(3   )) // -> 3
console.log(f(4   )) // -> 3 or 5 or 3, 5
console.log(f(6   )) // -> 5
console.log(f(7   )) // -> 8
console.log(f(11  )) // -> 13
console.log(f(17  )) // -> 13 or 21 or 13, 21
console.log(f(63  )) // -> 55
console.log(f(101 )) // -> 89
console.log(f(377 )) // -> 377
console.log(f(467 )) // -> 377
console.log(f(500 )) // -> 610
console.log(f(1399)) // -> 1597

JavaScript (Babel Node), 41 bytes

f=(n,i=1,j=1)=>j<n?f(n,j,j+i):j-n>n-i?i:j


Based on ovs's awesome Python answer

Try it online!

Ungolfed

f=(n,i=1,j=1)=> // Function f: n is the input, i and j are the most recent two Fibonacci numbers, initially 1, 1
j<n?           // If j is still less than n
f(n,j,j+i)    //  Try again with the next two Fibonacci numbers
:              // Else:
j-n>n-i?i:j   //  If n is closer to i, return i, else return j

• This was commented on my answer but it would make it stop working for 0 (not that it needs to; I just want it to): f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i) – Neil Jul 21 '17 at 13:28

JavaScript (ES6), 41 bytes

f=(n,x=0,y=1)=>y<n?f(n,y,x+y):y-n>n-x?x:y
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0

Rounds up by preference.

• Almost identical to the version I was working on. At least you didn't use the same variable names or I would have been freaked out. – Grax Jul 19 '17 at 16:37
• @Grax Huh, now you mention it, Business Cat beat me to it... – Neil Jul 19 '17 at 16:49
• (Well, almost... I made my version work with 0, because why not?) – Neil Jul 19 '17 at 16:50
• f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y) Since you don't have to work with 0, you can golf a bit more. – Alix Eisenhardt Jul 21 '17 at 13:00

dc, 52 bytes

si1d[dsf+lfrdli>F]dsFxli-rlir-sdd[lild-pq]sDld<Dli+p


Try it online!

Takes input at run using ?

Edited to assume top of stack as input value, -1 byte.

Input is stored in register i. Then we put 1 and 1 on the stack to start the Fibonacci sequence, and we generate the sequence until we hit a value greater than i. At this point we have two numbers in the Fibonacci sequence on the stack: one that is less than or equal to i, and one that is greater than i. We convert these into their respective differences with i and then compare the differences. Finally we reconstruct the Fibonacci number by either adding or subtracting the difference to i.

Oops, I was loading two registers in the wrong order and then swapping them, wasting a byte.

• Functions are allowed. – CalculatorFeline Jul 19 '17 at 17:38
• Thanks, I repeatedly missed that in the challenge's text. – brhfl Jul 19 '17 at 19:03

C# (.NET Core), 63 56 bytes

-1 byte thanks to @Neil

-6 bytes thanks to @Nevay

n=>{int a=0,b=1;for(;b<n;a=b-a)b+=a;return n-a>b-n?b:a;}


Try it online!

• Does for(;b<n;a=b,b+=c)c=a; save a byte? – Neil Jul 19 '17 at 21:00
• You can remove c by using b+=a,a=b-a (should save 6 bytes). – Nevay Jul 19 '17 at 21:06

Python 3, 103 bytes

import math
def f(n):d=5**.5;p=.5+d/2;l=p**int(math.log(d*n,p))/d;L=[l,p*l];return round(L[2*n>sum(L)])


Try it online!

Python 3, 72 bytes

lambda n:r(p**r(math.log(d*n,p))/d)
import math
d=5**.5
p=.5+d/2
r=round


Try it online!

My first PPCG submission. Instead of either calculating Fibonacci numbers recursively or having them predefined, this code uses how the n-th Fibonacci number is the nearest integer to the n-th power of the golden ratio divided by the root of 5.

• Nice job! Welcome to PPCG :) – musicman523 Jul 19 '17 at 19:20
• To fairly calculate the byte count of your code I think you need to assign the lambda, as shown in the other Python answers. However, this algorithm doesn't always work correctly for n in range(1, 1+10**8). Eg, n=70 returns 89, but it should return 55. Here are the n values < 120 that it gives wrong answers for: (27, 44, 70, 71, 114, 115, 116). For testing purposes, you may like to use the nearest_fib_PM2R function I linked in my comment on the question. – PM 2Ring Jul 20 '17 at 8:39
• @PM2Ring You're right, I made a stupid mistake... I now have a correct solution, but with a lot more bytes. As for the lambda, I believe you're wrong. I believe the answers assigning lambda only do so because they use recursion. The other Python 3 answers doesn't assign the first lambda, for example. – SteamyRoot Jul 20 '17 at 10:04

C (gcc), 868583 76 bytes

f(n){n=n<2?:f(n-1)+f(n-2);}i,j,k;g(n){for(;k<n;j=k,k=f(i++));n=k-n<n-j?k:j;}


Try it online!

Python 2, 43 bytes

f=lambda n,a=0,b=1:a*(2*n<a+b)or f(n,b,a+b)


Try it online!

Iterates through pairs of consecutive Fibonacci numbers (a,b) until it reaches one where the input n is less than their midpoint (a+b)/2, then returns a.

Written as a program (47 bytes):

n=input()
a=b=1
while 2*n>a+b:a,b=b,a+b
print a

f=lambda n,a=0,b=1:b/2/n*(b-a)or f(n,b,a+b)


x86-64 Machine Code, 24 bytes

31 C0 8D 50 01 92 01 C2 39 FA 7E F9 89 D1 29 FA 29 C7 39 D7 0F 4F C1 C3


The above bytes of code define a function in 64-bit x86 machine code that finds the closest Fibonacci number to the specified input value, n.

The function follows the System V AMD64 calling convention (standard on Gnu/Unix systems), such that the sole parameter (n) is passed in the EDI register, and the result is returned in the EAX register.

Ungolfed assembly mnemonics:

; unsigned int ClosestFibonacci(unsigned int n);
xor    eax, eax        ; initialize EAX to 0
lea    edx, [rax+1]    ; initialize EDX to 1

CalcFib:
xchg   eax, edx        ; swap EAX and EDX
add    edx, eax        ; EDX += EAX
cmp    edx, edi
jle    CalcFib         ; keep looping until we find a Fibonacci number > n

mov    ecx, edx        ; temporary copy of EDX, because we 'bout to clobber it
sub    edx, edi
sub    edi, eax
cmp    edi, edx
cmovg  eax, ecx        ; EAX = (n-EAX > EDX-n) ? EDX : EAX
ret


Try it online!

The code basically divides up into three parts:

• The first part is very simple: it just initializes our working registers. EAX is set to 0, and EDX is set to 1.
• The next part is a loop that iteratively calculates the Fibonacci numbers on either side of the input value, n. This code is based on my previous implementation of Fibonacci with subtraction, but…um…isn't with subtraction. :-) In particular, it uses the same trick of calculating the Fibonacci number using two variables—here, these are the EAX and EDX registers. This approach is extremely convenient here, because it gives us adjacent Fibonacci numbers. The candidate potentially less than n is held in EAX, while the candidate potentially greater than n is held in EDX. I'm quite proud of how tight I was able to make the code inside of this loop (and even more tickled that I re-discovered it independently, and only later realized how similar it was to the subtraction answer linked above).

• Once we have the candidate Fibonacci values available in EAX and EDX, it is a conceptually simple matter of figuring out which one is closer (in terms of absolute value) to n. Actually taking an absolute value would cost way too many bytes, so we just do a series of subtractions. The comment out to the right of the penultimate conditional-move instruction aptly explains the logic here. This either moves EDX into EAX, or leaves EAX alone, so that when the function RETurns, the closest Fibonacci number is returned in EAX.

In the case of a tie, the smaller of the two candidate values is returned, since we've used CMOVG instead of CMOVGE to do the selection. It is a trivial change, if you'd prefer the other behavior. Returning both values is a non-starter, though; only one integer result, please!

. 2 } + " .
| ' = = ' . @
. & } 1 . !
_ | . _ }
$_ } {  Broken down: start: ? { 2 ' * //set up 2*target number " ' 1 //initialize curr to 1 main loop: } = + //next + curr + last " - //test = next - (2*target) branch: <= 0 -> continue; > 0 -> return continue: { } = & //last = curr } = & //curr = next return: { } ! @ //print last  Like some other posters, I realized that when the midpoint of last and curr is greater than the target, the smaller of the two is the closest or tied for closest. The midpoint is at (last + curr)/2. We can shorten that because next is already last + curr, and if we instead multiply our target integer by 2, we only need to check that (next - 2*target) > 0, then return last. Common Lisp, 69 bytes (lambda(n)(do((x 0 y)(y 1(+ x y)))((< n y)(if(<(- n x)(- y n))x y))))  Try it online! Perl 6, 38 bytes {(0,1,*+*...*>$_).sort((*-$_).abs)[0]}  Test it { # bare block lambda with implicit parameter ｢$_｣

( # generate Fibonacci sequence

0, 1,  # seed the sequence
* + *  # WhateverCode lambda that generates the rest of the values
...    # keep generating until
* > $_ # it generates one larger than the original input # (that larger value is included in the sequence) ).sort( # sort it by ( * -$_ ).abs  # the absolute difference to the original input
)[0]              # get the first value from the sorted list
}


For a potential speed-up add .tail(2) before .sort(…).

In the case of a tie, it will always return the smaller of the two values, because sort is a stable sort. (two values which would sort the same keep their order)

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


Pyth, 19 bytes

JU2VQ=+Js>2J)hoaNQJ


Try it here

Explanation

JU2VQ=+Js>2J)hoaNQJ
JU2                  Set J = [0, 1].
VQ=+Js>2J)        Add the next <input> Fibonacci numbers.
oaNQJ  Sort them by distance to <input>.
h       Take the first.


(%)a b x|abs(b-x)>abs(a-x)=a|1>0=b%(a+b)\$x