

A328701


Period in residues modulo n in iteration of x^2 + x + 1 starting at 0.


2



1, 1, 2, 2, 1, 2, 3, 4, 2, 1, 2, 2, 3, 3, 2, 8, 1, 2, 2, 2, 6, 2, 4, 4, 4, 3, 2, 6, 7, 2, 7, 16, 2, 1, 3, 2, 3, 2, 6, 4, 7, 6, 5, 2, 2, 4, 5, 8, 3, 4, 2, 6, 1, 2, 2, 12, 2, 7, 11, 2, 4, 7, 6, 32, 3, 2, 2, 2, 4, 3, 10, 4, 18, 3, 4, 2, 6, 6, 3, 8, 2, 7, 2, 6, 1, 5, 14, 4, 1, 2, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

a(n) is the period of {A002065 mod n}.
Let f(0) = 0, f(k+1) = (f(k)^2+f(k)+1) mod n, then a(n) is the smallest t such that f(i) = f(i+t) for all sufficiently large i.
Obviously a(n) <= A290731(n): f(1), f(2), ..., f(A290731(n)+1) are all of the form (s^2+s+1) mod n, so there must exists 1 <= i < j <= A290731(n)+1 such that f(i) = f(j), and a(n) <= j  i <= A290731(n). The equality seems to hold only for n = 3, 6 or n is a power of 2.


LINKS



FORMULA

a(n1*n2) = lcm(a(n1),a(n2)) if gcd(n1,n2) = 1.
It seems that for e > 0, a(3^e) = 2; a(5^e) = 1 if e = 1, 4*5^(e2) otherwise; a(7^e) = 3; a(11^e) = 2 if e = 1, 10*11^(e2) otherwise; a(13^e) = 3 if e = 1, 12*13^(e2) otherwise ...
Proof that a(2^e) = 2^(e1) by induction: we will show that {f(1), f(2), ..., f(2^(e1)} is a reduced system modulo 2^e, where f is defined in the comment section. It is easy to see that this is true for e = 1, 2.
Suppose that {f(1), f(2), ..., f(2^(e1))} is a reduced system modulo 2^e, e = 1, 2. For each 1 <= i <= 2^(e1), f(2^(e1)+i)  f(i) = Sum_{j=i..2^(e1)+i1} (f(j+1)f(j)) = Sum_{j=i..2^(e1)+i1} (f(j)^2+1) = 2^(e1) + Sum_{j=i..2^(e1)+i1} f(j)^2. Of course, {f(i), f(i+1), ..., f(2^(e1)+i1)} is also a reduced system modulo 2^e.
Note that if x == y (mod 2^e), then x^2 == y^2 (mod 2^(e+1)). So f(2^(e1)+i)  f(i) == 2^(e1) + (1^2+3^2+5^2+...+(2^e1)^2) == 2^e (mod 2^(e+1)), 1 <= i <= 2^(e1). This shows that {f(1), f(2), ..., f(2^(e1)), f(2^(e1)+1), f(2^(e1)+2), ..., f(2^e)} is a reduced system modulo 2^(e+1). QED.


EXAMPLE

In the following example, () denotes the cycles.
A002065(n) mod 4: 0, (1, 3), so a(4) = 2.
A002065(n) mod 7: 0, (1, 3, 6), so a(7) = 3.
A002065(n) mod 29: 0, (1, 3, 13, 9, 4, 21, 28), so a(29) = 7.
A002065(n) mod 61: (0, 1, 3, 13). {A002065(n) mod 61} enters into the cycle (0, 1, 3, 13) from the very beginning, so a(61) = 0.
A002065(n) mod 64: 0, (1, 3, 13, 55, 9, 27, 53, 47, 17, 51, 29, 39, 25, 11, 5, 31, 33, 35, 45, 23, 41, 59, 21, 15, 49, 19, 61, 7, 57, 43, 37, 63), so a(64) = 32.


PROG

(PARI) a(n) = my(v=[0], k); for(i=2, n+1, k=(v[#v]^2+v[#v]+1)%n; v=concat(v, k); for(j=1, i1, if(v[j]==k, return(ij))))


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



