# Complex Fibonacci numbers

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).

• Brownie points for beating my 11 byte Jelly answer – caird coinheringaahing Apr 7 at 0:10
• Relevant: youtube.com/watch?v=ghxQA3vvhsk – Neil Apr 7 at 10:40
• @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 – pxeger Apr 7 at 16:48
• @FedericoPoloni The output should be the principal root – caird coinheringaahing Apr 8 at 12:34
• Related (as pointed out by tsh here). – Arnauld Apr 8 at 13:23

# 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}\$$.

# R, 6057 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!

• 46 bytes (Also, you didn't update the TIO link) – att Apr 7 at 5:17
• 44 bytes... – Dominic van Essen Apr 7 at 7:58
• ...or 41 bytes with input using complex number notation. – Dominic van Essen Apr 7 at 7:59

# 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

• 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 – Level River St Apr 7 at 1:02
• @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! – hyper-neutrino Apr 7 at 1:04
• Python has complex number support? What? – A username Apr 7 at 4:44
• What about .5+5**.5/2 instead of (1+5**.5)/2? – dingledooper Apr 7 at 6:46
• @Ausername: Sure. Look into the complex type, imaginary number literals, and the standard cmath module. – David Foerster Apr 8 at 18:38

# 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.

• Can save another byte with q**-x instead of --q**x – att Apr 7 at 6:40

# 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...

# MATL, 15 bytes

17Lt_Qwhi^d5X^/


### 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


# Charcoal, 25 bytes

⭆¹ΣＥ∕Ｘ⊘⊕×⟦¹±¹⟧₂⁵Ｎ₂⁵⎇μ⁻⁰λλ


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
Ｘ                      Vectorised raised to power
Ｎ           Input as a number
∕                       Vectorised divide by
₂          Square root of
⁵         Literal 5
Ｅ               ⎇μ⁻⁰λλ   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.

# 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

• I was about to post this myself, but -1 if you just move the I to the end (no need for µ) – Unrelated String Apr 7 at 0:23
• @UnrelatedString ah, I knew the chain break had to have been an unnecessary waste of bytes. thanks :D – hyper-neutrino Apr 7 at 0:24
• Also 11 bytes, using niladic chains :P – caird coinheringaahing Apr 7 at 0:25
• Also also 11 bytes. Note that IN could just as well be _/, and the N could also go before the ¤. Smells vaguely like golfing potential – Unrelated String Apr 7 at 0:46
• (forgot to mention this third variation) – Unrelated String Apr 7 at 0:47

# 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/ϕ

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

# 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 }

# J, 25 bytes

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


Try it online!

# Java + Apache Commons Math, 138136 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.

• 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);} – user Apr 7 at 19:44
• @OriginalOriginalOriginalVI Good observation. – Unmitigated Apr 8 at 0:11
• I know nothing about this implementation, but any reason to use 1-a/2-.5 instead of .5-a/2? – tsh Apr 8 at 3:25
• @tsh Thanks. I somehow missed that. – Unmitigated Apr 8 at 3:45

# 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}\$$

# 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

# 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.

• 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/… – Luis Mendo May 6 at 18:08