On Periodic Points of the Order of Appearance in the Fibonacci Sequence

Abstract

Let ${\left(F_n\right)}_{n\ge 0}$ be the Fibonacci sequence. The order of appearance $z\left(n\right)$ of an integer $n\ge 1$ is defined by $z\left(n\right)=min\{k\ge 1:n\mid F_k\}$. Marques, and Somer and Křížek proved that all fixed points of the function $z\left(n\right)$ have the form $n=5^k$ or $12·5^k$. In this paper, we shall prove that $z\left(n\right)$ does not have any k-periodic points, for $k\ge 2$.

1. Introduction

The Fibonacci sequence ${\left(F_n\right)}_n$ is presumably the most classical example of a recursion sequence. This sequence is defined by the recurrence $F_n=F_{n-1}+F_{n-2}$, for $n\ge 2$, with initial terms $F_0=0$ and $F_1=1$ (see [1,2,3,4] for many surprising properties of ${\left(F_n\right)}_n$ and some generalizations of them, e.g., in [5,6,7,8,9]). The study of this sequence embraces a number of interesting aspects in Diophantine problems. For example, the “ingenuous” (and yet unproved) problem of the existence of infinitely many prime Fibonacci numbers is related to the powerful Zaremba’s conjecture in Diophantine approximation.

We point out that the function $z:{\mathbb{Z}}_{>0}\to {\mathbb{Z}}_{>0}$ (known as the order of appearance in the Fibonacci sequence) plays a pivotal role in the characterization of divisibility relations involving Fibonacci numbers. This arithmetical function is defined as

$$z\left(n\right):=min\{k\ge 1:n\mid F_k\}.$$

See

Table 1. Values of $z\left(n\right)$ for n from 1 to 50.

n	$\mathit{z}\left(\mathit{n}\right)$	n	$\mathit{z}\left(\mathit{n}\right)$	n	$\mathit{z}\left(\mathit{n}\right)$	n	$\mathit{z}\left(\mathit{n}\right)$	n	$\mathit{z}\left(\mathit{n}\right)$
1	1	11	10	21	8	31	30	41	20
2	3	12	12	22	30	32	24	42	24
3	4	13	7	23	24	33	20	43	44
4	6	14	24	24	12	34	9	44	30
5	5	15	20	25	25	35	40	45	60
6	12	16	12	26	21	36	12	46	24
7	8	17	9	27	36	37	19	47	16
8	6	18	12	28	24	38	18	48	12
9	12	19	18	29	14	39	28	49	56
10	15	20	30	30	60	40	30	50	75

for some values of $z\left(n\right)$ and Figure 1 for the graphic behavior of $z\left(n\right)$.

In 1878, Lucas [10] (see p. 300) showed that $z\left(n\right)$ is well-defined, for all $n\ge 1$. An immediate consequence of the Dirichlet’s Box Principle yields $z\left(n\right)\le {(n-1)}^2+1$. A better upper bound for $z\left(n\right)$ can be provided by combining the inequalities $z\left(n\right)\le \sigma \left(n\right)$ and $\sigma \left(n\right)\le 3.5nloglogn$, for $n\ge 4$ (this last inequality is a consequence of a result of Robin, see Théorème 2 of [11]), where $\sigma \left(n\right)$ denotes the sum of the positive divisors of n. For a prime number p, the better upper bound $z\left(p\right)\le p+1$ holds. In 1975, J. Sallé [12] found the sharpest upper bound for $z\left(n\right)$. Indeed, he proved that $z\left(n\right)\le 2n$, for all $n\ge 1$. His result is sharp, since we have infinitely many extremal cases (i.e., where the equality is valid):

$$z\left(n\right)=2n\hspace{1em}\mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}\hspace{1em}n=6·5^k,\mathrm{for}k\ge 0.$$

The order of appearance in the Fibonacci sequence became an object of much interest in 1992, when Z. H. Sun and Z. W. Sun [13] found a very close connection between the equation $z\left(n\right)=z\left(n^2\right)$ and Fermat’s Last Theorem (which was an open problem in that time).

Since $z\left({\mathbb{Z}}_{>0}\right)\subseteq {\mathbb{Z}}_{>0}$, one may realise the order of appearance z as a discrete dynamical system on ${\mathbb{Z}}_{>0}$ and ask about the periodic orbits of z for some fixed periods. Recall, that n is called a periodic point of z, if $z^k\left(n\right)=n$, for some $k\ge 0$ (Here $z^j$ is the jth iterate of z). The smallest positive integer k with this property is defined as the period of n (under z) and n is named as a k-period point of z (i.e., if $z^k\left(n\right)=n$ and $z^j\left(n\right)\ne n$, for all $j\in [1,k-1]$. Here, we utilize the usual notation $[a,b]=\{a,a+1,\dots ,b\}$, for integers $a<b$). For $k=1$, a 1-periodic point is usually denoted as a fixed point.

Marques [14] and Somer and Křížek [15] (independently) found all fixed points of $z\left(n\right)$. More precisely, they proved that

$$z\left(n\right)=n\hspace{1em}\mathrm{if}\mathrm{and}\mathrm{only}\mathrm{if}\hspace{1em}n=5^k\mathrm{or}12·5^k,\mathrm{for}k\ge 0.$$

Recently, two extensions of this result were proved. The first one by Trojovský [16] (who dealt with the equation $z\left(n\right)=n+\ell$, for $\ell \in [-9,9]$) and another by Trojovská [17] (who studied the behavior of $z\left(n\right)$ “near” its sharpest upper bound, i.e., solutions of the Diophantine equation $z\left(n\right)=2n-n/k$, where n, k are any positive integers). We refer the reader to these two papers (and references therein) to more problems involving the z-function.

A positive integer n is called a pre-periodic point (of z) if $z^k\left(n\right)$ is a periodic point. In other words, n is pre-periodic if its orbit ${\mathrm{Orb}}_z\left(n\right)$ under the order of appearance z (i.e., ${\mathrm{Orb}}_z\left(n\right):=\{z^k\left(n\right):k\ge 0\}$) is finite. For example,

-

${\mathrm{Orb}}_z\left(10\right)=\{10,15,20,30,60\}$;

-

${\mathrm{Orb}}_z\left(65\right)=\{65,35,40,30,60\}$;

-

${\mathrm{Orb}}_z\left(73\right)=\{73,37,19,18,12\}$;

-

${\mathrm{Orb}}_z\left(111\right)=\{111,76,18,12\}$;

and then $10,65$ and $73,111$ are pre-periodic points since 12 and 60 are fixed points of z (see Figure 2).

With the help of Wolfram Mathematica we searched the lengths of orbits ${\mathrm{Orb}}_z\left(n\right)$ for every n from 1 to 50,000. This experiment showed that the maximal length of the orbit was 10 and

Table 2. Total number of n’s from 1 to $\mathrm{50,000}$, which have the same value of $\#{\mathrm{Orb}}_z\left(n\right)=k$.

k	1	2	3	4	5	6	7	8	9	10
Color of points in Figure 1	red	orange	yellow	green	cyan	blue	magenta	purple	pink	brown
$\#n$	13	520	6248	17,988	16,282	6672	1796	418	53	10
$(\#n/500)\%$	0.03	1.04	12.50	35.98	32.56	13.34	3.59	0.84	0.11	0.02

summarizes how many times each length of the orbit from 1 to 10 was realized (we have included their percentage distribution in the last row).

Figure 1 and Figure 3 show graphically the relationship between n, $z\left(n\right)$ and the length of the orbit $\#{\mathrm{Orb}}_z\left(n\right)$ for each natural number less than or equal to 50,000. In Figure 1 we have drawn the points of the coordinates $[n,z(n\left)\right]$ and to show the corresponding length of orbits we have colored these points by the colors listed in Table 2, e.g., the red color corresponds to the length of the orbit equal to 1 (i.e., they are fixed points). In Figure 3 we plotted an analogous graph to Figure 1, but we used a 3D-graph to plot a set of all points of coordinates $[n,z\left(n\right),{\mathrm{Orb}}_z\left(n\right)]$, for n from 1 to 50,000.

Remark 1.

We now turn to a brief discussion of another concept which can be helpful to the understanding of the special points (periodic and pre-periodic) in discrete dynamics. A sequence ${\left(a_n\right)}_{n\ge 0}$ is called periodic if it satisfies $a_{n+p}=a_n$, for all $n\ge 0$(for a smallest integer $p>0$ which is known as the period of the sequence). A sequence ${\left(a_n\right)}_{n\ge 0}$ is called eventually periodic if it can be made periodic by deleting some finite number of terms from the beginning, i.e., if ${\left(a_n\right)}_{n\ge n_0}$ is periodic, for an $n_0\ge 0$. Let us denote by $\mathfrak{P}$ and ${\mathfrak{P}}_e$ the sets of the periodic and eventually periodic sequences, respectively (clearly, ${\mathfrak{P}}_e\subseteq \mathfrak{P})$. Since the orbit of a point (as a multiset) may be identified as an infinite sequence, then we can say that n is a periodic point (resp., pre-periodic point) if and only if ${Orb}_z\left(n\right)\in \mathfrak{P}$ (resp., ${Orb}_z\left(n\right)\in {\mathfrak{P}}_e$).

Actually, Luca and Tron [18] (see the proof of their Theorem 2.2) proved that every positive integer is a pre-periodic point of z. Actually, they proved that for any positive integer n, there exists a $k\ge 1$, such that $z^k\left(n\right)$ is a fixed point of z. Another proof for this fact is the following: if $\pi \left(n\right)$ is the Pisano period of n ($\pi \left(n\right)$ is the smallest period of the Fibonacci sequence modulo n), then $\pi \left(n\right)/z\left(n\right)\in \{1,2,4\}$ (see Theorem 7 of [19]) and so, ${\pi }^k\left(n\right)/z^k\left(n\right)\in \{2,24\}$, if $n>1$ and $k\ge 4$. Thus, by Iteration Theorem of [20], there exists an integer $k\ge 4$, such that ${\pi }^k\left(n\right)>1$ is a fixed point of $\pi$, i.e., ${\pi }^k\left(n\right)=24·5^a$, for some $a\ge 0$ (see Fixed Point Theorem] of [20]). Since ${\pi }^k\left(n\right)/z^k\left(n\right)\in \{2,24\}$, then $z^k\left(n\right)$ is either $5^a$ or $12·5^a$, as desired.

Since all pre-periodic points of z close their orbit in a fixed point, the following question arises: has the function $z\left(n\right)$ some k-periodic point, for $k>1$?

In this paper, we shall completely answer this question by proving that

Theorem 1.

All periodic points of z are fixed points. In other words, if $z^k\left(n\right)=n$, for some $k\ge 1$, then $z\left(n\right)=n$.

Remark 2.

We remark that the sets $\mathfrak{P}$ and ${\mathfrak{P}}_e$ can be written as

$$\mathfrak{P}={\bigcup }_{p\ge 1}\mathfrak{P}\left(p\right)and{\mathfrak{P}}_e={\bigcup }_{p\ge 1}{\mathfrak{P}}_e\left(p\right),$$

where $\mathfrak{P}\left(p\right)$ and ${\mathfrak{P}}_e\left(p\right)$ denote, respectively, the sets of the periodic and eventually periodic sequences with period exactly p. Now, observe that (according to Remark 1) Luca and Tron result (in [18]) can be rephrased as: if ${Orb}_z\left(n\right)\in {\mathfrak{P}}_e$, then ${Orb}_z\left(n\right)\in {\mathfrak{P}}_e\left(1\right)$. However, Theorem 1 is equivalent to the fact that: if ${Orb}_z\left(n\right)\in \mathfrak{P}$, then ${Orb}_z\left(n\right)\in \mathfrak{P}\left(1\right)$.

In brief outline, the main idea of the proof is to use a variant of the fact that $z\left(\mathrm{lcm}\right(m,n\left)\right)=\mathrm{lcm}\left(z\right(m),z(n\left)\right)$ (where $\mathrm{lcm}(·)$ denotes the least common multiple) together with some properties of $z\left(p^k\right)$ (for a prime p). Mathematica software was very useful when performing some calculations (for remaining cases).

2. Auxiliary Results

In this section, we shall present two results which will be very important tools in our proofs. Firstly, we have to recall that the p-adic valuation (the exponent of the highest power of a prime number p which divides n is called the p-adic order of n and it is denoted by ${\nu }_p\left(n\right)$, thus ${\nu }_p\left(n\right)=max\{s\ge 0:p^s\mid n\}$) of Fibonacci numbers was fully characterized by Halton [21] and Lengyel [22] (see generalizations and applications in [23,24,25]).

The first essential ingredients are related to the behavior of $z\left(n\right)$ at prime powers arguments.

Lemma 1.

We have

(i) 

(Theorem 1.1 of [26]) $z\left(2^k\right)=3·2^{k-2}$ (for $k\ge 3$), $z\left(3^k\right)=4·3^{k-1}$ (for $k\ge 1$) and $z\left(5^k\right)=5^k$ (for $k\ge 0$).

(ii) 

(Theorem 2.4 of [20]) If p is an odd prime, then

$$z\left(p^k\right)=p^{max\{k-e(p),0\}z\left(p\right)},$$

where $e\left(p\right)={\nu }_p\left(F_{z\left(p\right)}\right)\ge 1$. In particular, since $z\left(p\right)\mid p-\left(\frac{5}{p}\right)$, it holds that

$$z(p^k)divides\left(p-\left({\displaystyle \frac{5}{p}}\right)\right)p^{k-1},forallk\ge 1,$$

where, as usual, $(\frac{a}{q})$ denotes the Legendre symbol of an integer a with respect to an odd prime q.

We point out the Wall’s conjecture which states that $z\left(p^a\right)=p^{a-1}z\left(p\right)$, when $p>2$ is a prime and a a positive integer (see [27]).

The second tool is a kind of “formula” for $z\left(n\right)$ depending on $z\left(p^a\right)$ for all primes p dividing n. The proof of this fact can be found in [28].

Lemma 2.

(Theorem 3.3 of [28]) Let $n>1$ be an integer with prime factorization $n=p_1^{a_1}\cdots p_k^{a_k}$. Then

$$z\left(n\right)=lcm(z\left(p_1^{a_1}\right),\dots ,z\left(p_k^{a_k}\right)).$$

Now we are ready to deal with the proof of the theorem.

3. The Proof of The Theorem

First, let us make some considerations. For an integer n with prime factorization $n=p_1^{a_1}\cdots p_k^{a_k}$, we have, by Lemma 2, that

$$z\left(n\right)=\mathrm{lcm}(z\left(p_1^{a_1}\right),\dots ,z\left(p_k^{a_k}\right)).$$

However, in view of Lemma 1 (ii) together with the fact that $\mathrm{lcm}(m_1,\dots ,m_s)$ divides $m_1\cdots m_s$, we obtain

$$z\left(n\right)\mid p_1^{a_1-1}\cdots p_k^{a_k-1}(p_1-{\delta }_1)\cdots (p_k-{\delta }_k),$$

(1)

where, to simplify the notation, ${\delta }_j$ denotes the Legendre symbol $\left(\frac{5}{p_j}\right)$.

So, let us suppose that n is a t-periodic point, for some $t\ge 1$. Let us prove that n is a fixed point of z, i.e., $n=5^a$ or $12·5^a$, for an integer $a\ge 0$. Since $\#{\mathrm{Orb}}_z\left(n\right)=t$, then there exist distinct positive integers $n_2,n_3,\dots ,n_t$ such that

$$z\left(n\right)=n_2,z\left(n_2\right)=n_3,\dots ,z\left(n_{t-1}\right)=n_t,z\left(n_t\right)=n.$$

Now, let us write the prime factorization of $n_j$ as $n_j=p_1^{a_{1,j}}\cdots p_k^{a_{k,j}}$, for all $j\in [1,t]$, where we define $n_1:=n$ (also, with $p_1<\cdots <p_k$). By using (1), we have (by writing also $n_{t+1}:=n$) that

$$p_1^{a_{1,j+1}}\cdots p_k^{a_{k,j+1}}=n_{j+1}=z\left(n_j\right)\mid p_1^{a_{1,j}-1}\cdots p_k^{a_{k,j}-1}(p_1-{\delta }_1)\cdots (p_k-{\delta }_k),$$

for all $j\in [1,t]$. Thus,

$$p_1^{a_{1,j+1}}\cdots p_k^{a_{k,j+1}}\mid p_1^{a_{1,j}-1}\cdots p_k^{a_{k,j}-1}(p_1-{\delta }_1)\cdots (p_k-{\delta }_k).$$

By multiplying all the previous relations (i.e., for all $j\in [1,t]$) and after some straightforward computations, we arrive at

$$p_1^{s_1}\cdots p_k^{s_k}\mid p_1^{s_1-t}\cdots p_k^{s_k-t}{(p_1-{\delta }_1)}^t\cdots {(p_k-{\delta }_k)}^t,$$

where $s_j:={\sum }_{i=1}^t{a}_{j,i}$, for all $j\in [1,k]$. Thus, ${(p_1\cdots p_k)}^t$ divides ${((p_1-{\delta }_1)\cdots (p_k-{\delta }_k))}^t$ which yields

$$p_1\cdots p_k\mid (p_1-{\delta }_1)\cdots (p_k-{\delta }_k).$$

(2)

Now the proof splits into two cases:

Case $p_k\le 3$

In this case, we can write $n=2^a·3^b$. If $a\in [0,5]$ and $b\in [0,2]$, then

$$\begin{array}{ccc}\mathcal{A}\hfill & :=& \{2^a·3^b:a\in [0,5],b\in [0,2]\}\hfill \\ & =& \{1,2,3,4,6,8,9,12,16,18,24,32,36,48,72,96,144,288\}.\hfill \end{array}$$

Since for $n=2$ and $n=3$, the orbits

$${\mathrm{Orb}}_z\left(2\right)=\{2,3,4,6,12\}\mathrm{and}{\mathrm{Orb}}_z\left(3\right)=\{3,4,6,12\}$$

do not return to 2 or 3, we can consider only integers in the set $\mathcal{A}\backslash \{2,3\}$. For such an integer, we have that $z^j\left(n\right)$ is a fixed point, for all $j\ge 3$ (by using some simple Mathematica routine). So, we can consider only $k=2$. However, $z^2\left(n\right)=n$, for $n\in \mathcal{A}\backslash \{2,3\}$, only if $n=1$ or 12 which are fixed points. Thus, we may suppose that $a\ge 6$ and $b\ge 3$. In this case, we have, by Lemmas 1 and 2,

$$z\left(n\right)=\mathrm{lcm}(z\left(2^a\right),z\left(3^b\right))=\mathrm{lcm}(3·2^{a-2},4·3^{b-1})=2^{a-2}·3^{b-1}$$

and so

$$z^2\left(n\right)=\mathrm{lcm}(z\left(2^{a-2}\right),z\left(3^{b-1}\right))=\mathrm{lcm}(3·2^{a-4},4·3^{b-2})=2^{a-4}·3^{b-2},$$

where we used that $a\ge 6$ and $b\ge 3$. Note that if we proceed with this chain, we will have that ${\nu }_2\left(z^j\left(n\right)\right)$ will decrease, by Lemma 1 (ii), (in the form $a-2\ell$) if a is large. However, since $z^k\left(n\right)=n$, then, in particular, it holds that ${\nu }_2\left(z^k\left(n\right)\right)={\nu }_2\left(n\right)=a$. So, we must have $a\in [0,5]$. The same is valid for b (by using ${\nu }_3$) and so $b\in [0,2]$ which contradicts our assumption on a and b (i.e., $a\ge 6$ and $b\ge 3$).

Case $p_k>3$

If $k=1$, then, by (2), we have that $p_k\mid (p_k-{\delta }_k)$ and so $p_k\mid {\delta }_k\in \{-1,0,1\}$. This implies that $0={\delta }_k=\left(\frac{5}{p_k}\right)$ which, by definition of the Legendre symbol, yields that $p_k\mid 5$ and then $p_k=5$. For the case in which $k>1$, we have (since $p_k>3$) that $p_k>p_i+1\ge p_i-{\delta }_i$ (for all $i\in [1,k-1]$) and again, by the relation in (2), we infer that $p_k$ divides $p_k-{\delta }_k$ and so $p_k=5$ (as previously deduced). In conclusion, the largest prime factor of n is 5. Therefore, we can write $n=2^a·3^b·5^c$. Let us suppose that $a\ge 6$ and $b\ge 3$. Then, by Lemmas 1 and 2, we have

$$z\left(n\right)=\mathrm{lcm}(z\left(2^a\right),z\left(3^b\right),z\left(5^c\right))=\mathrm{lcm}(3·2^{a-2},4·3^{b-1},5^c)=2^{a-2}·3^{b-1}·5^c$$

and so

$$z^2\left(n\right)=\mathrm{lcm}(z\left(2^{a-2}\right),z\left(3^{b-1}\right),z\left(5^c\right))=\mathrm{lcm}(3·2^{a-4},4·3^{b-2},5^c)=2^{a-4}·3^{b-2}·5^c,$$

where we used that $a\ge 6$ and $b\ge 3$. Observe that as before, by continuing this process, we will infer that ${\nu }_2\left(z^j\left(n\right)\right)$ decreases, by Lemma 1 (ii), for large values of a. Since $z^k\left(n\right)=n$, then ${\nu }_2\left(z^k\left(n\right)\right)={\nu }_2\left(n\right)=a$ which yields that $a\in [0,5]$. This also holds for b (again by applying ${\nu }_3$). So, the possible solutions are in the range $a\in [0,5]$ and $b\in [0,2]$. Hence, the possible k-periodic points must belong to the set

$$\{2^a·3^b·5^c:a\in [0,5],b\in [0,2],c\ge 0\}.$$

Since we are interested in iterations of z and $z\left(5^c\right)=5^c$ (for all $c\ge 0$), then it is enough to search for periodic points of z belonging to $\mathcal{A}\backslash \{2,3\}$ and after, multiply them by $5^c$. In this case, the proof proceeds along the same lines as in the previous case. That is, only 1 and 12 are invariant. Now, by multiplying them by $5^c$, we obtain that $n=5^c$ or $12·5^c$ (that is, the fixed points of z). This completes the proof of Theorem 1.

4. Conclusions

In this paper, we study the dynamics of the order of appearance function $z\left(n\right)=min\{k\ge 1:n\mid F_k\}$. It is known that the orbit (under z) of all positive integer is finite. A recent result classifies all orbits with length 1 (loops), i.e., fixed points of $z\left(n\right)$. Namely, all the numbers with this property are of the form $5^k$ or $12·5^k$, for some integer $k\ge 0$. Thus, in this work, we study the existence of positive integers with larger closed orbits (i.e., k-periodic points of z, for $k>1$). In particular, we close the problem of the arithmetic dynamics of z, by proving that if $z^k\left(n\right)=n$, for some positive integers n and k (where $z^k$ is the kth iteration of z), then $z\left(n\right)=n$. In particular, the function z does not admit k-periodic points, for all $k>1$.