Complex Fibonacci numbers

Question

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 code-golf, 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).

Answer 1

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

Answer 2

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

Answer 3

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!

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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 }

Answer 9

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!

• -1 byte by Arnauld
• -1 byte by att

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.

Answer 10

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

Answer 11

J, 25 bytes

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

Try it online!

Answer 12

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.

Answer 13

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

Answer 14

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

Answer 15

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.