15
\$\begingroup\$

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.

\$\endgroup\$
15
  • 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 Apr 30 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 Apr 30 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\$ – EliteDaMyth Apr 30 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\$ – EliteDaMyth Apr 30 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\$ – EliteDaMyth Apr 30 at 10:00

12 Answers 12

9
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Your answer seems really interesting. Is there any chance you could add an explanation! \$\endgroup\$ – EliteDaMyth Apr 30 at 9:06
  • 1
    \$\begingroup\$ @EliteDaMyth I've added a commented version. Let me know if something is still unclear. \$\endgroup\$ – Arnauld Apr 30 at 9:28
  • \$\begingroup\$ Thank you! your solution is amazing, as always! \$\endgroup\$ – EliteDaMyth Apr 30 at 9:38
  • \$\begingroup\$ This is supremely neat, very nice work! \$\endgroup\$ – Etheryte Apr 30 at 23:17
6
\$\begingroup\$

Haskell, 76 75 bytes

g n=last[i|i<-[1..n],i?n==i?99]
e?n=floor$10^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=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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ using tio.run is preferable to share your code, so it can be run by others easily \$\endgroup\$ – EliteDaMyth Apr 30 at 7:59
  • \$\begingroup\$ also, instead of (''+(.5+5**.5/2))[i] you can use `${.5+5**.5/2}`[i] \$\endgroup\$ – EliteDaMyth Apr 30 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\$ – ophact Apr 30 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\$ – EliteDaMyth Apr 30 at 9:03
3
\$\begingroup\$

Desmos, 169 113 107 bytes

s=.5
p=s+s5^s
F(n)=p^n-(1-p)^n
h(k,n)=floor(10^{[1...n]}k)
f(n)=total(1-abs(sign(h(p,n)-h(F(n)/F(n-1),n))))

Try It On Desmos!

Try It On Desmos! - Prettified

Test the code on function \$f(n)\$.

As usual, Desmos is in last place :|. Probably can be golfed more though.

Brief Explanation:

s=.5: Makes a variable \$s\$ that has a value of 0.5. This variable is made solely to make the next equation shorter(literally saves only one byte, but still).

p=s+s5^s: 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,n)=floor(10^{[1...n]}k): The \$h(k,n)\$ function creates a list of length \$n\$. Then it computes \$\left\lfloor10^ik\right\rfloor\$ for each element, where \$i\$ is the index(1-based). For example, \$h(1.56789, 5)\$ returns the list \$[15,156,1567,15678,156789]\$.

f(n)=total(1-abs(sign(h(p,n)-h(F(n)/F(n-1),n)))): Returns the answer. Kind of hard to explain what I'm doing here, so I'm currently not going to add an explanation for this expression, but I might add an actual explanation here at a later time.

\$\endgroup\$
2
\$\begingroup\$

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!

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ 65 bytes by using > instead of f \$\endgroup\$ – MarcMush May 2 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. May 3 at 10:34
1
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 39 bytes

NθF²⊞υιF⊖θ⊞υΣ…⮌υ²I⊖⊖⌕EI∕⊟υ⊟υ¬⁻ι§I⊘⊕₂⁵κ⁰

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

Nθ

Input n.

F²⊞υιF⊖θ⊞υΣ…⮌υ²

Calculate the first n Fibonacci numbers.

I⊖⊖⌕EI∕⊟υ⊟υ¬⁻ι§I⊘⊕₂⁵κ⁰

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

87 bytes for arbitrary precision:

NθF²⊞υιF⊖θ⊞υΣ…⮌υ²≦Xχθ≔⁰η≔⁰ζF↨×⁵×θθ⁴«≔⁺×ζ⁴ιζ≦⊗η¿›ζ⊗η«≧⁻⊕⊗ηζ≦⊕η»»I⊖⌕EI÷×θ⊟υ⊟υ¬⁻ι§I÷⁺ηθ²κ⁰

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.

F²⊞υιF⊖θ⊞υΣ…⮌υ²

Calculate the first n Fibonacci numbers.

≦Xχθ

Compute 10ⁿ.

≔⁰η≔⁰ζF↨×⁵×θθ⁴«≔⁺×ζ⁴ιζ≦⊗η¿›ζ⊗η«≧⁻⊕⊗ηζ≦⊕η»»

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

I⊖⌕EI÷×θ⊟υ⊟υ¬⁻ι§I÷⁺ηθ²κ⁰

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.