You want to see how quickly the ratio of two consecutive Fibonacci numbers converges on φ.

Phi, known by the nickname "the golden ratio" and written as \$φ\$, is an irrational number, almost as popular as π and e. The exact value of \$φ\$ is \$\frac {1 + \sqrt 5} 2 = 1.618...\$

The Fibonacci sequence is a recursive series of integers calculated by

$$F_n = F_{n-1} + F_{n-2} \\ F_0 = 0 \\ F_1 = 1$$

Calculate \$φ\$'s value and the ratio \$\frac {F_n} {F_{n-1}}\$. How closely does \$φ\$ match the ratio?


\$n = 2\$, ratio: \$\frac 1 1 = 1.000\$, compared to \$1.618...\$, 0 decimal spots match

\$n = 5\$, ratio: \$\frac 5 3 = 1.666...\$, compared to \$1.618...\$, 1 decimal spot matches


1 integer \$n\$ to calculate \$\frac{F_n}{F_{n-1}}\$

\$ n >= 5\$


1 integer \$x\$, indicating the number of decimal places that match the value of \$φ\$

It is acceptable that the program only works accurately until the float precision limit of the language.

Test Cases

Input -> Output

5 -> 1
10 -> 2
12 -> 2
15 -> 5
20 -> 7
23 -> 7
25 -> 9
50 -> 18
100 -> 39


Do not round the ratio of \$\frac{F_n}{F_{n-1}}\$

Rounding will give you errors.

Let's look at \$n = 5\$ again.

\$1.666...\$ rounds to \$1.7\$ and \$1.618...\$ rounds to \$1.6\$, so 0 is the wrong answer.

Useful information and math.

The limit of the ratios of the consecutive Fibonacci terms as \$n\$ tends to infinity is the golden number \$φ\$. The inverse of this ratio is \$\frac 1 φ\$ which equals to \$φ−1\$.

\$\frac 1 φ = φ -1 \$

\$ \lim_{n \to \infty} \frac{F_n}{F_{n-1}} = φ\$

Winning criterion

Code Golf.

  • 4
    \$\begingroup\$ What is the expected return value for, say, \$n=3\$, where the ratio doesn't even match the digit before the decimal point (\$F_3/F_2=2.0\$)? \$\endgroup\$
    – Delfad0r
    Commented Apr 30, 2021 at 8:46
  • 1
    \$\begingroup\$ @EliteDaMyth Thanks, although this invalidates some of the answers below, you may want to notify the authors and add n=3 as a testcase. \$\endgroup\$
    – Delfad0r
    Commented Apr 30, 2021 at 8:58
  • 2
    \$\begingroup\$ @Delfad0r thanks for the heads up! Now, thinking about it, it would be better for everyone if we said, you wont be given inputs under 5. Will save everyone from updating their answers. \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 9:01
  • 3
    \$\begingroup\$ @etheryte, Please take a look at above comments, Taking in consideration this issue, we have decided n will always be more than 5. \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 9:43
  • 2
    \$\begingroup\$ @etheryte, I think there was a misunderstanding, for n=13, the fibonacci ratio is 1.61805555...... The golden ratio is 1.6180399.... Comparing these two numbers, we find that the digits 6180 are common, i.e. the first four decimal places match, hence the answer would be 4. \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 10:00

12 Answers 12


JavaScript (ES7),  77 75 69  67 bytes


Try it online!


n => (            // main function, taking n
  g = p =>        // g is a recursive function taking p which, along with q,
                  // is used to compute the Fibonacci sequence
  --n > 1 ?       // decrement n; if it's still greater than 1:
    g(q, q += p)  //   do a recursive call with (p, q) = (q, q + p)
  :               // else:
    (1 + 5 ** .5) //   compute the golden ratio
    / 2           //
    * (m *= 10)   //   multiply m by 10 and multiply the golden ratio by m
    ^             //   xor (forces the decimal places to be discarded)
    q / p         //   compute q / p (last Fibonacci term / penultimate one)
    * m           //   multiply by m
    ?             //   if the above values are not equal:
      0           //     stop
    :             //   else:
      1 + g(p)    //     increment the final result and do a recursive call
)(q = m = 1)      // initial call to g with p = q = m = 1
  • 1
    \$\begingroup\$ Your answer seems really interesting. Is there any chance you could add an explanation! \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 9:06
  • 1
    \$\begingroup\$ @EliteDaMyth I've added a commented version. Let me know if something is still unclear. \$\endgroup\$
    – Arnauld
    Commented Apr 30, 2021 at 9:28
  • \$\begingroup\$ Thank you! your solution is amazing, as always! \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 9:38
  • \$\begingroup\$ This is supremely neat, very nice work! \$\endgroup\$
    – Etheryte
    Commented Apr 30, 2021 at 23:17

Haskell, 76 75 bytes

g n=last[i|i<-[1..n],i?n==i?99]

Try it online!

The relevant function is g, which takes n as input and returns the number of matching decimal digits between \$\varphi\$ and \$F_n/F_{n-1}\$. It probably won't work if the answer is larger than 15 because that's the maximum precision allowed by Doubles.


f=0:scanl(+)1f is the standard Haskell definition of the Fibonacci numbers.

e?n=floor$10^e*f!!n/f!!(n-1) is a function (?) which computes $$ \left\lfloor10^e\cdot\frac{F_n}{F_{n-1}}\right\rfloor. $$

g n=last[i|i<-[1..n],i?n==i?99] finds the largest exponent i such that $$ \left\lfloor10^i\cdot\frac{F_n}{F_{n-1}}\right\rfloor=\left\lfloor 10^i\varphi\right\rfloor. $$ Note that \$\varphi\$ is computed as \$F_{99}/F_{98}\$ to save bytes, since the error is far beyond the accuracy of Doubles. Also, the fact that the answer will always be smaller than n is exploited.


APL (Dyalog Extended), 37 32 bytes

Full program, assumes ⎕IO←0.

-5 bytes by not using dfns.fibonacci.


Try it online!

(+/,⊃)⍣⎕⍳2 calculates adjacent fibonacci pairs. Starting with 0 1 ≡ ⍳2, iterate input () times: pair the sum of both values +/ with the first value .

2÷⍨1+√5            ⍝ Phi
,                  ⍝ paired with 
÷/(+/,⊃)⍣⎕⍳2       ⍝ fib(n) ÷ fib(n-1)
↑⍕¨                ⍝ format both numbers as strings and arrange in character matrix
=⌿                 ⍝ reduce each column by equality
2↓                 ⍝ remove the first two values (first digit and decimal point)
0⍳⍨                ⍝ get the index of 0 in this list
                   ⍝ this is the first index where Phi and fib(n-0) ÷ fib(n-1) differ

Jelly, 17 bytes


Try it online!

Probably can be improved.


,’ÆḞ÷/Ṿ=ØpṾ¤ŒɠḢ_2   Main monadic link
,                   Pair with
 ’                    n-1
  ÆḞ                Get the Fibonacci numbers
     /              Reduce by
    ÷                 division
      Ṿ             Convert to string
       =            Equals [vectorized]
           ¤         (
        Øp            Phi
          Ṿ           Convert to string
           ¤         )
            Œɠ      Run lengths
              Ḣ     First element
               _    Subtract
                2     2

Desmos, 169 113 107 98 97 95 87 bytes


Try It On Desmos!

Try It On Desmos! - Prettified

Finally managed to get it under 100 90 bytes after all this time!

I don't know why I keep coming back to this answer, but every time I do, I always find a way to golf it even further...

Test the code on function \$f(n)\$. It only works up to around \$n=25\$, though, because of float precision errors. Uses the fact that the output has to be smaller than \$n\$.

(The f(n)=\{h(p)=h(F(n)/F(n-1)),0\}.\total equation does not render properly in Desmos, in case you are wondering. It still works though.)


pp-p~1: Sets p to be the golden ratio.

F(n)=p^n-(1-p)^n: \$F(n)\$ is Binet's formula for the \$n\$th Fibonacci number, but with the \$\sqrt5\$ denominator taken out, because it gets cancelled out anyways in \$\frac{F(n)}{F(n-1)}\$.

h(k)=floor(10^{[1...n]}k): The \$h(k)\$ function creates a list of length \$n\$. It then computes \$\left\lfloor10^ik\right\rfloor\$ for each element, where \$i\$ is the index(1-based). Also, the \$n\$ in [1...n] is referring to the argument passed into \$f(n)\$(which is the next equation). For example, \$h(1.56789)\$ with \$n=5\$ returns the list \$[15,156,1567,15678,156789]\$.

f(n)=\{h(p)=h(F(n)/F(n-1)),0\}.\total: This function \$f(n)\$ essentially compares each digit of \$p\$ and \$\frac{F(n)}{F(n-1)}\$ under the \$h\$ function. If you look at the \$h\$ function, you will see that at any index \$1\le i\le n\$, it is actually comparing every digit up to the \$i\$'th decimal place. For example, let's say you were comparing \$1.56789\$ and \$1.56889\$, with \$n=5\$. \$h(1.56789)=[15,156,1567,15678,156789]\$, and \$h(1.56889)=[15,156,1568,15688,156889]\$.
From this, you can tell that the first \$2\$ elements(\$15\$ and \$156\$) of each of the lists are the same, but once you get to the digit that is different, the rest of the elements are not equal.
With this information, we can then combine the two lists into one, by doing the following: If the element at index \$1\le i\le n\$ in each list are the same, then the \$i\$'th element of the new list is \$1\$. Otherwise, it is \$0\$. (This is what \{h(p)=h(F(n)/F(n-1)),0\} does)
We can then simply take the sum of this new list to obtain the answer.


JavaScript, 97 89 bytes


You have got to be kidding me. Not the best answer definitely but uses a different approach.

Also, try it online.

8 bytes were shaved off the program thanks to suggestions from the OP as well as a rule change.

  • \$\begingroup\$ using tio.run is preferable to share your code, so it can be run by others easily \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 7:59
  • \$\begingroup\$ also, instead of (''+(.5+5**.5/2))[i] you can use `${.5+5**.5/2}`[i] \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 8:00
  • 1
    \$\begingroup\$ @EliteDaMyth thanks! I'm in a hurry at the moment so I can't update my answer but I'll take your suggestions into account soon. \$\endgroup\$
    – user100690
    Commented Apr 30, 2021 at 8:01
  • \$\begingroup\$ I have updated the question, so the input will always be greater than or equal to five. you can remove the n<3?0: \$\endgroup\$
    – user100752
    Commented Apr 30, 2021 at 9:03

Python 3, 120 102 88 bytes

Saved a whopping 18 32 bytes thanks to ovs!!!

f=lambda n,r=1,a=0,b=1:n>1and f(n-1,r,b,a+b)or-((1+5**.5)*r//2!=b*r//a or~f(n,r*10,a,b))

Try it online!

  • 1
    \$\begingroup\$ 102 bytes \$\endgroup\$
    – ovs
    Commented Apr 30, 2021 at 17:34
  • 1
    \$\begingroup\$ And 88 bytes as a single function. \$\endgroup\$
    – ovs
    Commented Apr 30, 2021 at 17:42
  • \$\begingroup\$ @ovs Wow, thanks! :D \$\endgroup\$
    – Noodle9
    Commented Apr 30, 2021 at 19:21

Julia 0.7, 68 65 bytes


Try it online!

Fibonacci numbers are calculated using Binet's formula dropping the constant \$\sqrt5\$ term in the denominator since we are interested in ratios anyway.

Thanks to MarcMush for -3 bytes.

  • \$\begingroup\$ 65 bytes by using > instead of f \$\endgroup\$
    – MarcMush
    Commented May 2, 2021 at 12:41
  • \$\begingroup\$ Ouch, I was so frustrated that I couldn't squeeze any savings from duplicated *10^x÷1 part, that totally missed this. Thanks! \$\endgroup\$
    – Kirill L.
    Commented May 3, 2021 at 10:34

Charcoal, 39 bytes


Try it online! Only works up to n=40 due to floating-point rounding. Explanation:


Input n.


Calculate the first n Fibonacci numbers.


Divide the last two and compare the string representation with that of φ.

87 bytes for arbitrary precision:


Try it online! Link is to verbose version of code. Explanation: Uses @Delfad0r's observation that the result is always less than n so that you need only compute n decimal places.


Input n.


Calculate the first n Fibonacci numbers.


Compute 10ⁿ.


Calculate ⌊√5·10²ⁿ⌋ using the method from my answer to Shift right by half a bit.


Calculate the Fibonacci ratio multiplied by 10ⁿ and compare it with the digits of φ·10ⁿ calculated from the above value.


05AB1E, 17 bytes


Try it online!

3L    push the list [1,2,3]
Í     subtract 2, [-1,0,1]
+     add to the implicit input, [9, 10, 11]
Åf    take the nth Fibonacci number, [34, 55, 89]
R     reverse, [89, 55, 34]
ü/    take the division of each pair, [1.6181818181818182, 1.6176470588235294]
`     dump to stack
ø     zip, ["11", "..", "66", "11", "87", "16", "84", "17", "80", "15", "88", "18", "82", "13", "85", "12", "89", "24"]
€Ë    map to equal, [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
Åγ    run length encode, [4, 6, 1, 7]
нÍ    head - 2, 2

R, 100 bytes


Try it online!

Gets the ratio of the nth and n-1th fibonacci numbers using the recursive function:

Then calculates the number of digits of the ratio that are shared with phi by comparing successive integer divisions by negative powers of 10:
(so T ends-up with the number of shared digits +1)


MathGolf, 21 bytes


Try it online.


f          # Get the n'th Fibonacci number using the (implicit) input-integer `n`
 ∩∩        # Convert it to a float (by changing `F(n)` to `1/1/F(n)`..)
   k       # Push the input-integer again
    (      # Decrease it by 1
     f     # Get the n-1'th Fibonacci number as well
      /    # Divide the F(n) by F(n-1)
       ░▒  # Convert it to a string, and then a list of characters
           # (float directly to character-list isn't possible yet unfortunately)
φ          # Push the golden ratio constant (1.618033988749895)
 ░▒        # And convert it to a list of characters as well
   ^       # Zip the two lists together to create pairs
    ╞╞     # Remove the first two pairs (leading "1.")
m          # Map over each remaining pair,
 Å         # using the following 2 commands:
  ▀        #  Uniquify the pair
   £       #  And pop and push its length
    2=     # Then get the first (0-based) index of a 2 in this list
           # (after which the entire stack is output implicitly as result)

The /░▒φ░▒^ could alternatively be /░φ░^2/ for the same byte-count, where the zip will create a single string and we split it into pairs with 2/.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.