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.
Fibonacci, variation on the theme
computer arithmetic
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.