9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Trying your formula on the computer, I'm just getting $1$, $p - 1$, $0$, ZeroDivisionError for every value of $p$ I've tried. Are you sure you have it right? $\endgroup$ – Jack M Apr 20 '14 at 18:48
  • $\begingroup$ I think so. If p=3 then x_1 = 3-1-((3*0-1) % 1) = 2-(-1 % 1) = 2-0 = 2. x_2=2, x_3=1, x_4=2, ... $\endgroup$ – O. S. Dawg Apr 20 '14 at 19:19
  • 1
    $\begingroup$ Very interesting. A check for the first few primes suggests that your conjecture may be correct. $\endgroup$ – Anant May 10 '14 at 16:24
0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ You mean "for any proper subset of the columns" and "entirely comprised of a value not among the column indices", but I don't see why for any such subset there must be a row that does not contain any of those column indices. Also, I don't see why the period must be the $lcm$ of the columns' periods, since it is conceivable that the sequence repeats itself but some blocks follow different sequences of columns. What we do know from your argument is that the period of the sequence is a divisor of the $lcm$ of the first $p-1$ positive integers. $\endgroup$ – user21820 May 17 '14 at 2:56
  • $\begingroup$ Could you explain your table? What does the first row with $\text{mod}$ signify? What are the columns and/or rows? $\endgroup$ – Mussé Redi May 17 '14 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.