Density of "Fibonacci friends"

Question

Let $F$ be the set of all integers $n>1$ such that in the Fibonacci sequence modulo $n$, the value $0$ occurs infinitely often. What is the value of $\lim\sup_{n\to\infty}\frac{|F\cap\{0,\ldots,n\}|}{n+1}$?

Answer 1

The value $0$ always occurs infinitely often regardless of the value $n>1$. To see this, consider the mapping $L_n:\mathbb{Z}_n^2\rightarrow\mathbb{Z}_n^2$ defined by $L_n(x,y)=(y,x+y)$. Then the mapping $L_n$ is invertible. Then if we set $F_{0,n}=[0]_n,F_{1,n}=[1]_n$ and $F_{i+2,n}=F_{i+1,n}+F_{i,n}$, then $F_{i,n}$ is the $i$-th Fibonacci number modulo $n$. On the other hand, $L_n(F_{i,n},F_{i+1,n})=(F_{i+1,n},F_{i+2,n})$, so $L_n^m(F_{i,n},F_{i+1,n})=(F_{i+m,n},F_{i+m+1,n})$ for all $m\geq 0$. Since $L_n$ is invertible, there must be some $m>0$ where $([0]_n,[1]_n)=L^m_n([0]_n,[1]_n)=L^m_n(F_{0,n},F_{1,n})=(F_{m,n},F_{m+1,n})$, so $F_{m,n}=[0]_n$.

This is in contrast to the Foobonacci sequence where the function $M_n$ is not injective. Define the Foobonacci sequence $FO_{1,n}=1,FO_{2,n}=1,FO_{i+2,n}=FO_{i+1,n}*_nFO_{i,n}$ where $*_n$ is the self-distributive operation in the $n$-th Laver table. For example, in Hexadecimal ($104_{\text{hex}}=260_{\text{dec}}$), we have (according to my artificial intelligence calculations but without proof) $(FO_{1,104},\dots,FO_{7,104})=(1,1,2,3, F00...008, \mathbf{F00...00B}, 100...00)$, so we call this sequence the Foobonacci sequence.

The mapping $M_n:A_n^2\rightarrow A_n^2$ defined by $M_n(x,y)=(x*_ny,x)$ (where $A_n$ denotes the $n$-th Laver table) is not invertible, and for all $n>1$, there is no $t>2$ where $FO_{n,t}=1$, but for all $n>1$, we eventually have $FO_{n,2t+1}=2^n$ for sufficiently large $t$.