Phibonacci - Relation between Phi and Fibonacci

Question

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?

Examples

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

Input

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

\$ n >= 5\$

Output

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

Tips

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.

• Delfad0r: 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\$)?
• Delfad0r: @EliteDaMyth Thanks, although this invalidates some of the answers below, you may want to notify the authors and add n=3 as a testcase.
• user100752: @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.
• user100752: @etheryte, Please take a look at above comments, Taking in consideration this issue, we have decided n will always be more than 5.
• user100752: @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.

Answer 1

JavaScript (ES7), (削除) 77 75 69 (削除ここまで) 67 bytes

n=>(g=p=>--n>1?g(q,q+=p):(1+5**.5)/2*(m*=10)^q/p*m?0:1+g(p))(q=m=1)

Try it online!

Commented

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

• user100752: Your answer seems really interesting. Is there any chance you could add an explanation!
• Arnauld: @EliteDaMyth I've added a commented version. Let me know if something is still unclear.
• user100752: Thank you! your solution is amazing, as always!
• Etheryte: This is supremely neat, very nice work!

Answer 2

Haskell, ^{(削除) 76 (削除ここまで)} 75 bytes

g n=last[i|i<-[1..n],i?n==i?99]
e?n=floor10ドル^e*f!!n/f!!(n-1)
f=0:scanl(+)1f

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.

How?

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

e?n=floor10ドル^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.

Answer 3

APL (Dyalog Extended), (削除) 37 (削除ここまで) 32 bytes

Full program, assumes ⎕IO←0.

-5 bytes by not using dfns.fibonacci.

0⍳⍨2↓=⌿↑⍕ ̈(÷/(+/,⊃)⍣⎕⍳2),2÷⍨1+√5

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

Answer 4

Jelly, 17 bytes

,’ÆḞ÷/Ṿ=ØpṾ¤ŒɠḢ_2

Try it online!

Probably can be improved.

Explanation

,’ÆḞ÷/Ṿ=Ø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

Answer 5

JavaScript, (削除) 97 (削除ここまで) 89 bytes

n=>[...''+(f=n=>n<2?n:f(n-1)+f(n-2))(n)/f(n-1)].findIndex((e,i)=>`${.5+5**.5/2}`[i]!=e)-2

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.

• user100752: using tio.run is preferable to share your code, so it can be run by others easily
• user100752: also, instead of (''+(.5+5**.5/2))[i] you can use `${.5+5**.5/2}`[i]
• user100690: @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.
• user100752: I have updated the question, so the input will always be greater than or equal to five. you can remove the n<3?0:

Answer 6

Desmos, (削除) 169 (削除ここまで) (削除) 113 (削除ここまで) (削除) 107 (削除ここまで) (削除) 98 (削除ここまで) (削除) 97 (削除ここまで) (削除) 95 (削除ここまで) 87 bytes

pp-p~1
F(n)=p^n-(1-p)^n
h(k)=floor(10^{[1...n]}k)
f(n)=\{h(p)=h(F(n)/F(n-1)),0\}.\total

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

Explanation:

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.

Answer 7

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!

• ovs: 102 bytes
• ovs: And 88 bytes as a single function.
• Noodle9: @ovs Wow, thanks! :D

Answer 8

Julia 0.7, (削除) 68 (削除ここまで) 65 bytes

!n=φ^n-(1-φ)^n
>(n,x=1)=!n/!(n-1)*10^x÷1!=φ*10^x÷1?x-1:n>x+1

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.

• MarcMush: 65 bytes by using > instead of f
• Kirill L.: Ouch, I was so frustrated that I couldn't squeeze any savings from duplicated *10^x÷1 part, that totally missed this. Thanks!

Answer 9

Charcoal, 39 bytes

NθF2⊞υιF⊖θ⊞υΣ...⮌υ2I⊖⊖⌕EI∕⊟υ⊟υ¬−ι§I⊘⊕25κ0

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

Nθ

Input n.

F2⊞υιF⊖θ⊞υΣ...⮌υ2

Calculate the first n Fibonacci numbers.

I⊖⊖⌕EI∕⊟υ⊟υ¬−ι§I⊘⊕25κ0

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

87 bytes for arbitrary precision:

×ばつθ⊟υ⊟υ¬−ι§I÷+ηθ2κ0

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.

Nθ

Input n.

F2⊞υιF⊖θ⊞υΣ...⮌υ2

Calculate the first n Fibonacci numbers.

≦Xχθ

Compute 10n.

×ばつζ4ιζ≦⊗η¿›ζ⊗η«≧−⊕⊗ηζ≦⊕η»»

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

×ばつθ⊟υ⊟υ¬−ι§I÷+ηθ2κ0

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

Answer 10

05AB1E, 17 bytes

3LÍ+ÅfRü/`ø€ËÅγнÍ

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

Answer 11

R, 100 bytes

h=function(n,m=1,l=0,p=.5+5^.5/2)`if`(n>1,h(n-1,m+l,m),{r=m/l
while(r%/%10^-T==p%/%10^-T)T=T+1
T-1})

Try it online!

Gets the ratio of the nth and n-1th fibonacci numbers using the recursive function:
g=function(n,m=1,l=0)`if`(n,g(n-1,m+l,m),m/l)

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

Answer 12

MathGolf, 21 bytes

f∩∩k(f/░▒φ░▒^╞╞mÅ▀2ドル=

Try it online.

Explanation:

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