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

20
\$\begingroup\$

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)
\$\endgroup\$
14
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ How is this 5 bytes when there are 2 characters there? And what is the difference between the first and second solution? \$\endgroup\$ – caird coinheringaahing Jul 19 '17 at 23:32
  • 1
    \$\begingroup\$ Are you counting bytes or characters? It appears the first is 15 bytes, and the second 7 bytes. \$\endgroup\$ – Nateowami Jul 20 '17 at 3:33
  • \$\begingroup\$ 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 \$\endgroup\$ – Roman Gräf Jul 20 '17 at 6:13
  • 1
    \$\begingroup\$ @cairdcoinheringaahing I've often had issues with people not being able to see my programs. Screenshot \$\endgroup\$ – Okx Jul 20 '17 at 9:34
  • 1
    \$\begingroup\$ @Okx Oh OK, interesting, I would not have guessed. \$\endgroup\$ – Nateowami Jul 20 '17 at 14:38
10
\$\begingroup\$

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!

\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – djhurio Jul 19 '17 at 16:37
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – djhurio Jul 19 '17 at 16:47
  • 1
    \$\begingroup\$ @djhurio nice! thank you very much. \$\endgroup\$ – Giuseppe Jul 19 '17 at 17:08
  • 1
    \$\begingroup\$ 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] \$\endgroup\$ – djhurio Jul 19 '17 at 18:21
  • \$\begingroup\$ Using a builtin to generate the fibnums is shorter: numbers::fibonacci(x<-scan(),T) \$\endgroup\$ – JAD Jul 20 '17 at 11:42
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Grax Jul 19 '17 at 16:37
  • \$\begingroup\$ @Grax Huh, now you mention it, Business Cat beat me to it... \$\endgroup\$ – Neil Jul 19 '17 at 16:49
  • \$\begingroup\$ (Well, almost... I made my version work with 0, because why not?) \$\endgroup\$ – Neil Jul 19 '17 at 16:50
  • \$\begingroup\$ 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. \$\endgroup\$ – Alix Eisenhardt Jul 21 '17 at 13:00
6
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ You can remove µḢ. \$\endgroup\$ – Erik the Outgolfer Jul 19 '17 at 17:12
  • \$\begingroup\$ @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"? \$\endgroup\$ – nmjcman101 Jul 19 '17 at 17:14
  • \$\begingroup\$ As in "it's allowed by the rules". :P \$\endgroup\$ – Erik the Outgolfer Jul 19 '17 at 17:17
  • \$\begingroup\$ Ah. Thank you! (Filler text) \$\endgroup\$ – nmjcman101 Jul 19 '17 at 17:18
5
\$\begingroup\$

Mathematica, 30 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ NASM listings are nice for codegolf answers, since they mix the machine code bytes with the original commented source somewhat compactly. I used nasm foo.asm -l /dev/stdout | cut -b -28,$((28+12))- to trim some columns between the machine code and source in a recent answer. \$\endgroup\$ – Peter Cordes Jul 20 '17 at 20:38
  • 1
    \$\begingroup\$ In 32-bit code, you can get eax=0 and edx=1 in only 4 bytes instead of 5, with xor eax,eax / cdq / inc edx. So you could make a 32-bit custom-calling-convention version that saved a byte. \$\endgroup\$ – Peter Cordes Jul 20 '17 at 20:45
  • \$\begingroup\$ I used to do that, @Peter, but there's a lot of confusion here over submissions being in "assembly" or "machine code". Apparently some of the experienced users maintain that there is a difference, and object to my counting the bytes of machine code for an answer that is presented using assembly mnemonics. Naturally, I think this is stupid, because "assembly" is just a mnemonic representation of the machine bytes, but I got outvoted. I've found that the separate presentation creates less friction, even though I don't personally like it as well. \$\endgroup\$ – Cody Gray Jul 21 '17 at 6:23
  • \$\begingroup\$ The other trick is nice—thanks. I should have thought of that, I use cdq a lot in code-golf answers. A custom calling convention isn't required. I usually use the Microsoft __fastcall calling convention for 32-bit code. The nice thing about this is it's supported by GCC with an annotation, so you can still use the TIO service that everyone wants to see. \$\endgroup\$ – Cody Gray Jul 21 '17 at 6:24
  • \$\begingroup\$ Ah yes, any old register calling convention works for you . My most recent codegolf answer needed pointers in edi/esi for lodsb/stosb, and only x86-64 SysV does that (fun fact: on purpose for that reason, because some functions pass on their args to memset / memcpy, and I guess gcc at the time liked to inline string ops). \$\endgroup\$ – Peter Cordes Jul 21 '17 at 7:44
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Neil Jul 21 '17 at 13:28
4
\$\begingroup\$

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, Fk = φk/√5 + φk/√5 = round(φk/√5). So the return value switches from Fk − 1 to Fk exactly where k = logφ(n⋅2√5) − 1, or n = φk + 1/(2√5), which is within 1/4 of Fk + 1/2 = (Fk − 1 + Fk)/2.

\$\endgroup\$
  • \$\begingroup\$ Damn, I knew something like this had to be possible. Well done! (+1) \$\endgroup\$ – SteamyRoot Jul 20 '17 at 12:17
3
\$\begingroup\$

05AB1E, 6 bytes

nÅFs.x

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice job! Welcome to PPCG :) \$\endgroup\$ – musicman523 Jul 19 '17 at 19:20
  • \$\begingroup\$ 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. \$\endgroup\$ – PM 2Ring Jul 20 '17 at 8:39
  • \$\begingroup\$ @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. \$\endgroup\$ – SteamyRoot Jul 20 '17 at 10:04
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

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!

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

Q/KDB+, 51 bytes

{w where l=min l:abs neg[x]+w:{x,sum -2#x}/[x;0 1]}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Jul 20 '17 at 12:47
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Japt -g, 8 bytes

ò!gM ñaU

Try it

\$\endgroup\$
1
\$\begingroup\$

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);}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Okx Jul 19 '17 at 15:54
  • \$\begingroup\$ 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. \$\endgroup\$ – Nevay Jul 19 '17 at 20:58
  • \$\begingroup\$ @Nevay I don't see the error, I've tested it without fails \$\endgroup\$ – 0x45 Jul 20 '17 at 7:10
1
\$\begingroup\$

Pyke, 6 bytes

}~F>R^

Try it online!

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

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!

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

Haskell, 48 bytes

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

Try it online!

\$\endgroup\$

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.