Find the closest Fibonacci Number

Question

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 10⁸.

---

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 code-golf, so the shortest code in bytes in every language wins!

Answer 1

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

Same length:

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

Answer 2

Neim, 5 bytes

fS

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!

Answer 3

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!

Answer 4

R, 70 67 64 62 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

Answer 5

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]

Answer 6

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.

Answer 7

Mathematica, 30 bytes

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

Try it online!

Answer 8

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!

Answer 9

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.

Answer 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

Answer 11

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

Answer 12

Python, 74 bytes

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

Try it online!

How it works

For all k ≥ 0, since |φ^−k/√5| < 1/2, F_k = φ^k/√5 + φ^−k/√5 = round(φ^k/√5). So the return value switches from F_{k − 1} to F_k exactly where k = log_φ(n⋅2√5) − 1, or n = φ^{k + 1}/(2√5), which is within 1/4 of F_{k + 1}/2 = (F_{k − 1} + F_k)/2.

Answer 13

05AB1E, 6 bytes

nÅFs.x

Try it online!

Answer 14

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!

Sadly, had to use a def instead of lambda... There's probably much room for improvement here.

Original (incorrect) answer:

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.

Answer 15

C (gcc), 86 85 83 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!

Answer 16

Java (OpenJDK 8), 60 57 56 bytes

c->{int s=1,r=2;for(;c>r;s=r-s)r+=s;return c-s>r-c?r:s;}

Try it online!

-1 byte thanks to @Neil

Answer 17

Taxi, 2321 bytes

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Trunkers.Go to Trunkers:n 1 l 1 l.0 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 2 l.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[a]Pickup a passenger going to Rob's Rest.Pickup a passenger going to Magic Eight.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Rob's Rest:n.Go to Trunkers:s 1 l 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Trunkers.Pickup a passenger going to Magic Eight.Go to Zoom Zoom:n.Go to Trunkers:w 3 l.Go to Magic Eight:e 1 r.Switch to plan "b" if no one is waiting.Pickup a passenger going to Firemouth Grill.Go to Firemouth Grill:w 1 r.Go to Rob's Rest:w 1 l 1 r 1 l 1 r 1 r.Pickup a passenger going to Cyclone.Go to Bird's Bench:s.Pickup a passenger going to Addition Alley.Go to Cyclone:n 1 r 1 l 2 l.Pickup a passenger going to Addition Alley.Pickup a passenger going to Bird's Bench.Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Switch to plan "a".[b]Go to Trunkers:w 1 l.Pickup a passenger going to Cyclone.Go to Bird's Bench:w 1 l 1 r 1 l.Pickup a passenger going to Cyclone.Go to Rob's Rest:n.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to What's The Difference.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 l.Pickup a passenger going to Magic Eight.Go to Sunny Skies Park:e 1 r 1 l.Go to Cyclone:n 1 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to What's The Difference.Go to Sunny Skies Park:n 1 r.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 r 1 l.Pickup a passenger going to Magic Eight.Go to Magic Eight:e 1 r 2 l 2 r.Switch to plan "c" if no one is waiting.Go to Sunny Skies Park:w 1 l 1 r.Pickup a passenger going to The Babelfishery.Go to Cyclone:n 1 l.Switch to plan "d".[c]Go to Cyclone:w 1 l 2 r.[d]Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 2 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

Try it online!
Try it online with comments!

Un-golfed with comments:

[ Find the Fibonacci number closest to the input ]
[ Inspired by: https://codegolf.stackexchange.com/q/133365 ]


[ n = STDIN ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Trunkers.
Go to Trunkers: north 1st left 1st left.


[ Initialize with F0=0 and F1=1 ]
0 is waiting at Starchild Numerology.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd left.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 1st right 4th left.


[ For (i = 1; n > F(i); i++) { Store F(i) at Rob's Rest and F(i-1) at Bird's Bench } ]
[a]
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Magic Eight.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Rob's Rest: north.
Go to Trunkers: south 1st left 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Trunkers.
Pickup a passenger going to Magic Eight.
Go to Zoom Zoom: north.
Go to Trunkers: west 3rd left.
Go to Magic Eight: east 1st right.
Switch to plan "b" if no one is waiting.

[ n >= F(i) so iterate i ]
Pickup a passenger going to Firemouth Grill.
Go to Firemouth Grill: west 1st right.
Go to Rob's Rest: west 1st left 1st right 1st left 1st right 1st right.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: south.
Pickup a passenger going to Addition Alley.
Go to Cyclone: north 1st right 1st left 2nd left.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Bird's Bench.
Go to Addition Alley: north 2nd right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left.
Switch to plan "a".


[b]
[ F(i) > n which means n >= F(i-1) and we need to figure out which is closer and print it]
Go to Trunkers: west 1st left.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: west 1st left 1st right 1st left.
Pickup a passenger going to Cyclone.
Go to Rob's Rest: north.
Pickup a passenger going to Cyclone.
Go to Cyclone: south 1st left 1st left 2nd left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to What's The Difference.
Pickup a passenger going to What's The Difference.
[ Passengers:n, n, F(i-1) ]
Go to What's The Difference: north 1st left.
Pickup a passenger going to Magic Eight.
[ Passengers:n, n-F(i-1) ]
Go to Sunny Skies Park: east 1st right 1st left.
Go to Cyclone: north 1st left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to What's The Difference.
[ Passengers: n-F(i-1), F(i-1), F(i) ]
Go to Sunny Skies Park: north 1st right.
Pickup a passenger going to What's The Difference.
[ Passengers: n-F(i-1), F(i), n ]
Go to What's The Difference: north 1st right 1st left.
[ Passengers: n-F(i-1), F(i)-n ]
Pickup a passenger going to Magic Eight.
Go to Magic Eight: east 1st right 2nd left 2nd right.
Switch to plan "c" if no one is waiting.

[ If no one was waiting, then {n-F(i-1)} < {F(i)-n} so we return F(i-1) ]
Go to Sunny Skies Park: west 1st left 1st right.
Pickup a passenger going to The Babelfishery.
Go to Cyclone: north 1st left.
Switch to plan "d".

[c]
[ Otherwise {n-F(i-1)} >= {F(i)-n} so we return F(i) ]
[ Note: If we didn't switch to plan c, we still pickup F(i) but F(i-1) will be the *first* passenger and we only pickup one at The Babelfishery ]
[ Note: Because of how Magic Eight works, we will always return F(i) in the event of a tie ]
Go to Cyclone: west 1st left 2nd right.
[d]
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 2nd right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.

Answer 18

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.

Answer 19

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.

Answer 20

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!

Answer 21

Q/KDB+, 51 bytes

{w where l=min l:abs neg[x]+w:{x,sum -2#x}/[x;0 1]}

Answer 22

Hexagony, 37 bytes

?\=-${&"*.2}+".|'=='.@.&}1.!_|._}$_}{

Try it online!

ungolfed:

   ? \ = - 
  $ { & " * 
 . 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.

Answer 23

Brachylog, 22 bytes

;I≜-.∧{0;1⟨t≡+⟩ⁱhℕ↙.!}

Try it online!

Really all I've done here is paste together Fatalize's classic Return the closest prime number solution and my own Am I a Fibonacci Number? solution. Fortunately, the latter already operates on the output variable; unfortunately, it also includes a necessary cut which has to be isolated for +2 bytes, so the only choice point it discards is ⁱ, leaving ≜ intact.

Answer 24

Japt -g, 8 bytes

ò!gM ñaU

Try it

Answer 25

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);}

Answer 26

Pyke, 6 bytes

}~F>R^

Try it online!

}      -    input*2
 ~F    -   infinite list of the fibonacci numbers
   >   -  ^[:input]
    R^ - closest_to(^, input)

Answer 27

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!

Answer 28

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)

Answer 29

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.

Answer 30

Haskell, 48 bytes

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

Try it online!

Answer 31

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