20
\$\begingroup\$

The Binet formula is a closed form expression for the \$n\$'th Fibonacci number:

$$F_n = \frac {\phi^n - (1-\phi)^n} {\sqrt 5}$$

where \$\phi = \frac {1 + \sqrt 5} 2\$ is the golden ratio. This formula works even when \$n\$ is negative or rational, and so can be a basis to calculating "complex Fibonacci numbers".

For example, by setting \$n = \frac 1 2\$, we can calculate \$F_\frac 1 2\$ as:

$$F_\frac 1 2 = \frac 1 {\sqrt 5} \left( \sqrt \frac {1+\sqrt 5} 2 - \sqrt \frac {1-\sqrt 5} 2 \right) \\ \approx 0.56886-0.35158i$$

You are to take a floating point, \$-10 \le n \le 10\$, with up to 3 decimals after the point, and output \$F_n\$, accurate to at least 5 decimal places. You may either round or truncate, so long as it is consistent. You may also choose to input as a rational number if you wish, or as a (numerator, denominator) pair. You may also choose whether integers should be suffixed with .0 or not, so long as it is consistent across all 21 integer inputs.

As the output will be a complex number in all but 21 cases, you may output in any reasonable format for such a type, including outputting as a (real, imag) pair. For the integer inputs, the imaginary part will be \$0\$. You may choose whether to output the imaginary part in this case (and returning an integer or float is perfectly fine).

This is , so the shortest code in bytes wins

Test cases

These all round their output, rather than truncate.


  n       Re(Fn)     Im(Fn)
-10      -55         0
  1        1         0
 -7       13         0
  3        2         0
  0.5      0.56886  -0.35158
  5.3      5.75045   0.02824
  7.5     16.51666   0.01211
 -1.5      0.21729  -0.92044
 -9.06    34.37587  -6.55646
  9.09    35.50413   0.00157
 -2.54     0.32202   1.50628
  5.991    7.96522   0.00071
 -6.033   -8.08507   0.84377
  8.472   26.36619  -0.00756

And a script to output all possible outputs in the same format (gets cut off on TIO due to the length).

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Brownie points for beating my 11 byte Jelly answer \$\endgroup\$ Apr 7 at 0:10
  • 2
    \$\begingroup\$ Relevant: youtube.com/watch?v=ghxQA3vvhsk \$\endgroup\$
    – Neil
    Apr 7 at 10:40
  • 6
    \$\begingroup\$ @Ausername Besides the fact this has been answered in JS already, it's pretty obvious this is possible in JS given it's plainly turing-complete \$\endgroup\$
    – pxeger
    Apr 7 at 16:48
  • 1
    \$\begingroup\$ @FedericoPoloni The output should be the principal root \$\endgroup\$ Apr 8 at 12:34
  • 1
    \$\begingroup\$ Related (as pointed out by tsh here). \$\endgroup\$
    – Arnauld
    Apr 8 at 13:23

15 Answers 15

10
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

(h=2/--√5;h^#-(1-h)^#)√.2&

Try it online!

Uses \$\frac{\sqrt 5+1}{2}=\frac{2}{\sqrt 5-1}\$. Mathematica's pre-increment/decrement operators still return the desired value when used on (non-variable) non-atoms.

The built-in Fibonacci is a continuous real function, the real part of the Binet formula: \$F_n=\frac{\phi^n-\cos(\pi n)\phi^{-n}}{\sqrt 5}\$.

\$\endgroup\$
0
7
\$\begingroup\$

Octave, 20 bytes

@(n)([1 1;1 0]^n)(2)

Try it online!

You know, this classical Fibonacci number formula still works here...

$$ F_x=\begin{bmatrix}1 & 0\end{bmatrix}\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^x\begin{bmatrix}0 \\ 1\end{bmatrix} $$


Aha, after I posted this answer. I try some searching about it. And I finally found out flawr's previous answer to Negative Fibonacci Numbers question. It just using the same codes. Also there are many other answers may simply fit this questions' requirement. I'm not sure if this is a duplicate here, but... They does solve this question with short codes...

\$\endgroup\$
7
\$\begingroup\$

R, 60 57 41 bytes

Just the straightforward golfed implementation. Stole the sqrt() = ^.5 trick from Level River St.

att and Dominic van Essen golfed off several bytes, thank you. My algebra is rusty! This version takes arguments in complex number notation.

function(x,g=.5+5^.5/2)(g^x-(1-g)^x)/5^.5

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 46 bytes (Also, you didn't update the TIO link) \$\endgroup\$
    – att
    Apr 7 at 5:17
  • \$\begingroup\$ 44 bytes... \$\endgroup\$ Apr 7 at 7:58
  • \$\begingroup\$ ...or 41 bytes with input using complex number notation. \$\endgroup\$ Apr 7 at 7:59
6
\$\begingroup\$

Python 3, 43 bytes

lambda x,p=.5+5**.5/2:(p**x-(1-p)**x)/5**.5

Try it online!

-6 bytes thanks to caird coinheringaahing (old version)
-6 bytes thanks to Noodle9 (old version)

-a lot of bytes after realizing i don't need sympy thanks to Noodle9
-1 byte thanks to dingledooper

\$\endgroup\$
5
  • \$\begingroup\$ You use 5**.5 twice. I don't know Python but can you set up a constant for this? I managed to save some bytes doing this in Ruby \$\endgroup\$ Apr 7 at 1:02
  • \$\begingroup\$ @LevelRiverSt defining a as 5**.5 and using a twice is the same length as using 5**.5 twice since i need the newline after the definition, and so i end up taking +2 bytes because i need to define a first and therefore have to move f= into the body. i'll think about golfing opportunities relating to this though. thanks! \$\endgroup\$
    – hyper-neutrino
    Apr 7 at 1:04
  • 3
    \$\begingroup\$ Python has complex number support? What? \$\endgroup\$
    – emanresu A
    Apr 7 at 4:44
  • 1
    \$\begingroup\$ What about .5+5**.5/2 instead of (1+5**.5)/2? \$\endgroup\$ Apr 7 at 6:46
  • 1
    \$\begingroup\$ @Ausername: Sure. Look into the complex type, imaginary number literals, and the standard cmath module. \$\endgroup\$ Apr 8 at 18:38
6
\$\begingroup\$

JavaScript (Node.js), 65 bytes

with(Math)f=x=>[(q=5**.5,q*=(++q/2)**x)/5-cos(x*=PI)/q,-sin(x)/q]

Try it online!

Simply a translation of given formula

$$ q = \sqrt5\cdot\left(\frac{\sqrt5+1}{2}\right)^x $$

$$ F_x=\frac{q}{5}-\frac{\left(-1\right)^x}{q}=\left(\frac{q}{5}-\frac{\cos\left(\pi x\right)}{q}\right) + \left(-\frac{\sin\left(\pi x\right)}{q}\right)\cdot i $$

Nothing special here.

I believe it is wrong language to use here. Use some languages with complex numbers support would be a better idea.

\$\endgroup\$
1
  • \$\begingroup\$ Can save another byte with q**-x instead of --q**x \$\endgroup\$
    – att
    Apr 7 at 6:40
5
\$\begingroup\$

MATL, 15 bytes

17Lt_Qwhi^d5X^/

Try it online! Or verify all test cases.

Explanation

17L    % Push ϕ (predefined literal)
t_Q    % Duplicate, negate, add 1: gives 1-ϕ
wh     % Swap, concatenate horizontally: gives [1-ϕ, ϕ]
i^     % Input n, element-wise power: gives [(1-ϕ)^n, ϕ^n]
d      % Consecutive difference(s): gives ϕ^n - (1-ϕ)^n
5X^    % Push 5, square root
/      % Divide: gives (ϕ^n - (1-ϕ)^n) / sqrt(5)
       % Implicit display
\$\endgroup\$
5
\$\begingroup\$

Charcoal, 25 bytes

⭆¹ΣE∕X⊘⊕×⟦¹±¹⟧₂⁵N₂⁵⎇μ⁻⁰λλ

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

         ⟦¹±¹⟧              Literal list `1, -1`
        ×                   Vectorised multiply by
              ₂             Square root of
               ⁵            Literal `5`
       ⊕                    Vectorised increment
      ⊘                     Vectorised halved
     X                      Vectorised raised to power
                N           Input as a number
    ∕                       Vectorised divide by
                 ₂          Square root of
                  ⁵         Literal `5`
   E               ⎇μ⁻⁰λλ   Negate the second element
  Σ                         Sum the elements
⭆¹                          Stringify

Charcoal doesn't really support complex numbers, but as it happens the Power of a negative number to a floating-point value will return a complex result; I just have to be careful not to use operations such as Negate and Cast where Charcoal will get confused as to which overload to use.

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

Jelly, 11 bytes

ØpC,$*÷5½¤I

Try it online!

Need to find where the 1 byte is :c 1 byte found thanks to Unrelated String :D

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

Ruby, 39 37 bytes

->n{((-p=(1-s=5**0.5)/2)**-n-p**n)/s}

Try it online!

With thanks to Dingus for a 1-byte improvement, and Att for a 1-byte improvement and a correction.

Uses the fact that ϕ-1 = 1/ϕ

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 37 bytes \$\endgroup\$
    – att
    Apr 7 at 5:03
  • 1
    \$\begingroup\$ \$(-\phi)^{-n}\$ also gets the sign of the imaginary part wrong \$\endgroup\$
    – att
    Apr 7 at 5:25
  • \$\begingroup\$ @att thanks for the 1 byte improvement and the correction! I shouldn't look at this site late at night. \$\endgroup\$ Apr 7 at 6:41
  • \$\begingroup\$ @att The conjugate is a valid branch cut of Binet's formula. \$\endgroup\$ Apr 7 at 9:16
5
\$\begingroup\$

Factor + math.unicode, 36 bytes

[ φ over ^ 1 φ - rot ^ - 5 √ / ]

Try it online!

Explanation:

It's a quotation (anonymous function) that takes a number as input and leaves a number as output. Factor seamlessly promotes floats and rational numbers to complex numbers when necessary (denoted by C{ real imaginary }). Assuming 0.5 is on top of the data stack when this quotation is called...

  • φ Push phi, the golden ratio, to the data stack.

    Stack: 0.5 1.618033988749895

  • over Put a copy of NOS (next on stack) at TOS (top of stack).

    Stack: 0.5 1.618033988749895 0.5

  • ^ Raise NOS to the TOS power.

    Stack: 0.5 1.272019649514069

  • 1 Push 1 to the data stack.

    Stack: 0.5 1.272019649514069 1

  • φ Push phi to the data stack.

    Stack: 0.5 1.272019649514069 1 1.618033988749895

  • - Subtract TOS from NOS.

    Stack: 0.5 1.272019649514069 -0.6180339887498949

  • rot Take the data stack object third from the top and move it to TOS.

    Stack: 1.272019649514069 -0.6180339887498949 0.5

  • ^ Raise NOS to the TOS power.

    Stack: 1.272019649514069 C{ 4.813788842079551e-17 0.7861513777574233 }

  • - Subtract TOS from NOS.

    Stack: C{ 1.272019649514069 -0.7861513777574233 }

  • 5 Push 5 to the data stack.

    Stack: C{ 1.272019649514069 -0.7861513777574233 } 5

  • Take the square root of TOS.

    Stack: C{ 1.272019649514069 -0.7861513777574233 } 2.23606797749979

  • / Divide NOS by TOS.

    Stack: C{ 0.568864481005783 -0.3515775842541429 }

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

J, 25 bytes

%:@5%~[:-/(-:1+(,-)%:5)&^

Try it online!

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

Java + Apache Commons Math, 138 136 134 bytes

n->{var a=Math.sqrt(5);return new org.apache.commons.math3.complex.Complex(.5-a/2).pow(n).negate().add(Math.pow(a/2+.5,n)).divide(a);}

Saved 2 bytes thanks to Original Original Original VI.

Saved 2 bytes thanks to tsh.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Not using b may save a couple bytes: n->{var a=Math.sqrt(5);return new org.apache.commons.math3.complex.Complex(1-a/2+.5).pow(n).negate().add(Math.pow(a/2+.5,n)).divide(a);} \$\endgroup\$
    – user
    Apr 7 at 19:44
  • \$\begingroup\$ @OriginalOriginalOriginalVI Good observation. \$\endgroup\$ Apr 8 at 0:11
  • 1
    \$\begingroup\$ I know nothing about this implementation, but any reason to use 1-a/2-.5 instead of .5-a/2? \$\endgroup\$
    – tsh
    Apr 8 at 3:25
  • \$\begingroup\$ @tsh Thanks. I somehow missed that. \$\endgroup\$ Apr 8 at 3:45
2
\$\begingroup\$

APL (Dyalog Extended), 23 22 bytes (SBCS)

Anonymous tacit prefix function. Complex results are returned as \$Re\$J\$Im\$.

-/s÷⍨(2÷⍨1(+,-)s←√5)*⊢

Try it online!

()*⊢ raise the following value to the power of the argument:

√5 square root of five: \$\sqrt5\$

s← store that as s and return the value: \$\sqrt5\$

1(+,-) that, added to and subtracted from one: \$1±\sqrt5\$

2÷⍨ half of that: \$1±\sqrt5\over2\$

Now we have \$\left(\frac{1±\sqrt5}2\right)^n\$

s÷⍨ divide that by s: \$\left(\frac{1±\sqrt5}2\right)^n\over\sqrt5\$

-/ the difference between them: \${\left(\frac{1+\sqrt5}2\right)^n\over\sqrt5}-{\left(\frac{1-\sqrt5}2\right)^n\over\sqrt5}\$

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

Excel, 73 bytes

=LET(q,5^0.5*((5^0.5+1)/2)^A1,a,PI()*A1,IF({1,0},q/5-COS(a)/q,-SIN(a)/q))

Using tsh's formula

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

MATLAB, 43 bytes

Try it online

p=.5+sqrt(5/4);F=@(n)(p^n-(1-p)^n)/sqrt(5);

F is an anonymous function that you plug n into.

\$\endgroup\$
1
  • \$\begingroup\$ I think the link may be incorrect (different code). Also, you can replace sqrt(5/4) by 5^.5/2, and reuse 5^.5 that to save a few bytes. Also, the ; is not necessary, because the output is the argument returned by the function, not STDOUT: tio.run/##y08uSSxL/f@/0NY0Ts/UusBWz1S7UN/… \$\endgroup\$
    – Luis Mendo
    May 6 at 18:08

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.