Finch's sequence over \$\mathbb{F}_3\$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T17:08:36Z http://mathoverflow.net/feeds/question/50678 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50678/finchs-sequence-over-mathbbf-3 Finch's sequence over \$\mathbb{F}_3\$ Victor Miller 2010-12-29T21:31:31Z 2010-12-29T21:31:31Z <p>In <a href="http://algo.inria.fr/csolve/seqmod3.pdf" rel="nofollow">http://algo.inria.fr/csolve/seqmod3.pdf</a> -- "Periodicity in sequences mod 3" Steven Finch (also cited in Sloane's OEIS A112683) defines the following sequences in \$\mathbb{F}_3\$:</p> <p>For each positive integer \$k\$, consider the sequence \$x_n\$ in \$\mathbb{F}_3\$</p> <p>\$x_i = 0\$ for \$i=1,2, \dots, k-1\$, \$x_k = 1\$ and</p> <p>\$x_n = x_{n-1} + x_{n-k}^2\$ for \$n > k\$.</p> <p>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:</p> <p>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</p> <p>Richard Pinch had an explanation for all the 4's as follows:</p> <p>"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".</p> <p>I can't find any more references to the problem than the ones that I give.</p>