# 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 Commented Apr 7, 2021 at 0:10
– Neil
Commented Apr 7, 2021 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 Commented Apr 7, 2021 at 16:48
• @FedericoPoloni The output should be the principal root Commented Apr 8, 2021 at 12:34
• Related (as pointed out by tsh here). Commented Apr 8, 2021 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}\$$.

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

# 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
Commented Apr 7, 2021 at 5:17
• 44 bytes... Commented Apr 7, 2021 at 7:58
• ...or 41 bytes with input using complex number notation. Commented Apr 7, 2021 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 Commented Apr 7, 2021 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! Commented Apr 7, 2021 at 1:04
• Python has complex number support? What? Commented Apr 7, 2021 at 4:44
• What about .5+5**.5/2 instead of (1+5**.5)/2? Commented Apr 7, 2021 at 6:46
• @Ausername: Sure. Look into the complex type, imaginary number literals, and the standard cmath module. Commented Apr 8, 2021 at 18:38

# 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


# 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 µ) Commented Apr 7, 2021 at 0:23
• @UnrelatedString ah, I knew the chain break had to have been an unnecessary waste of bytes. thanks :D Commented Apr 7, 2021 at 0:24
• Also 11 bytes, using niladic chains :P Commented Apr 7, 2021 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 Commented Apr 7, 2021 at 0:46
• (forgot to mention this third variation) Commented Apr 7, 2021 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
Commented Apr 7, 2021 at 5:03
• $(-\phi)^{-n}$ also gets the sign of the imaginary part wrong
– att
Commented Apr 7, 2021 at 5:25
• @att thanks for the 1 byte improvement and the correction! I shouldn't look at this site late at night. Commented Apr 7, 2021 at 6:41
• @att The conjugate is a valid branch cut of Binet's formula. Commented Apr 7, 2021 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 }

# 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
Commented Apr 7, 2021 at 6:40

# Charcoal, 25 24 bytes

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


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

          ⁵                 Literal 5
₂                  Square root
⁵              Literal 5
₂               Square root
±               Negated
⟦     ⟧             Make into list
⊕                    Vectorised increment
⊘                     Vectorised halved
Ｘ                      Vectorised raised to power
Ｎ            Input as a number
∕                       Vectorised divide by
⁵          Literal 5
₂           Square root
Ｅ              ⎇μ⁻⁰λλ    Negate the second element
Σ                         Sum the elements
⭆¹                          Stringify


The version of Charcoal on TIO 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.

18 bytes using the newer version of Charcoal on ATO:

Ｉ↨∕Ｘ⊘⊕⟦±₂⁵₂⁵⟧Ｎ₂⁵±¹


Attempt This Online! Link is to verbose version of code. Explanation: The version of Charcoal on ATO can use "base -1" conversion to take the difference of a list of two complex numbers saving 5 bytes and also can directly cast a complex number to string saving a further 1 byte. (Note that the difference has the opposite sign to the TIO code so I've swapped the two list elements to compensate.)

# 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
Commented Apr 7, 2021 at 19:44
• @OriginalOriginalOriginalVI Good observation. Commented Apr 8, 2021 at 0:11
• I know nothing about this implementation, but any reason to use 1-a/2-.5 instead of .5-a/2?
– tsh
Commented Apr 8, 2021 at 3:25
• @tsh Thanks. I somehow missed that. Commented Apr 8, 2021 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/… Commented May 6, 2021 at 18:08