Previous Fibonacci number

Question

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

Answer 1

K (ngn/k), 21 22 bytes

{_x%1.618033988749895}

Try it online!

Increased 1 byte to round the number.

Answer 2

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.

Answer 3

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!

Answer 4

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

Answer 5

Charcoal, 24 bytes

ＮθＦ²⊞υιＷ‹⌈υθ⊞υΣ…⮌υ²Ｉ§υ±²

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

Ｎθ

Input the target.

Ｆ²⊞υι

Start with [0, 1].

Ｗ‹⌈υθ

Repeat until the target is reached.

⊞υΣ…⮌υ²

Generate the next Fibonacci number.

Ｉ§υ±²

Output the highest one less than the input.

Answer 6

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)

Answer 7

C (gcc), 27 bytes

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

Port of Unmitigated's JavaScript answer.

Try it online!

Answer 8

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.

Answer 9

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)

Answer 10

Ruby, 29 bytes

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

Try it online!

Answer 11

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

Answer 12

Go, 59 bytes

import."math"
func f(n float64)float64{return Round(n/Phi)}

Attempt This Online!

wow built-in constants

Calculated version, 72 bytes

import."math"
func f(n float64)float64{return Round(2*n/(1+Pow(5,0.5)))}

Attempt This Online!

Answer 13

><>, 17 bytes

01\~n;
=?\:@+:{:}

Try it online

Explanation

Starts at 0,1.
Calculates the next Fibonacci number until we reach the input.
Prints the second newest.

Answer 14

J, 12 14 bytes

1.61803<.@%~>:

Pretty self-explanatory.

Attempt This Online!

1.61803<.@%~>:
            >:  NB. increment input
1.61803         NB. golden ratio
          %~    NB. flip arg order and divide
       <.@      NB. then floor the result

I saw 1.618 might be too inaccurate. -:>:%:5 results in 1.61803, so I added the extra digits.

Answer 15

Raku, 40 bytes

sub p(\n,\a=0,\b=1){n==b??a!!p(n,b,a+b)}

Try it online!

Answer 16

Scala, 43 bytes

Try it online!

def f(n:Int)=((n*math.sqrt(5)-n+1)/2).toInt