This can't be a coincidence

Number Theory Level 5

$\begin{aligned} 0. && 00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00005 \quad 00008 \\ && 00013 \quad 00021 \quad 00034 \quad 00055 \quad 00089\quad 00144\quad \ldots \\ \end{aligned}$

The above shows the first few digits (actually 65) of the decimal representation of the fraction $\large \frac1{9,999,899,999}.$ If we split the digits into partitions of 5, we can see that the numbers form a Fibonacci sequence: $0,1,1,2,3,5,8,13,\ldots$ . How many positive Fibonacci numbers can we find before the pattern breaks off?

Note: For example, suppose that the fraction equals $0.00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00009 \ldots$ instead of the one given at the top. Then you could only find the first five Fibonacci numbers, namely $0,1,1,2,3$ . So your answer would then be that there are 4 positive Fibonacci numbers before the pattern breaks off.

Bonus : Generalize this.
Try Daniel Liu's problem that was inspired by this problem.

The answer is 24.

1 solution

Daniel Liu
Jun 29, 2015

Let $F(x)=\dfrac{x}{1-x-x^2}$ . Then $\dfrac{1}{100000}F\left(\dfrac{1}{100000}\right)=\dfrac{1}{9999899999}$

But note that $F(x)$ is the generating function of the Fibonacci numbers, so $F(x)=x+x^2+2x^3+3x^4+5x^5+\cdots$ So $\dfrac{1}{9999899999}=\dfrac{1}{100000}F\left(\dfrac{1}{100000}\right)=0.00000 00001 00001 00002\cdots$ and so on, generating all the Fibonacci numbers to infinity. At least, that would be the case if there wasn't a finite amount of space for the Fibonacci numbers: the fact that we used $x=\dfrac{1}{100000}$ means that there is only five digits of space for each Fibonacci number. We find that the first Fibonacci number with six digits is $F_{26}=121393$ which will bring a carry to $F_{25}$ , making it one more than the actual Fibonacci number. Since $F_{25} < 99999$ , we are sure that there are no carries, so $F_{24}$ is the last Fibonacci number in the pattern.

Thus, the answer is $\boxed{24}$ .

As a separate example, look at the smaller root of $1000000x^2-1000000x+1$ Notice anything unusual?

Daniel Liu - 5 years, 11 months ago

WHAAAAAAAAAAAAAAAAAAT?! How's that possible? Let me get my thinking cap on.

Pi Han Goh - 5 years, 11 months ago

Catalan??? No! It can't be.

Pi Han Goh - 5 years, 11 months ago

@Pi Han Goh – Yup, I see it now. A generating function by (this one is left as an exercise for the reader)! Nice One Daniel!

Pi Han Goh - 5 years, 11 months ago

@Pi Han Goh – Added the last line in my problem statement! ^_^

Pi Han Goh - 5 years, 11 months ago

I cant observe anything . Please tell me what is there.

Sahil Jain - 4 years, 3 months ago

Check the solutions to the problem here: https://brilliant.org/problems/is-this-a-coincidence-too/

Daniel Liu - 4 years, 3 months ago

@Pi Han Goh This problem has led to too many coincidence problems on brilliant. Interesting!

Nihar Mahajan - 5 years, 11 months ago

This can't be a coincidence

The answer is 24.

1 solution

0 pending reports