Does this sequence always terminate or enter a cycle?

I've been fiddling with the recursive sequence defined as follows:

$$\begin{equation} f_n=\begin{cases} a, & n=1.\\ b, & n=2.\\ c, & n=3.\\ f_{n-1}f_{n-2}f_{n-3} \mod[f_{n-1}+f_{n-2}+f_{n-3}], & n>3. \end{cases} \end{equation}$$

And no matter my initial choices of positive integers $a,b,c$, it seems $ \{ f_n \}$ always terminates (three consecutive zeros) or enters a cycle. For instance, if $a=12,b=12,c=9$, then the sequence becomes $12,12,9, 9,12,$ $12\dots$

My question: can we prove (or disprove) that for any positive integers $a,b,c$, the sequence $\{ f_n\}$ will always terminate (three consecutive zeros) or enter a cycle?

More important remarks in quotes.

(Dec. 27) Remark 1.1: it appears (though I have not proved it) that my conjecture is true for the simpler recursive sequence

$$\begin{equation} f_n=\begin{cases} a, & n=1.\\ b, & n=2.\\ f_{n-1}f_{n-2} \mod[f_{n-1}+f_{n-2}], & n>2. \end{cases} \end{equation}$$

Perhaps this would be a better starting point. Hereafter, I will only be referring to the above.

(Dec. 28) Remark 1.2: If $f_n=f_{n-1}$ and is odd, then $f_k=f_n$ for all $k>n$. If $f_n=f_{n-1}$ and is even, the sequence will terminate. This can be proven simply enough.

(Dec. 28) Remark 1.3: I conjecture that if $a$ is odd and $b>a+1$ is even, the sequence always terminates. Also, if $a$ is even and $b>a+1$ is odd, the sequence never terminates.

(Dec. 28) Remark 1.4: the sequence reaches the cycle $\dots 5,7,11,5,7,11\dots$ for many choices of $a,b.$ Some pairs $(a,b)$ for which $f_n$ enters the cycle $\dots 5,7,11 \dots$ are $(3,5), (5,7), (7,11),$ $(7,3),(35,11),(44,13).$ There are probably infinitely many pairs $(a,b)$ for which this occurs. The frequency with which I see $5,7,11$ is probably due to my relatively small choices of integers. I wonder what the minimum of $X+Y+Z > 3$ is, where $X,Y,Z$ is a cycle eventually reached by the function.

I wonder further if there are arbitrarily long sequences of numbers which this recurrence relation would cycle through for certain initial $a,b$. I have not found any cycles longer than three terms, though $5,7,11$ is not the only three-term cycle I have found. For $(a,b) = (7,111111101)$, the sequence eventually reaches the cycle $8496495, 3641355, 6068925$. If we have $(a,b) = (6, 99)$, the sequence reaches a different length-$3$ cycle.

(Dec. 28) Remark 1.5: almost always, it seems that when $f_n$ does not terminate, the repeated terms are multiples of $5$. Some exceptions are $\{ f_n \}^{(9,66)}$, $\{ f_n \}^{(6,99)}$, and $\{ f_n \}^{(3,11)}$, where $\{ f_n \}^{(x,y)}$ is the sequence generated for $a=x,b=y$.

(Dec. 28) Remark 1.6: I conjecture $5,7,11$ are the only primes that appear in a distinct cycle (see Def. 1.1). In fact, it may even be the case that $5,7,11$ is the only distinct cycle with primes.

(Dec. 29) Remark 1.7: I should probably state what the 'cycles' I am talking about are.

Definition 1.1: $\{ f_n \}$ is said to enter cycle $X,Y,Z$ if for some $k>0$ we have $f_{k+3n} = X, f_{k+3n+1} =Y$, and $f_{k+3n+2} = Z$ for all integer $n \geq 0$.

Definition 1.2: A cycle is said to be non-constant if $X,Y,Z$ are not all equal. Similarly, a cycle is said to be distinct if $X \neq Y \neq Z$.

(Dec. 29) Remark 1.8: It seems not every positive integer is part of a distinct cycle (see Def. 1.2) That is, there are some (in fact, many) integers for which, no matter our choice of integers $a,b > 0$, the sequence $\{ f_n \}^{(a,b)}$ will not enter a distinct cycle with that integer. I am not sure if the same is true for non-constant cycles. For constant cycles, this is trivially not the case.

Solution 1:

I think there can be cycles of any odd length.
Take $2n+1$ odd primes $p_k$, for which any $n$ of them have a sum less than the other $n+1$.
Let $a_i = p_i-p_{i+1}+p_{i+2}-....+p_{i-1}$, where the index is taken cyclically. Then $a_i+a_{i+1}=2p_i$, and all the $a_i$ are odd.
Let $N$ be an odd number for which $Na_ia_{i+1}=a_{i+2}\pmod{a_i+a_{i+1}}$. That is possible by the Chinese Remainder Theorem.
Then take the numbers $\{Na_i\}$ as the cycle.

Solution 2:

This is not a complete answer, just my observations.

In short, I have split the "simpler" recursion into "decreasing" and "short" patterns.

For the initial recursion, I have only computations as everything seems much more chaotic.

The definitions and question

Let $(a,b)$ and $(a,b,c)$ be starting conditions for your recursions (for $n=1,2$ and $n=1,2,3$).

We write $f_n=f_n(a,b)$ for the recursion $f_n=f_{n-1}f_{n-2} \bmod[f_{n-1}+f_{n-2}],n\gt 2$.

We write $f_n=f_n(a,b,c)$ for $f_n=f_{n-1}f_{n-2}f_{n-3} \bmod[f_{n-1}+f_{n-2}+f_{n-3}],n\gt 3$.

If there exists $n_0$ such that $\forall n\ge n_0,f_n\in F$, we write $f_n\to F$, where $F$ is a tuple (ordered set) that represents a cycle. In this case, we say that $f_n$ converges to $F$.

Additionally, specially define $0\pmod 0:=0$ so "consecutive zeroes" (sequence terminates) can now be treated as a cycle $F_0=(0)=0$ (if $F$ has only one element, we can write it as a number instead).

Your question now becomes:

Does $f_n$ always converge to some cycle $F$?

If for some $n_0$ we have that $\forall n\ge n_0$, $f_n(a_1,b_1)= f_{n-n_0+1}(a_2,b_2)$, then we say that the pattern (starting conditions) $(a_1,b_1)$ converge to the pattern (sequence given by) $(a_2,b_2)$.

So we have to prove that all sequences either converges to some $F$ or to some other converging sequence.

About the "simpler" $f_n(a,b)$ recursive function

Proving that the "simpler" recursive sequence $f_n=f_n(a,b)$ always terminates looks possible, but hard.

I claim that, every pair of starting conditions $(a,b)$ either converges into the "decreasing pattern", or converges in finitely many steps following one of the "short patterns".

The "decreasing pattern" are sequences that could be extended to have arbitrarily large $n_0$, but still converge to some $F$. Otherwise, we have the "short pattern" of sequences that converge in at most $n_0\le n_0^{\text{max}}$ steps, for some constant $n_0^{\text{max}}$.

I claim the "decreasing pattern" is given by these three families of starting conditions:

$$\begin{array}{} f_n(6k+0,6k-6)\to 0, & n_0=k+1, & \text{(Ends as: $...,12,6,0.$)}\\ f_n(6k+2,6k-4)\to 0, & n_0=k+5, & \text{(Ends as: $...,14,8,2,6,4,4,0.$)}\\ f_n(6k+4,6k-2)\to 0, & n_0=k+3, & \text{(Ends as: $...,16,10,4,12,0.$)}\\ \end{array}$$

Where $k\ge2$ is a positive integer.

In other words, I claim that $n_0$ can be arbitrarily large if and only if the sequence $f_n(a,b)$ belongs to the "decreasing pattern" or converges into it. Otherwise, it either belongs to or converges to one of the "short patterns" in at most $n_0^{\text{max}}\lt\infty$ steps.

This claim would imply that $f_n(a,b)$ always converges in finitely many steps $n_0$.

This claim was verified for all possible pairs $(a,b)$ such that $a,b\le 2000$, so far.

The record breakers for the longest "short patterns", that have been observed so far, are:

$$\begin{array}{} f_n(1,1) & \to1, & n_0=2\\ f_n(1,2) & \to0, & n_0=4\\ f_n(2,1) & \to0, & n_0=5\\ f_n(3,2) & \to0, & n_0=6\\ f_n(3,4) & \to3, & n_0=7\\ f_n(2,9) & \to95, & n_0=14\\ f_n(11,2) & \to95, & n_0=15\\ f_n(12,19) & \to\{7,11,5\}, & n_0=17\\ f_n(21,8) & \to\{7,11,5\}, & n_0=20\\ f_n(24,23) & \to\{7,11,5\}, & n_0=21\\ f_n(16,27) & \to15, & n_0=23\\ f_n(29,13) & \to\{7,11,5\}, & n_0=25\\ f_n(7,32) & \to\{7,11,5\}, & n_0=27\\ f_n(28,37) & \to\{7,11,5\}, & n_0=38\\ f_n(9,52) & \to855, & n_0=59\\ f_n(57,124) & \to855, & n_0=61\\ f_n(126,113) & \to855, & n_0=77\\ f_n(145,126) & \to855, & n_0=78\\ f_n(305,261) & \to855, & n_0=79\\ f_n(948,889) & \to455, & n_0=80\\ f_n(350,1073) & \to855, & n_0=81\\ f_n(1159,1106) & \to6399, & n_0=85\\ f_n(157,1241) & \to8775, & n_0=93\\ f_n(942,1387) & \to54675, & n_0=99\\ &\dots& \end{array}$$

That is, so far, $n_0^{\text{max}}\ge 99$.

A potential issue could be that, the "decreasing pattern" is incomplete.

That is, are there more sequences that could have arbitrarily large $n_0(k)\gt n_0^{\text{max}}$, other than sequences that converge into one of the three families defined under "decreasing pattern"?

Assuming no such issue, the main problem is characterizing all of the "short patterns", which looks hard.

First, here are some easy conclusions to start with:

• We can assume $a\ne b$ since it is not hard to see that:

$$ f_n(a,a)\to\begin{cases}0 & (n_0=3), & 2\mid a \\a & (n_0=1), & 2\not\mid a \end{cases} $$

• We can also assume $a,b\ge 2$ since it is also not hard to see that:

$$ f_n(1,b)\to \begin{cases} 0 & (n_0=4), & 2\mid b \\ b & (n_0=2), & 2\not\mid b \end{cases} $$ $$ f_n(a,1)\to \begin{cases} 0 & (n_0=5), & 2\mid a \\ a & (n_0=3), & 2\not\mid a \end{cases} $$

• If $a=2$ then assume $b$ is odd, and if $b=2$ then assume $a$ is odd, since:

$$\begin{array}{} f(2,2k)\to 0, & (n_0=5) \\ f(2k,2)\to 0, & (n_0=6) \\ \end{array}$$

• Assume $a,b$ are not solutions to "$0=ab\bmod(a+b)$", since then $f_n(a,b)\to0, (n_0=3)$.

Looking at the last assumption, continuing to try to characterize "short patterns" via such equations $(x_{i}\cdot x_{i+1})\bmod (x_{i}+x_{i+1})=x_{i+2}$ looks like a never ending spiral of problems.

Instead, alternative ways are needed to find and prove $n_0^{\text{max}}$ and the remainder of the claim.

This reminds me more and more of the Collatz conjecture. In other words, this recursion could be as hard as that famous unsolved conjecture.

Nonlinear recurrences are generally chaotic. Even more, recurrence depending on modulo operation does not help at all.

About the $f_n(a,b,c)$ recursive function

Trying to characterize patterns here seems too hard. Even restricting to only $f_n(1,1,c),c\in\mathbb N$ sequences, I'm not seeing any useful structures.

I have computationally examined starting conditions $(1,1,c),c\in\mathbb N$. The elements of $F$ can get large, but they seem to have a lot of small factors. Hence, I will write them down in terms of their prime factorization.

It seems $n_0$ could get arbitrarily large, so I compiled the table of record $n_0$'s for $(1,1,c)$:

$$\begin{array}{ccl} (a,b,c) & n_0 & F \\ (1,1,1) & 1& \left(\begin{array}{}1\end{array}\right)\\ (1,1,2) & 6& \left(\begin{array}{}0\end{array}\right)\\ (1,1,3) & 8& \left(\begin{array}{}2\end{array}\right)\\ (1,1,4) & 9& \left(\begin{array}{}16\end{array}\right)\\ (1,1,5) & 10& \left(\begin{array}{}0\end{array}\right)\\ (1,1,8) & 19& \left(\begin{array}{}0\end{array}\right)\\ (1,1,9) & 143& \left(\begin{array}{}2^{33}\cdot5^2,\\2^{33}\cdot5^2,\\2^{31}\cdot5^2\cdot13,\\2^{31}\cdot5^2\cdot19\end{array}\right)\\ (1,1,18) & 493& \left(\begin{array}{}2^{73}\cdot5^3\cdot7^2\cdot11^2,\\2^{71}\cdot5^3\cdot7^3\cdot11^2,\\2^{70}\cdot5^4\cdot7^2\cdot11^2,\\2^{70}\cdot5^4\cdot7^2\cdot11^2\end{array}\right)\\ (1,1,73) & 1169& \left(\begin{array}{}2^{183}\cdot5^{13}\cdot7^{9}\cdot11^{6}\cdot13^{1}\cdot17^{2}\end{array}\right)\\ (1,1,128) & 4351& \left(\begin{array}{}2^{685}\cdot5^{83}\cdot7^{35}\cdot11^{6}\cdot13^{1}\cdot17^{2}\cdot19^{2}\cdot23^{2}\end{array}\right)\\ (1,1,877) & 5529& \left(\begin{array}{}2^{800}\cdot5^{87}\cdot7^{42}\cdot11^{13}\cdot13^{9}\cdot17^{1}\cdot19^{6}\cdot83^{1}\end{array}\right)\\ (1,1,1774) & 8637& \left(\begin{array}{}2^{1298}\cdot5^{140}\cdot7^{59}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{140}\cdot7^{59}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{140}\cdot7^{58}\cdot11^{20}\cdot13^{10}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{142}\cdot7^{58}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1},\\2^{1298}\cdot5^{142}\cdot7^{58}\cdot11^{20}\cdot13^{9}\cdot17^{4}\cdot23^{1}\cdot29^{2}\cdot79^{2}\cdot107^{1}\end{array}\right)\\ \dots & \dots & \dots \end{array}$$

Another observation is that cycles seem to be able to be of arbitrary length as well. For example, $f_n(1,1,7618)$ converges to a cycle $F$ of $32$ elements (at $n_0=556$):

$$\left(\begin{array}{l} 2^{106}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{2}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{2},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{2}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{2},\\ 2^{109}\cdot5^{13}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{108}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{2}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1}\cdot61^{1},\\ 2^{112}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{107}\cdot5^{13}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{108}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{109}\cdot5^{13}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{14}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{2},\\ 2^{108}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{4}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{110}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1},\\ 2^{106}\cdot5^{12}\cdot7^{3}\cdot13^{1}\cdot19^{1}\cdot31^{1} \end{array}\right)$$

Even if we only observe $c$'s such that $f_n(1,1,c)\to 0$, the $n_0$'s still seem to grow arbitrarily.

For example, $f_n(1,1,417)$ converges to $0$ after $n_0=448$ steps.

What is worse here compared to the "simpler" recursion, is that here the "decreasing pattern", if it exists, does not look easy.