1
$\begingroup$

I don't know what happended to this website but for months I am not able to connect me in it. As I understand it the website is closed. It is in this website I found this problem.


Let $L$ be the function which give the number of digits of a number. Let F(n) be the n-th Fiboncci number with $F(0)=F(1)=1$.

What is $$L\left[\prod_{k=0}^{2000} L\left(F\left(2^k\right)\right)\right]$$ ?


I know how to compute the number of digits of a number like $$L(n)=E\left(\log_{10}(n)\right)+1$$ where $E$ is the floor function.

I also know how to compute Fibonacci numbers but my method is not very good when I am out of the first millions of Fibonacci numbers and I also don't know how I should find for example $F(2^{100})$

Here is my program in Python 3.0

def fib(n):
    a,b,c=1,1,1
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        while c<n-2:
            a,b,c=b,a+b,c+1
        return a+b

I also know that I can use this to compute them :

$$\begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\cdot\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix}$$

But I don't know how to compute the golden ratio enough to get my Fibonacci numbers.

In the problem they mention the number was so big we needed to find only the first six and the end six digit of this number.

So my question is, does exist other things that I don't know in maths and that may help me or should I ask my question in https://stackoverflow.com/?

Thank you in advance !

$\endgroup$
1
$\begingroup$

Here's one way to start: Binet's Formula for the Fibonacci numbers is $$F_n = {1\over \sqrt5}\left[ \left(1+\sqrt 5\over2 \right)^{n-1} - \left(1-\sqrt 5\over2 \right)^{n-1}\right]$$ Note that $\displaystyle\left(1+\sqrt 5\over2 \right)^{n-1} < {1\over2}$ when $n\ge 0$, so you can use the approximation $$F_n \approx {1\over \sqrt5}\cdot \left(1+\sqrt 5\over2 \right)^{n-1}. $$ (You are not changing the number of digits of the Fibonacci number by changing it by less than 1; $F_n$ is never a power of $10$.) (Well, other than $1$; you should handle that case separately.) Then $$\log_{10} F(2^n) = \log_{10} \left[{1\over \sqrt5}\cdot \left(1+\sqrt 5\over2 \right)^{2^n-1}\right]= \log_{10} {1\over \sqrt5} + (2^n-1)\log_{10}\left(1+\sqrt 5\over2 \right).$$ And then it gets icky again.

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