I am looking at what happens when the cyclic 1st order difference is repeatedly applied modulo $N$ to an initial sequence of length $N$. The cyclic 1st order difference is the difference between consecutive elements assuming the sequence is cyclic. That means
$x_{n+1}(1) = x_n(2)-x_n(1)$,
$x_{n+1}(2) = x_n(3)-x_n(2)$,
and the last element is
$x_{n+1}(N) = x_n(1) - x_n(N)$ (the modulo operation is omitted for convenience).
For example, if $N$ = 6 and the initial sequence is
$x = \begin{array}{r}\{1&0&0&0&0&0\}\end{array}$
then the output eventually cycles through the six states
$x_n = \begin{array}{r}\{5,1,1,4,2,5\}\end{array}$
$x_{n+1} = \begin{array}{r}\{2,0,3,4,3,0\}\end{array}$
$x_{n+2} = \begin{array}{r}\{4,3,1,5,3,2\}\end{array}$
$x_{n+3} = \begin{array}{r}\{5,4,4,4,5,2\}\end{array}$
$x_{n+4} = \begin{array}{r}\{5,0,0,1,3,3\}\end{array}$
$x_{n+5} = \begin{array}{r}\{1,0,1,2,0,2\}\end{array}$
Since for any N the number of states is finite they will eventually repeat with a fixed period, or end up as all zeros. I have an efficient implementation in C++ that can handle $N$ up to just over 100. Using an impulse as the initial state I have noticed the following two properties empirically.
- iff $N$ is a prime power the end state is zero
- the period is always a multiple of $N$
Here are the values of the period $p$ divided by $N$ for 50 <= $N$ <= 70.
N=50, p=10,230
N=51, p=13,120
N=52, p=126
-- 53 prime
N=54, p=4,599
N=55, p=284
N=56, p=12
N=57, p=118,092
N=58, p=229,362
-- 59 prime
N=60, p=4
-- 61 prime
N=62, p=5
N=63, p=2,964
-- 64 prime power
N=65, p=336
N=66, p=3,410
-- 67 prime
N=68, p=60
N=69, p=169,444
N=70, p=58,032
The highest period calculated by the C++ program is for
N=106, p=1,744,830,438,
corresponding to around 180 billion iterations of the difference operator.
The smallest $N$ for which the period is so large that the C++ program does not find it during a night of number crunching is 115.
My hope is to be able to find a way to calculate the period from $N$ and the initial state. As far as I can tell there is no obvious pattern in the periods I have already calculated. Any suggestions or links to relevant information are much appreciated.
I have made significant progress with this, although mainly on the numerical side. The progress is based on two insights.
First, assume $N$ is an even integer which is not a prime power. If the first-order difference modulo $N$ is applied $N$ times the result is a symmetric Toeplitz matrix. For example if N = 10, applying the first-order difference ten times is equivalent to multiplying by the matrix $D_{10}$, where
$$ D_{10} = \begin{bmatrix} 2 & 0 & 5 & 0 & 0 & 8 & 0 & 0 & 5 & 0 \\ 0 & 2 & 0 & 5 & 0 & 0 & 8 & 0 & 0 & 5 \\ 5 & 0 & 2 & 0 & 5 & 0 & 0 & 8 & 0 & 0 \\ 0 & 5 & 0 & 2 & 0 & 5 & 0 & 0 & 8 & 0 \\ 0 & 0 & 5 & 0 & 2 & 0 & 5 & 0 & 0 & 8 \\ 8 & 0 & 0 & 5 & 0 & 2 & 0 & 5 & 0 & 0 \\ 0 & 8 & 0 & 0 & 5 & 0 & 2 & 0 & 5 & 0 \\ 0 & 0 & 8 & 0 & 0 & 5 & 0 & 2 & 0 & 5 \\ 5 & 0 & 0 & 8 & 0 & 0 & 5 & 0 & 2 & 0 \\ 0 & 5 & 0 & 0 & 8 & 0 & 0 & 5 & 0 & 2 \\ \end{bmatrix}. $$ The matrix actually has a further symmetry since elements 2 to $N$ in the first row are symmetric around element $N/2 + 1$.
For $N$ odd and not a prime power the same property holds except the first-order difference matrix must be raised to the $2N^{th}$ power, not $N^{th}$ power. Furthermore, the symmetry of the first row is not around a single element but rather around a pair of elements. For example, the first row of $D_{30}$ for $N = 15$ is
$$ D_{30}(1,:) = \begin{array}{r} \{2 & 0& 0& 5& 0& 9& 0& 0& 0& 0& 9& 0& 5& 0& 0\} \\ \end{array} $$
Since the period is always a multiple of $N$ it is not necessary to iterate the first-order difference. It is enough to iterate over $D_N$ which reduces the amount of computations by approximately a factor of $N$.
The second important insight is that in the initial search for the period $P$, it is sufficient to hit a multiple of $P$ rather than $P$ itself. For example, let's say that for a particular $N$ the period is $P$ = 2 * 3 * 7 = 42 so that $D_N = (D_N)^{42}$. All we have to do is to repeatedly raise $D_N$ to prime powers until the result is equal to $D_N$. In the current example, we would test equality against $D_N$ for $(D_N)^2$, $(D_N)^{2*3} = (D_N)^6$, $(D_N)^{2*3*5} = (D_N)^{30}$, and $(D_N)^{2*3*5*7} = (D_N)^{210}$. The period 42 is not among the powers tested but it divides 2 * 3 * 5 * 7 = 210 and therefore $D_N = (D_N)^{210}$. We now know all the prime factors of $P$ are among 2, 3, 5, and 7, and we know 7 is the largest prime factor. In order to find the smaller factors, the search is run again on $(D_N)^7$, which will find the second largest factor, and so on.
In practice, small factors such as 2 are often repeated, and it is therefore a bad idea to use only the primes 2, 3, 5, and 7. It is better to use something like $2^5$, $3^5$, $5^4$, and $7^4$.
In order to speed things up binary exponentiation is used for raising $D_N$ to the power of primes, and above a certain threshold, say one million, we use only one prime factor. For example, imagine you want to continue testing from the number $P_0 = (D_N)^{2*3*5*7}$. For primes smaller than the threshold you continue with $(P_0)^{11}$, then $(P_0)^{11*13}$, $(P_0)^{11*13*17}$, and so on. For numbers greater than the threshold you continue with $(P_0)^{11}$, $(P_0)^{13}$, $(P_0)^{17}$, and so on. In that way each iteration requires the previous matrix to be raised to a power that is the difference between the last two primes (13-11=2, 17-13=4) rather than the power of the current prime (13, 17).
The techniques described above are implemented in C++ for $N <= 200$. The largest period for even $N$ is $P_{174}$, $$P_{174} = 103,303,762,520,840 = 2^3*5*7*43*113*127*547*1093$$
The largest prime factor for even $N$ occurs in $P_{166}$, $$P_{166} = 90,159,953,477,591 = 41*13,367*164,511,353$$
The only numbers smaller than 200 whose periods still need to be determined are 119 and 141. Both of these numbers have periods that either have at least one prime factor greater than one billion, or at least two prime factors greater than ten million.