The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 Table of n, a(n) for n=1..91. 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. 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=, 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)))) CROSSREFS Cf. A002065, A328702 (indices to enter the cycles), A290731. Sequence in context: A292602 A071444 A232441 * A085257 A352889 A230507 Adjacent sequences: A328698 A328699 A328700 * A328702 A328703 A328704 KEYWORD nonn AUTHOR Jianing Song, Oct 26 2019 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 4 03:55 EDT 2023. Contains 363118 sequences. (Running on oeis4.)