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

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

Offset: 1

Author

Jianing Song, Oct 26 2019

Keywords

• nonn

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.

Examples

			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.
		

Crossrefs

Cf. A002065, A328702 (indices to enter the cycles), A290731.

Programs

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, i-1, if(v[j]==k, return(i-j))))

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^(e-2) otherwise; a(7^e) = 3; a(11^e) = 2 if e = 1, 10*11^(e-2) otherwise; a(13^e) = 3 if e = 1, 12*13^(e-2) otherwise ...

Proof that a(2^e) = 2^(e-1) by induction: we will show that {f(1), f(2), ..., f(2^(e-1))} 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^(e-1))} is a reduced system modulo 2^e, e = 1, 2. For each 1 <= i <= 2^(e-1), f(2^(e-1)+i) - f(i) = Sum_{j=i..2^(e-1)+i-1} (f(j+1)-f(j)) = Sum_{j=i..2^(e-1)+i-1} (f(j)^2+1) = 2^(e-1) + Sum_{j=i..2^(e-1)+i-1} f(j)^2. Of course, {f(i), f(i+1), ..., f(2^(e-1)+i-1)} 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^(e-1)+i) - f(i) == 2^(e-1) + (1^2+3^2+5^2+...+(2^e-1)^2) == 2^e (mod 2^(e+1)), 1 <= i <= 2^(e-1). This shows that {f(1), f(2), ..., f(2^(e-1)), f(2^(e-1)+1), f(2^(e-1)+2), ..., f(2^e)} is a reduced system modulo 2^(e+1). QED.