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$
5
  • $\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
    Commented Jul 22, 2014 at 15:16
  • $\begingroup$ Related: math.stackexchange.com/questions/872071/…. $\endgroup$
    – Dietrich Burde
    Commented Jul 22, 2014 at 15:16
  • 5
    $\begingroup$ For no particular reason, $F_{155} = 110560307156090817237632754212345$ $\endgroup$
    – NovaDenizen
    Commented Jul 22, 2014 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
    Commented Jul 22, 2014 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
    Commented Jul 23, 2014 at 13:33

2 Answers 2

Reset to default
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$
3
  • $\begingroup$ Is there an analogous result for higher powers? I'd imagine so but an argument would be neat. $\endgroup$
    – Semiclassical
    Commented Jul 22, 2014 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
    Commented Jul 22, 2014 at 16:53
  • $\begingroup$ That recurring factor of 11/32 is bizarre to me. Any idea about the cause? $\endgroup$
    – Semiclassical
    Commented Jul 23, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .