3
$\begingroup$

I am trying to calculate the numbers $n$ for which the $n$-th Fibonacci number $F_n$ is a multiple of $n$; that is fib(n)%n==0. Here is the best PARI code I could come up with (for the counting function).

fibmod(n)={return(lift(((Mod([1,1;1,0],n))^n)[1,2]));};
S(n)=sum(k=1,floor(n),if(fibmod(k),0,1));

With this, I can go up to 10E9 in a reasonable time.

Can you think of a more efficient implementation? For instance, I guess writing it in C, or adding multithreading, could give a significant speed improvement.

$\endgroup$
3
  • $\begingroup$ It looks like the computation of Fibonacci number $F_n$ is done from scratch with each call to fibmod. So if instead you kept two variables holding $F_{n-1}$ and $F_n$, then each iteration would only require an addition and a reduction mod $n$, with a bit of shuffling of values to keep the last two Fibonacci numbers for the next iteration. $\endgroup$ – hardmath Mar 13 '14 at 11:39
  • 1
    $\begingroup$ You are indeed right, but I'm doubtful about the memory it would require; after all, $F_{10^9}$ already has more than $2 \cdot 10^8$ decimal digits... $\endgroup$ – lookatthis Mar 20 '14 at 12:34
  • $\begingroup$ That's a valid doubt. It suggests one might benefit by doing some Fibonacci steps of modest prime lengths to sieve out the bulk of numbers to be tested. $\endgroup$ – hardmath Mar 20 '14 at 16:07
2
$\begingroup$

The first thing to say is that such numbers exist. The "trivial" cases are where $n = F(n)$, namely $n=1,5$. After that the next solution is $n=12$, and many multiples of $12$ are also solutions. We will show below that infinitely many solutions exist.

The second thing to note is that computing Fibonacci numbers $F(n)$ by the recurrence relation modulo $n$ seems inefficient. These are basically integer powers of the "golden ratio" $\tau = 1.618\ldots$ and its reciprocal, so the computation of $F(n)$ can be done in $O(\log n)$ steps, rather than $n$ (very simple, add/subtract) steps using the recurrence from scratch each time. Knowing that PARI is performing the power of a small matrix mod $n$, it seems like that this is already being taken advantage of...

A sieving idea, using the strong divisibility property of the Fibonacci numbers, seems attractive as well. There should be a lot of structure to solutions of $n|F(n)$ because $m|n \iff F(m)|F(n)$. In particular if $n|F(n)$, and $m=F(n)$, then $m|F(m)$ will be another solution provided $n \gt 5$. This shows an infinite number of solutions exist.

More generally if $m,n$ are solutions, so too will $\operatorname{lcm}(m,n)$ be a solution. I will add more details, but as an example, $5\cdot 12$ is a solution since both $5$ and $12$ are.

I will also show that by looking at prime divisors, a large amount of search space can be pruned away. The simplest case of this is that any solution divisible by $2$ or by $3$ must actually be divisible by $12$. This alone reduces the search space by a little more than half, since we need check only residues $0,1,5,7,11$ mod $12$ for possible solutions.

What we should check is the periodic divisibility of Fibonacci numbers by $n$. It turns out that for each positive integer $n$, there exists a positive integer $a(n)$ such that $n|F(m)$ if and only if $a(n)|m$. See OEIS Sequence A001177 as well as David Speyer's fine Answer (and others) to this Math.SE Question on divisibility in Fibonacci numbers.

Only every third Fibonacci number is even, $a(2)=3$, which implies that if $n$ is an even solution to $n|F(n)$, then also $3|n$, and thus $3|F(n)$. But three divides only every fourth Fibonacci number, $a(3)=4$, so even $n|F(n)$ implies $12|n$. A similar argument starting from a solution where $3|n$ would give again that $12|n$.

Now the prime divisor $5$ is a bit of a wash, because $a(5)=5$. We get no new restrictions by sieving for multiples of $5$.

If we check for larger prime divisors, we do find ever more stringent restictions. Consider a solution $n|F(n)$ such that $7|n$. Thus, since $7|F(n)$ we have also $a(7)=8$ dividing $n$. Since $56 = \operatorname{lcm}(7,8)$ divides $n$ and $F(n)$, we have $a(56)=24$ divides $n$. Taking the least common multiple once more gives us that $168|n$, and now (since $a(168)=24$) the reasoning stabilizes. Note that $168|F(168)$, the first solution divisible by $7$, and to find any solution divisible by $7$, it suffices to check $n$ which are divisible by $168$.

This suggests a scheme in which we compute (or look up) $a(p)$ for all primes $p$ under the square root of the threshold $N$ you wanted to search, e.g. $N=10^{10}$ if I understood the original problem, and we need the primes below $10^5$. We carry out the chain of reasoning for $p$ similar to the case $p=7$ above entails, and that will both find a "primitive" solution and reduce searching for solutions that are multiples of $p$ to searching multiples of what generally is a much larger number.

There is an interesting open problem in mathematics, Wall's conjecture, connected to the computation of $a(p^k)$ for prime $p$ and exponent $k \gt 1$. The search of examples has been carried out in the negative beyond $10^{16}$, which allows us for computational purposes to assume $a(p^k) = p^{k-1} a(p)$. For example, $a(5^k) = 5^{k-1} a(5) = a(5)$ (this is known to be true).

Armed with these insights we should be able to make sense of the families of solutions that appear in our search. For example, if $n|F(n)$ is a solution, and $k$ is any factor of $F(n)/n$, then $kn$ will also be a solution. By "primitive" solutions earlier I meant solutions, such as $12$ and $168$ that do not arise in this fashion, e.g. there is no solution $n$ dividing $12$ (resp. $168$) such that $12/n$ is a factor of $F(n)/n$ (mutatus mutandi for $168$). The search can be refined in this way to a search only for primitive solutions, and it would be interesting to know their frequency.

$\endgroup$
6
  • $\begingroup$ I already gave it a shot, and I proved some theoretical results in this direction (there's actually quite a bit more to it!). However, I dismissed that approach quite soon because it all essentially boils down to calculating $a(p)$ for primes $p$, and, besides the fact that it is a divisor of $p \pm 1$, it behaves quite randomly. But after all the primes have density $0$, so in the long run it could be more efficient... I can't estimate the complexity of this approach at first sight. $\endgroup$ – lookatthis Mar 25 '14 at 8:08
  • $\begingroup$ I thought about the approach you outlined in your answer. While it is indeed faster by some constant factor, it requires a tremendous amount of memory to store the values of $a(p)$ for the primes (else one would have to recalculate them, losing the gain in efficiency). In other words, either one stores the relevant information (the $a(p)$'s), occupying several GBs, or calculates it from scratch every time. Am I correct? $\endgroup$ – lookatthis Mar 25 '14 at 22:37
  • $\begingroup$ I suspect we don't need to store a lot of $a(p)$ values to get a benefit in sieving, but you've done more computations than I have. How does the number of solutions between $10^N$ and $10^{N+1}$ seem to behave as $N$ grows? $\endgroup$ – hardmath Mar 25 '14 at 22:49
  • $\begingroup$ Here is what I could calculate with PARI: if $A(x)$ is the number of $n \leq x$ for which $n|F_n$, this list $\log A(e^x)/x$ for increasing values of $x$. $\endgroup$ – lookatthis Mar 26 '14 at 7:53
  • $\begingroup$ n C(exp(n)) 1 0.000000000 2 0.346573590 3 0.366204096 4 0.486477537 5 0.527811465 6 0.536479304 7 0.550021085 8 0.562476208 9 0.571295950 10 0.575574221 11 0.579856925 12 0.581982497 13 0.583872841 14 0.584866672 15 0.585875729 16 0.586202431 17 0.586400412 18 0.586293527 19 0.586121587 20 0.585780252 21 0.585366656 22 0.584919876 23 0.584414392 24 0.583888739 $\endgroup$ – lookatthis Mar 26 '14 at 7:54

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.