What is the period of this sequence?

Question

Consider the recurrence relation:

$$x_{i+1}=p-1-((p \cdot i-1) \mod{x_i})$$

If $p$ is prime and $x_0=1$, what is the least period of the resulting (eventually periodic) sequence?

My guess is the minimal period equals $\text{lcm}(p-1,...,2)$ but I only rarely believe this and can't quite gather a convincing amount of numerical evidence.

Edit (1/19/17):

Suppose $p$ is composite. Should $\text{gcd}(x_{i_0},p)$ be greater than one for some $i_0$ then it is always greater than one thereafter. So findng a factor of $p$ reduces to computing $x_i$ for any large enough $i$.

The few experiments I have done suggest this sequence always (rather inefficiently) cracks $p$. Can anyone here find a counterexample?

Answer 1

Your guess is correct.

We can construct a table of $x_{i+1}$ with values of $(p\cdot i-1)$ as the y-axis and $x_i$ (the modulus) as the x-axis; considering the example of $p=5$ we have:

          mod
 pi-1    1 2 3 4

  4      4 4 3 4
  9      4 3 4 3
 14      4 4 2 2
 19      4 3 3 1
 24      4 4 4 4
 29      4 3 2 3
 34      4 4 3 2
 39      4 3 4 1
 44      4 4 2 4
 49      4 3 3 3
 54      4 4 4 2
 59      4 3 2 1
 64      4 4 3 4

Note how $0 < x_i < p$, and how since $p$ is prime, the period of any column, $x_i$, will be $x_i$. This makes it easy to see that the period of the entire table (before rows begin repeating) is indeed $\text{lcm} (1, ..., p-1)$.

To see why this represents the period of the sequence in question, consider the fact that $x_{i+1}$ will be equal to the ${x_i}^{th}$ number in the $i^{th}$ row of the above table. For example $x_3 = 3$ so we go to the 3rd element of the third row (beginning with 14), and we get $x_4 = 2$. We then go to the 2nd element of the next row and we get $x_5 = 3$, and so on.

Considering this, it is clear that the period will be the lcm of every column which is visited at least once (so if it was the case that the value switched between the 2nd and 3rd columns, the period would only be 6). However, it is impossible for the sequence to not include each number at least once. This is because for any subset of the columns, there must be at least one row which is entirely comprised of a value not among those rows. Since each column will include numbers not in the subset, and since the columns are all coprime (and if not, can be equivalently represented by a set of coprime columns), a combination only including these numbers must occur at least once. This means that no matter what the previous value was, the next will have to be in an outside row.

I am only an enthusiast, and have little experience with trying to rigorously express my ideas; I tried to make my explanation as clear as I could but please feel free to ask for clarification if you see any lapse in logic or something difficult to understand.

Answer 2

I give a proof that the sequence is eventually periodic with period $L:=\mbox{lcm}(p-1,p-2,\ldots,1)$. I was not able to prove that this is the minimal eventual period, but I have some observations which I think are pretty good evidence.

Proposition: The sequence is eventually periodic with period $L:=\mbox{lcm}(p-1,p-2,\ldots,1)$.

Proof: First, note that $1\leq x_i\leq p-1$ for all $i$, which follows from $0\leq((p\cdot i-1)\ \mbox{mod}\ x_i)\leq x_i-1$ by induction. It follows that $x_i|L$ for all $i$. In order to determine the value of $((p\cdot i-1)\ \mbox{mod}\ x_i)$, it is thus sufficient to know the value of $i$ modulo $L$.

Since $p$ is prime, we have $\mbox{gcd}(p,L)=1$. By Bézout's identity, we find $i,j$ with $p\cdot i+L\cdot j=1$, so $p\cdot i-1\equiv 0\ (\mbox{mod}\ L)$. For all $k$, we have $x_{i+k\cdot L}|L$, and thus $$x_{i+k\cdot L+1}=p-1+((p\cdot(i+k\cdot L)-1)\ \mbox{mod}\ x_{i+k\cdot L})=p-1.$$ By the previous discussion, from $x_{i+1}=x_{i+1+L}$ it follows that $x_{i+j}=x_{i+j+L}$ for all $j\geq1$. We find that the sequence is eventually periodic with period $L$. $\square$

Remark: Note that it follows from the proof that the period also begins within the first $L$ terms.

Remark: Note that the same proof applies to the recurrence $x_{i+1}=p-1-((a\cdot i+b)\ \mbox{mod}\ x_i)$ for any $a,b$ with $a$ coprime with $L$, meaning all prime factors of $a$ are at least as large as $p$.

I am not sure whether $L$ is always the minimal eventual period of the sequence, but I think the following is pretty good evidence for the affirmative.

Proposition: If the sequence is periodic with period $K$ for $i\geq N$, then $x_i|K$ for all $i\geq N$.

Proof: Assume for the contrary that $x_i\not|K$ for some $i\geq N$. By $x_i\leq p-1$, it follows that $x_i\not|p\cdot K$, so $p\cdot i-1\not\equiv p\cdot(i+K)-1\ (\mbox{mod}\ x_i)$. This is in contradiction with $x_i=x_{i+K}$ and $x_{i+1}=x_{i+K+1}$. $\square$

We want to prove that $L|K$. It would thus suffice to show, for all $1\leq n\leq p-1$, there exists $i\geq N$ with $n|x_i$. The following argument almost proves this, but not quite.

By Bézout's identity, we find $i$ with $p\cdot i\equiv p-n\ (\mbox{mod}\ L)$. This gives $$x_{i+1}=p-1-((p\cdot i-1)\ \mbox{mod}\ x_i)=p-1-((p-1-n)\ \mbox{mod}\ x_i).$$ If $p-n-1\leq x_i$, then this would give $x_{i+1}=n$. By taking multiples of $n$ instead, this event can be made more likely, but it is still not certain.

For your Edit (1/19/17), it is also relevant to find $x_i$ divisible by certain numbers, so we run into the same issues.