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\$ – Recursive Co. 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 98 97 95 bytes

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

Try It On Desmos!

Try It On Desmos! - Prettified

Finally managed to get it under 100 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)=\total(\{h(p)=h(F(n)/F(n-1)),0\}) equation does not render properly in Desmos, in case you are wondering. It still works though.)

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 only saves one byte, but it's code golf :P).

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)=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)=\total(\{h(p)=h(F(n)/F(n-1)),0\}): 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)):1,0\} does)
We can then simply take the sum of this new list to obtain the answer.

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