fibonacci-numbersnumber theory
Related to this question:
For any given sequence of digits, does a Fibonacci number exist ending with such sequence?
If not, it would be nice to find the smallest counterexample. (in other words, for example, showing that no Fibonacci number ends in, let's say, 12345)
I tried several approaches (like in answers to the linked question), but none of them worked.
My guess is to pick $a(n-1)$ so that $a(n)/a(n-1)$ is close to the Fibonacci ratio.
You can actually use the formula $\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}$ where $\varphi = \frac{1 + \sqrt{5}}{2}$. But for all non integer values you get complex numbers. These numbers are of the form $a + bi$ where a and b are the numbers you're famillar with, and $i$ is a constant defined as $i^2 = -1$ or equivalently $i = \sqrt{-1}$.
You can plot this function:
When you look at the plot, you can see the red line which is the imaginary part of the number, and the imaginary part is zero at all of the integer values, which makes sense since the fibonacci numbers aren't imaginary.
Edit: You can avoid complex numbers by using another formula.
$$\frac{\varphi^x - \cos(\pi x)\varphi^{-x}}{\sqrt{5}}$$
When you plot this function, you get:
Best Answer
No fibonacci number is congruent to 4 or 6 modulo 8. They cycle [0,1,1,2,3,5,0,5,5,2,7,1] . So modulo 1000 there are numbers you can't reach.
More info:
$$\begin{align} \text{modulus} && \text{Fibonacci period} && \text{# of missing residues} \\ 2 && 3 && 0\\ 2^2 && 6 && 0\\ 2^3 && 12 && 2\\ 2^5 && 48 && 11 = 2^5 \cdot \frac{11}{32}\\ 2^8 && 3 \cdot 2^7 && 88 = 2^8 \cdot \frac{11}{32} \\ 2^{15} && 3 \cdot 2^{14} && 5637 = 2^{15} \cdot \frac{11}{32} \\ 2^{16} && 3 \cdot 2^{15} && 11264 = 2^{16}\cdot \frac{11}{32} \\ 2^{20} && 3 \cdot 2^{19} && 360448 = 2^{20} \cdot \frac{11}{32} \\ 5 && 20 && 0 \\ 5^2 && 100 && 0 \\ 5^3 && 500 && 0 \\ 5^4 && 2500 && 0 \\ 10 && 60 && 0 \\ 10^2 && 300 && 0 \\ 10^3 && 1500 && 250 \\ 10^4 && 15000 && 3125 = 10^4 \cdot \frac{5}{16}\\ 10^5 && 150000 && 34375 = 10^5 \cdot \frac{11}{32}\\ 10^6 && 1500000 && 343750 = 10^6 \cdot \frac{11}{32}\\ \end{align}$$
Conjectures:
Modulo $2^n$, the period is $3 \cdot 2^{n-1}$. For $n \ge 5$, exactly $\frac{11}{32}$ of the residues will not be present in the cycle.
Modulo $5^n$, the period is $4 \cdot 5^n$. All residues are present.
Modulo $10^n$, for $n \ge 3$, the period is $15 \cdot 10^{n-1}$. For $n \ge 5$, exactly $\frac{11}{32}$ of the residues will be missing.