2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A strategy would be to consider the mapping of $\{F_n\}$ to the integers modulo $10^{d}$. Then the statement amounts to asking whether the mapping is surjective, since otherwise one can construct a counterexample. $\endgroup$ – Semiclassical Jul 22 '14 at 15:16
  • $\begingroup$ Related: math.stackexchange.com/questions/872071/…. $\endgroup$ – Dietrich Burde Jul 22 '14 at 15:16
  • 5
    $\begingroup$ For no particular reason, $F_{155} = 110560307156090817237632754212345$ $\endgroup$ – NovaDenizen Jul 22 '14 at 16:15
  • $\begingroup$ Given the counterexamples below, maybe the question should be modified to asking how to characterize them. (For instance, should we expect to see counterexamples modulo 10000?) $\endgroup$ – Semiclassical Jul 22 '14 at 16:39
  • 1
    $\begingroup$ It's certain that no number congruent to any of [4,6,10,12,14,18,20,22,26,28,30] mod 32 will occur in the Fibonacci series. From my data it appears that all other residues of $10^n$ are present. $\endgroup$ – NovaDenizen Jul 23 '14 at 13:33
7
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there an analogous result for higher powers? I'd imagine so but an argument would be neat. $\endgroup$ – Semiclassical Jul 22 '14 at 16:39
  • 1
    $\begingroup$ Obviously, if none are congruent to 4 or 6 modulo 8, then none are congruent to 4, 6, 12, or 14 modulo 16. It turns out none are congruent to 10 either. $\endgroup$ – NovaDenizen Jul 22 '14 at 16:53
  • $\begingroup$ That recurring factor of 11/32 is bizarre to me. Any idea about the cause? $\endgroup$ – Semiclassical Jul 23 '14 at 5:22
2
$\begingroup$

A small brute-force search is enough to find several 3 digit sequences that are not ends of a fibonnaci number. Here are a few: 004, 006, 012, 014, 020, ...

All one and two digit possibilities appear.

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