Finch's sequence over $\mathbb{F}_3$

2010-12-29T21:31:31Z

In http://algo.inria.fr/csolve/seqmod3.pdf -- "Periodicity in sequences mod 3" Steven Finch (also cited in Sloane's OEIS A112683) defines the following sequences in $\mathbb{F}_3$:

For each positive integer $k$, consider the sequence $x_n$ in $\mathbb{F}_3$

$x_i = 0$ for $i=1,2, \dots, k-1$, $x_k = 1$ and

$x_n = x_{n-1} + x_{n-k}^2$ for $n > k$.

Since we're working in a finite field, the sequence is eventually periodic. Let $N(k)$ denote the period. Can we write down a formula for $N(k)$? Can we give good bounds, etc? The values which have been computed are:

1,4,4,9,19,4,4,22,36,4,4,45,64,4,4,102,1082,231,4,188,272,4,412,225,202,4,4

Richard Pinch had an explanation for all the 4's as follows:

"The semi-ubiquitous 4's come from the fact that 2011 is a cycle when $k$ is $2 \bmod 4$ and 2201 when $k$ is $3 \bmod 4$. Of course the sequence does not have to lock on to that cycle: for example when $k$ is 18 or 23".

I can't find any more references to the problem than the ones that I give.

Finch's sequence over $\mathbb{F}_3$ - MathOverflow

Finch's sequence over $\mathbb{F}_3$