|
%I #11 Oct 27 2019 14:29:38
%S 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,
%T 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,
%U 2,4,3,10,4,18,3,4,2,6,6,3,8,2,7,2,6,1,5,14,4,1,2,3
%N Period in residues modulo n in iteration of x^2 + x + 1 starting at 0.
%C a(n) is the period of {A002065 mod n}.
%C 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.
%C 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.
%F a(n1*n2) = lcm(a(n1),a(n2)) if gcd(n1,n2) = 1.
%F 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 ...
%F 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.
%F 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.
%F 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.
%e In the following example, () denotes the cycles.
%e A002065(n) mod 4: 0, (1, 3), so a(4) = 2.
%e A002065(n) mod 7: 0, (1, 3, 6), so a(7) = 3.
%e A002065(n) mod 29: 0, (1, 3, 13, 9, 4, 21, 28), so a(29) = 7.
%e 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.
%e 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.
%o (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))))
%Y Cf. A002065, A328702 (indices to enter the cycles), A290731.
%K nonn
%O 1,3
%A _Jianing Song_, Oct 26 2019
|
