34
\$\begingroup\$

The sequence of Fibonacci numbers is defined as follows:

\$ F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} \$

Given a Fibonacci number, return the previous Fibonacci number in the sequence. You do not need to handle the inputs \$ 0 \$ or \$ 1 \$, nor any non-Fibonacci numbers.

Errors as a result of floating point inaccuracies are permitted.

This is , so the shortest code in bytes wins.

\$\endgroup\$
0

37 Answers 37

17
\$\begingroup\$

Vyxal, 4 bytes

kg/ṙ

Try it Online!

Port of Unmitigated's JavaScript answer

  /  # Divide by...
kg   # Phi
   ṙ # Round
\$\endgroup\$
13
\$\begingroup\$

R, 23 22 20 bytes

Edit: -1 byte thanks to pajonk, then -2 bytes thanks to att

\(x)(x*5^.5-x+1)%/%2

Attempt This Online!

The ratio between consecutive fibonacci numbers famously converges towards the golden ratio phi, equal to (1+5^.5)/2.
This is sufficiently accurate that rounding produces the correct value for all fibonacci numbers, including even the second 1 at the start which we don't need to handle here.

(Edit after reading some other answers: this was independently-derived, but is also the approach taken by Luis Mendo and unmitigated)

\$\endgroup\$
4
  • \$\begingroup\$ Shouldn't this possibly work for -1 byte? \$\endgroup\$
    – pajonk
    May 26 at 9:58
  • \$\begingroup\$ @pajonk - Thanks - yes! Somehow whenever I'd tried something like that, it always came out longer (probably because I was adding .5 instead of your clever way to add 1)... \$\endgroup\$ May 26 at 10:43
  • \$\begingroup\$ 20 \$\endgroup\$
    – att
    May 27 at 0:01
  • \$\begingroup\$ @att - lovely, thanks! Whenever I look at something like this I think 'Doh! Why didn't I think of that...?' \$\endgroup\$ May 27 at 7:09
11
\$\begingroup\$

JavaScript, 21 17 bytes

n=>n*5**.5-n+1>>1

Try it online!

-4 bytes thanks to att.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 17 bytes \$\endgroup\$
    – att
    May 27 at 0:09
10
\$\begingroup\$

R, 27 bytes

\(x){while(x>T)T=F+(F=T);F}

Attempt This Online!

Similar to this answer, iterates through the Fibonacci sequence until T==x and returns F.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Realised that this is the shortest R fibonacci function (with F>T) and have cited it here and here... \$\endgroup\$ May 26 at 21:39
  • 1
    \$\begingroup\$ @DominicvanEssen odd, I really thought I had seen this approach somewhere before but can't seem to track it down. \$\endgroup\$
    – Giuseppe
    May 27 at 13:45
  • \$\begingroup\$ You might want to post it directly into the fibonacci challenge (as suggested by the author of the otherwise-shortest-but-actually-rather-longer answer...) \$\endgroup\$ Jun 2 at 5:31
  • \$\begingroup\$ @DominicvanEssen posted! \$\endgroup\$
    – Giuseppe
    Jun 2 at 13:53
9
\$\begingroup\$

C(gcc), 57,55,53,50,45, 36 bytes

x;y;f(a){for(x=y=1;y-a-x;y+=x=y-x);}

Naive approach based on calculating all previous Fibonacci numbers, breaking when we reach the input.

Try it here

Edit: Thanks for Neil, golfing 2 5 bytes.

Edit2: Thanks Dominic van Essen for golfing an other 5 bytes.

Edit3: Thanks att for golfing 9 bytes.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ May 25 at 22:34
  • 1
    \$\begingroup\$ You already have the previous number, so you can just use y-a as the condition and return x, saving 2 bytes, but you can also use globals and for to save a few more bytes: x;y;c;f(a){for(x=y=1;y-a;c=y,y=x+y,x=c);return x;}. \$\endgroup\$
    – Neil
    May 25 at 23:01
  • \$\begingroup\$ 45 bytes with a rather hacky return trick... \$\endgroup\$ May 25 at 23:12
  • \$\begingroup\$ 36 bytes \$\endgroup\$
    – att
    May 26 at 0:49
9
\$\begingroup\$

x86-64 assembly, 13 12 bytes

6a 01 58 99 92 01 c2 39 fa 75 f9 c3

In assembly:

previous:
    push 1
    pop rax
    cdq     # zeroes rdx
previous_loop:
    xchg eax,edx
    add edx,eax
    cmp edx,edi
    jne previous_loop
    ret

Try it online!

Uses the usual calling convention of taking the first argument in rdi and returning in rax. It's also valid x86-32, just with edi and eax instead.

It's pretty simple- it just explicitly computes Fibonacci numbers and returns if the new number is equal to the input. At the end of a loop, rdx contains the next Fibonacci number and rax contains the previous. If rdx is equal to the input rdi, then the loop terminates (and thus rax, the previous number, is returned). Otherwise the two are swapped, and the loop begins again.

This uses 32-bit registers to save a few bytes, so it only works up to the 47th Fibonacci number, 2971215073. It can be expanded to work with 64-bit numbers by changing all the registers to 64-bit, at the cost of 2 bytes:

6a 01 58 99 48 0f c1 c2 48 39 fa 75 f7 c3

The added bytes are the REX.W (0x48) prefix that swaps the operand size to 64-bit. xchg rax,rdx; add rdx,rax is also replaced with xadd rdx,rax, which is shorter because it uses one fewer REX.W prefix.

-1 byte thanks to @PeterCordes.

\$\endgroup\$
2
  • \$\begingroup\$ If we start with EAX=1 we can cdq for EDX=0 in 1 byte. That should enable savings even without changing the calling convention, e.g. xchg after add? If necessary, xadd can exchange-and-add between any two registers in one more byte than add. But with EAX involved it's the same size as xchg eax, reg / add. It's faster; only 3 uops on Intel or 2 on AMD, same as xchg, one less than xchg+add. And lower latency. (uops.info). \$\endgroup\$ May 26 at 21:10
  • \$\begingroup\$ @PeterCordes Good call. Swapping the two just adds one extra loop, since the first loop becomes effectively a no-op of add edx,0. It changes the output for an input of 1 to 0 instead of 1, but those are both equally valid. \$\endgroup\$
    – Chris
    May 27 at 0:18
8
\$\begingroup\$

Factor + math.unicode, 21 19 18 14 bytes

[ φ / round ]

Try it online!

-4 thanks to @DominicvanEssen!

Divide the input by the golden ratio and round the result.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Interesting fact: 1-phi (the golden ratio) is equal to 1/phi. So you can just divide by the golden ratio instead of multiplying by phi-1... \$\endgroup\$ May 25 at 23:16
  • \$\begingroup\$ Does Factor need the whitespace? If not you could save a few bytes \$\endgroup\$ Jun 11 at 15:26
5
\$\begingroup\$

Python 3, 41 bytes

f=lambda n,a=0,b=1:n-b and f(n,b,a+b)or a

Try it online!

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

Wolfram Language (Mathematica), 17 bytes

Round[2#/++√5]&

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ haha ++√5 love it! \$\endgroup\$ May 26 at 16:13
5
\$\begingroup\$

Python 3, 29 28 27 24 bytes

The footer uses @Noodle9's checker code.

1 byte saved thanks to @Chris!

3 more bytes off thanks to Albert.Lang!

Function that returns an integer-valued float. It fails for large inputs due to floating-point inaccuracies.

lambda n:~n*(1-5**.5)//2

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 27 bytes, Try it online! \$\endgroup\$
    – Chris
    May 26 at 6:43
  • \$\begingroup\$ ~n*(1-5**.5)//2 seems to work just as well. \$\endgroup\$ May 26 at 17:46
4
\$\begingroup\$

JavaScript, Node.js, 32 bytes

-1 thanks to Arnauld

n=>(y=1,f=x=>y-n?f(y,y+=x):x)(0)

Explanation:

This is a recursive solution, based off one of the two most common recursive fibonacci algorithms, which involves a function f(x, y) = f(y, x + y) that stops at some point. With this function, x is always a fibonacci number, and y is always the fibonacci number after it, so once y is the fibonacci number we were given as input, we know x is the one before it.

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

05AB1E, 4 bytes

ÅF¨θ

Try it online or verify some more test cases.

¨θ could be a lot of different alternatives, like Á¤ or `\.

Explanation:

ÅF    # Push a list of Fibonacci numbers lower than or equal to the (implicit) input
  ¨   # Remove the last one (the input)
   θ  # Keep the next last one
      # (after which it is output implicitly as result)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Oof, sorry about accidentally answering it the same way. Guess I hadn't refreshed the page since then. Nice to know my solution was at least somewhat good, haha :) \$\endgroup\$
    – Bismarck71
    May 25 at 22:20
4
\$\begingroup\$

MathGolf, 6 4 bytes

)φ/i

-2 bytes porting @emanresuA's Vyxal answer, which is in turn a port of @Unmitigated's JavaScript answer.

Try it online.

Original 6 bytes answer:

╒fg<┤Þ

Try it online.

g< could alternatively also be á>: try it online.

Explanation:

)      # Increase the (implicit) input-integer by 1
 φ/    # Divide it by the golden ratio 1.618033988749895
   i   # Truncate it to an integer
       # (the +1 and truncate act as a round builtin here, which MathGolf lacks)
       # (after which the entire stack is output implicitly as result)
╒      # Push a list in the range [1, (implicit) input-integer]
 f     # Get the 0-based n'th Fibonacci number for each value in this list
  g    # Filter it by:
   <   #  Where it's smaller than the (implicit) input-integer
    ┤  # Extract the trailing value
     Þ # Discard the list from the stack, keeping just that value
       # (after which the entire stack is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Haskell, 38 37 bytes

This works for an aribrary size of inputs. We iterate through the Fibonacci sequence until we find some number x, that is larger than half the input n. This is works because the previous fibonacci number is roughly 0.618*n. The Fibonacci list f was borrowed from R. Martinho Fernandes.

g n=[x|x<-f,2*x>=n]!!0
f=0:scanl(+)1f

Try it online!

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

Retina 0.8.2, 26 bytes

.+
$*
(\2?(\1)|1)+1
$1$2
1

Try it online! Link includes test cases. Explanation: Loosely based on @MartinEnder's Retina answer to Am I a Fibonacci Number?.

.+
$*

Convert to unary.

(\2?(\1)|1)+1

Match as many Fibonacci numbers as possible. The first iteration only matches the leading 1 while subsequent iterations match iteration of the loop matches the penultimate Fibonacci number (if any), then the previous Fibonacci number, while saving it as the next penultimate Fibonacci number. The match actually sums the Fibonacci sequence, resulting in a sequence one less than the Fibonacci sequence, so a final 1 needs to be matched.

$1$2

Because the match is summing the sequence, the final capture of the sequence $1 is actually the Fibonacci number before the one we want, so we need to add on the penultimate matched Fibonacci number $2.

1

Convert to decimal.

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

PARI/GP, 16 bytes

n->n*2\/(1+5^.5)

Attempt This Online!

Port of Unmitigated's JavaScript answer. a\/b is a short way to write round(a/b).

PARI/GP's floating point number is 128-bit by default. This gives the correct result until the 184th Fibonacci number (127127879743834334146972278486287885163).

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

PowerShell, 31 bytes

[int]("$args"/1.61803398874989)

Try it online!

The ratio of two adjacent numbers in the Fibonacci series rapidly approaches ((1 + sqrt(5)) / 2). So if N is divided by ((1 + sqrt(5)) / 2) and then rounded, the resultant number will be the previous Fibonacci number...

at least according to this article.

-16 thanks mazzy

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 1. The constant 1.61803398874989 is shorter then the expression (1+[math]::sqrt(5))/2) :) 2. $x is redundant. 3. -replace'\..*' is shorter then [math]::round() :) Welcome to the CodeGolf \$\endgroup\$
    – mazzy
    May 26 at 18:42
  • 1
    \$\begingroup\$ $args is an array. use "$args" to get a value. \$\endgroup\$
    – mazzy
    May 26 at 18:44
  • 1
    \$\begingroup\$ see also Tips for golfing in PowerShell \$\endgroup\$
    – mazzy
    May 26 at 18:45
  • 1
    \$\begingroup\$ Try it online! or try &{[int]("$args"/1.61803398874989)} 233 in your PS console \$\endgroup\$
    – mazzy
    May 26 at 18:57
  • 2
    \$\begingroup\$ 1.618033989 is shorter and is sufficient for all 47 possible inputs, here's a test. \$\endgroup\$
    – Ruslan
    May 27 at 23:03
3
\$\begingroup\$

Jelly, 4 bytes

‘:Øp

Add 1 to the input and integer-divide by the golden ratio.

Try it online!

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

Python 3, 50 bytes 48 bytes

def f(n,a=0,b=1):
 while b<n:a,b=b,a+b
 return a

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$ May 26 at 21:44
  • 1
    \$\begingroup\$ Welcome to CGCC! You can save 2 bytes: by changing b!=n to b<n, and by removing the second line and using def f(n,a=0,b=1): instead. Enjoy your stay! Oh, and if you haven't seen it yet Tips for golfing in Python and Tips for golfing in 'all languages' might be interesting to read through. :) \$\endgroup\$ May 27 at 6:42
  • 1
    \$\begingroup\$ You can also save some bytes by reducing your indentation to only one space per line, because that's all that is required in Python. \$\endgroup\$
    – pxeger
    May 27 at 6:57
  • \$\begingroup\$ @pxeger The code had tabs for indent, so it wouldn't matter \$\endgroup\$
    – axolotl
    May 27 at 14:43
3
\$\begingroup\$

Husk, 5 bytes

→←xİf

Try it online!

Makes use of the built-in list of Fibonacci numbers.

Explanation

→←xİf
   İf  Take the list of Fibonacci numbers
  x    Split it on occurrences of the input
 ←     Get the first sub-list
→      Get the last element of that
\$\endgroup\$
3
\$\begingroup\$

Stax, 10 bytes

Çâ'Ç,¼)í"─

Run and debug it

Approach

  • Start with an infinite Fibonacci generator
  • Keep values while they are less than the input, resulting in array e.g. [1, 1, 2, 3, 5].
  • Extract last element.
\$\endgroup\$
1
3
\$\begingroup\$

K (ngn/k), 12 11 bytes

--2!(1-%5)*

Try it online!

Applies @Albert.Lang's approach from this comment.

  • (1-%5)* calculate 1 minus the square root of 5 (i.e. -1.2360679774997898) and multiply it by the (implicit) input
  • -2! integer divide by 2 (rounding towards 0, e.g. -8!-7 returns -1)
  • - negate (and implicitly return)
\$\endgroup\$
3
\$\begingroup\$

Pip, 10 bytes

Ua*DRT5//2

Attempt This Online!

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

rSNBATWPL, 32 bytes

x~for{t=1;x>t;f=b}{b=t;t=f+t}$-1

Try It Online!

Port of R answer.

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

rSNBATWPL, 31 bytes

n~(y=1;x~cond{y!n}{{y=y+x}}$x)$

Try It Online!

Port of my JS answer:

This is a recursive solution, based off one of the two most common recursive fibonacci algorithms, which involves a function f(x, y) = f(y, x + y) that stops at some point. With this function, x is always a fibonacci number, and y is always the fibonacci number after it, so once y is the fibonacci number we were given as input, we know x is the one before it.

\$\endgroup\$
1
  • \$\begingroup\$ Wow, nice language name. I wonder who could have possibly made it \$\endgroup\$ Jun 11 at 15:30
2
\$\begingroup\$

Haskell, 57 bytes (or 14 bytes)

Complete solution which handles arbitrarily large input:

f n=(x!!).flip(-)1.length.fst.span(<n)$x
x=scanl(+)0(1:x)

Explanation:

  1. Let x be a an infinite list of fibonacci numbers ( x = scanl (+) 0 (1:x) ).

  2. Partition list into a tuple ([Int], [Int]), the leftmost portion being all numbers < than the input.

  3. Take the first portion with fst.

  4. Subtract 1 from the length of that list.

  5. Extract (!!) the number with the resultant (idx--) index from the infinite list.

Simple solution:

round.(/0.618)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ It's actually quite a bit shorter just to define x as a global function: ato.pxeger.com/… \$\endgroup\$
    – pxeger
    May 26 at 16:42
  • \$\begingroup\$ True, suppose I was aiming for the one-liner aesthetic \$\endgroup\$ May 26 at 17:29
  • 1
    \$\begingroup\$ If the round.(/0.618) is indeed a valid program or funciton, would you mind to post a link so it can be run & tested? I am quite sceptical that it will return the correct answer for large-ish inputs, for instance 17711... \$\endgroup\$ May 26 at 20:38
2
\$\begingroup\$

Vyxal, 6 bytes

ÞFḟ‹∆f

Try it Online!

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

Husk, 6 bytes

i*½←√5

Try it online!

Same strategy as my R answer (and also those of Luis Mendo and unmitigated).

(Husk has a fibonacci sequence built-in, but using it here seems to come-out longer at 7 bytes: S!o←€İf).

Update: proven wrong by Leo

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

Rattle, 17 bytes

|r`=+s[$+~[\gq]]0

Try it Online!

Explanation

|             take input
 r`           save input as special arg
   =          set top of stack to 0
    +         increment
     s        save value of 1 to storage
      [...]0  infinite loop

 $            swap top of stack with value in storage
  +~          increment top of stack by value in storage
    [\...]    if the top of the stack is equal to the special arg...
      g       get the value in storage (i.e. the previous Fibonacci value)
       q      quit and print implicitly
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 21 22 bytes

{_x%1.618033988749895}

Try it online!

Increased 1 byte to round the number.

\$\endgroup\$
1
  • \$\begingroup\$ You need to round the number, because the output has to be an integer. \$\endgroup\$
    – pxeger
    Jun 2 at 13:56

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.