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

42 Answers 42

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

Desmos, 25 22 bytes

-3 bytes thanks to @Steffan

pp-p~1
f(n)=round(n/p)

Port of some of the other answers.

Try It On Desmos!

\$\endgroup\$
1
  • \$\begingroup\$ @Steffan yep, thanks! \$\endgroup\$
    – Aiden Chow
    Jul 20 at 21:09
2
\$\begingroup\$

Fig, \$5\log_{256}(96)\approx\$ 4.116 bytes

_\mG}

Try it online!

No round builtins, so I use the old increment and floor trick.

_\mG}
    } # The input number incremented
 \    # Divided by
  mG  # The golden ratio
_     # Floor
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 24 bytes

NθF²⊞υιW‹⌈υθ⊞υΣ…⮌υ²I§υ±²

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input the target.

F²⊞υι

Start with [0, 1].

W‹⌈υθ

Repeat until the target is reached.

⊞υΣ…⮌υ²

Generate the next Fibonacci number.

I§υ±²

Output the highest one less than the input.

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

C (gcc), 27 bytes

f(a){a=2*a/(1+sqrt(5))+.5;}

Port of Unmitigated's JavaScript answer.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 26 bytes \$\endgroup\$
    – att
    May 26 at 23:59
1
\$\begingroup\$

BitCycle (-u), 93 bytes

Try it online!

    v    / <^ ~+AA/v
1v ~B B vC   v> ^/ <
v ~ ?\BB\v  ?= ~ !
1D~ D ^  +C >~
ADA~^   +  ^   B@

The program generates a Fibonacci number, doubles it, and compares it to the input. If it's greater than or equal to the input, it is halved and output, otherwise it's discarded and the next number is generated.

          the question mark [input] hits a splitter [\]. one bit is redirected while the rest of the bits move to top B  [input].
1v ~B     top D [2fib(n-1)], which starts with 2, is emptied to right A [2fib(n)] and left A [intermittent]. 
v ~ ?\B   bottom D [2fib(n-2)] empties to right A.
1D~       right A empties to top D and top B [2fib(n)].
ADA~      left A empties to bottom D [2fib(n-2)].
v    / <   *'top B' refers to BOTH B's; 'bottom B' refers to BOTH B's*
B B vC     if bottom B [input] isn't empty, it hits a splitter. one bit is redirected to D [intermittent] while the rest of the bits re-enter bottom B.
  BB\v     top B [2fib(n)] hits a splitter. one bit is redirected to top C [2fib(n)] while the rest re-enter top B.
D ^  +C    if bottom B is empty, top B hits another splitter. one bit is redirected to bottom C ["2fib(n) >= input"?].
^   +  ^   D will eventually empty to bottom B.
   ^ ~+AA/v   *'A' refers to BOTH A's
C   v> ^/ <   if bottom C ["2fib(n) >= input"?] isn't empty, it hits a switch. the bits are redirected to B [terminator]
   ?= ~ !     if bottom C is empty, top C [2fib(n)] hits a switch. the bits are redirected into the question mark, destroying them.
 C >~         if bottom C isn't empty, top C empties to A [fib(n)]
      B@      A hits 2 splitters. one bit is redirected away, and another is redirected into the exclamation mark [output]. the rest of the bits re-enter A.
              B empties into the at-sign, which terminates the program.
\$\endgroup\$
1
\$\begingroup\$

Brainfuck, 94 bytes

>>>>+<<<+[[-]<[->+>+<<]>>[-<<+>>]>>[->+>+<<]>>[-<<+>>]<<<[->>+<<]>[-<+>]>[-<+<<<->>>>]<<<<]>>

Input should be entered into the first address. Output is at the address pointed to when the program terminates.

Might add an explanation later.

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

Brev, 50 45 bytes

(define((p x y)n)(if(= n y)x((p y(+ x y))n)))

Example:

(map (p 0 1) '(34 13 55 2))
=> (21 8 34 1)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 29 bytes

->n{a=b=1;0while n>a=b+b=a;b}

Try it online!

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

TI-BASIC, 13 bytes

round(2Ans(1+√(5))⁻¹,0

Hexdump:
(Token hex-values found here.)

12 32 72 10 31 70 BC 35 11 11 0C 2B 30 | round(2Ans(1+√(5))⁻¹,0

Takes input in Ans and prints the requested output in the challenge.

Explanation:

round(2Ans(1+√(5))⁻¹,0           ; full program

           1+√(5)                ; phi * 2
          (      )⁻¹             ; 1 / (phi * 2)
       Ans                       ; Ans / (phi * 2)
      2                          ; Ans / phi
round(              ,0           ; round to nearest integer

Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

TI-BASIC only has decimal precision up to 14 decimals for calculations and 10 decimals for equivalence.

Byte count is determined via the following steps:

  1. Find the program's size via MEM>Mem Mgmt/Del…>Prgm…
  2. Subtract the length of the program name
  3. Subtract the program header length, which is 9 bytes
\$\endgroup\$
0
\$\begingroup\$

Python, 28 bytes

lambda n:round(n/(1+5**.5)/2)

Too simple.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I don't think 1.618 is accurate enough for this to work for very high numbers. \$\endgroup\$
    – Steffan
    Sep 24 at 16:58
1
2

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.