This is a question about the open problem Fibonacci divisibility from the Open Problem Garden.

The problem, originally stated in 1960 by D.D. Wall, has several equivalent formulations one of which is:

Find a prime $p$ with $p^2|a_{p-\left(\frac{p}{5}\right)}$,

where $a_n$ is the $n$-th Fibonacci number. Such primes are often called Wall-Sun-Sun primes.

However in his paper his hypothesis was that Fibonacci-wieferich primes do not exist. He stated that one might conjecture something similar to the Wieferich question, because a lack of proof otherwise. He could not prove that Fibonacci Wieferich primes do not exist. The Sun brothers later followed his open question with the Wall-Sun-Sun prime conjecture.

Since always $p|a_{p-\left(\frac{p}{5}\right)}$ Crandall, Dilcher and Pomerance assumed uniform distribution of the residues and proposed the heuristic $\log \log y -\log \log x$ for the number of such primes in the interval $[x,y]$. Several authors did computer aided searches and no such prime was found up to $9.7 \times 10^{14}$. That confuses me and therefore my question.

Q: Is the heuristic of Crandall, Dilcher and Pomerance (maybe in its patched version by Klaska) still considered state of the art? If not, are there other approaches?

Edit: For me the question is sufficiently answered. That is more that I could hope for. Thank you very much!

  • $\begingroup$ What is Klaska's patch? $\endgroup$ – Charles Sep 23 '11 at 14:07
  • 2
    $\begingroup$ $\log\log(9.7*10^{14})$ is only $3.54$, so they found about 3.5 fewer than expected - not too surprising. $\endgroup$ – Stopple Sep 23 '11 at 17:28
  • $\begingroup$ @ Charles: In a recent work Jiří Klaška (Short remark on Fibonacci-Wieferich primes, Acta Mathematica Universitatis Ostraviensis, Vol. 15 (2007), No. 1, 21--25) argues that one only has to consider primes = 1 or 9 mod 10. That modifies CDP to 1/2 log log. @ Stopple: The searches for Wolstenholme (2 known), Wieferich (2 known) and Wilosn (3 known) primes are on the spot. Just the Wall-Sun-Sun primes do not seem to fit. @quid, @Francois: Wow! Thx for checking the data. I need some time to digest that, especially your comment on the result of Klaska. $\endgroup$ – Uwe Stroinski Sep 25 '11 at 12:40

As quid mentioned, Klyve and I have done some computational investigations on Fibonacci-Wieferich/Wall-Sun-Sun primes. In particular, we collected all primes $p < 9.7\times10^{14}$ such that $F_{p-(p/5)} \equiv Ap \pmod{p^2}$ with $|A| < 2\times10^6$. I've just crunched our data for primes in the range from $6.5\times10^{14}$ to $9.5\times10^{14}$ to see if the incidence of small values of $A$ matches the Crandall–Dilcher–Pomerance heuristic. Here are the results:

$$\begin{matrix} p \in [6.5\times10^{14},7.0\times10^{14}) & : & 2112 & 2085 & 2083 & 2155 & 2170.39 \cr p \in [7.0\times10^{14},7.5\times10^{14}) & : & 1905 & 1915 & 2021 & 1953 & 2016.36 \cr p \in [7.5\times10^{14},8.0\times10^{14}) & : & 1867 & 1854 & 1781 & 1870 & 1882.50 \cr p \in [8.0\times10^{14},8.5\times10^{14}) & : & 1768 & 1779 & 1707 & 1669 & 1765.11 \cr p \in [8.5\times10^{14},9.0\times10^{14}) & : & 1598 & 1561 & 1650 & 1686 & 1661.35 \cr p \in [9.0\times10^{14},9.5\times10^{14}) & : & 1568 & 1592 & 1519 & 1556 & 1568.96 \cr \end{matrix}$$

The first four columns report the count of primes $p$ in the given interval whose corresponding $A$ values lie in the respective intervals $(-2\times10^6,-10^6)$, $(-10^6,0)$, $(0,10^6)$, and $(10^6,2\times10^6)$. The last column represents the value predicted by the Crandall–Dilcher–Pomerance heuristic (namely $10^6\log\left(\frac{\log y}{\log x}\right)$ for the interval from $x$ to $y$).

The agreement between experimental data and theoretical values is pretty good. If I understand Klaška's adjustment correctly, he proposes an expected count of roughly half that proposed by the Crandall–Dilcher–Pomerance heuristic. Thus, the data does not appear to support Klaška's modified heuristic. However, note that Klaška's argument is specifically for the special value $A = 0$, so the above data does not invalidate his proposed estimate.


A very recent paper on computations on this and related things is by Dorais and Klyve; they write that their computations (for the related Wieferich primes) are in line with a conjecture of Crandall, Dilcher, Pomerance. So, it does not appear there was much change in the general expectation and what you mention still seems to be state of the art.

Also note that Crandall, Dilcher, Pomerance were aware of inexistence up to about $10^{12}$. Now $$ \log \log (10^{15}) - \log log (10^{12}) = 0.22...$$ so that also in the larger range nothing was found does not seem to shake the heuristic of CDP too much; one would not expect to find something.

  • 2
    $\begingroup$ Thanks for mentioning our paper! I don't recall checking whether our data for Wall-Sun-Sun primes matches theoretical expectations. I will crunch the data very soon and report the results here... $\endgroup$ – François G. Dorais Sep 24 '11 at 3:06

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.