A328702 Start with 0, a(n) is the smallest number of iterations: x -> (x^2+x+1) mod n needed to run into a cycle.

0, 1, 0, 1, 2, 1, 1, 1, 2, 2, 3, 1, 0, 1, 2, 1, 3, 2, 4, 2, 1, 3, 1, 1, 2, 1, 4, 1, 1, 2, 2, 1, 3, 3, 2, 2, 2, 4, 0, 2, 4, 1, 5, 3, 2, 1, 3, 1, 3, 2, 3, 1, 9, 4, 3, 1, 4, 1, 6, 2, 0, 2, 2, 1, 2, 3, 7, 3, 1, 2, 2, 2, 3, 2, 2, 4, 3, 1, 4, 2, 4, 4, 14, 1, 3, 5, 1, 3, 8, 2, 1

Offset: 1

Author

Jianing Song, Oct 26 2019

Keywords

• nonn

Comments

Let f(0) = 0, f(k+1) = (f(k)^2+f(k)+1) mod n, then a(n) is the smallest i such that f(i) = f(j) for some j > 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 0 <= i < j <= A290731(n)+1 such that f(i) = f(j), and a(n) <= i <= A290731(n). The equality seems to hold only for n = 2.

k divides A002065(m) for some m > 0 if and only if a(k) = 0, in which case all the indices m such that k divides A002065(m) are m = t*A328701(k), t = 0, 1, 2, 3, ...

Examples

			A002065(n) mod 4: 0, (1, 3). {A002065(n) mod 4} enters into the cycle (1, 3) from the 1st term on, so a(4) = 1.
A002065(n) mod 7: 0, (1, 3, 6). {A002065(n) mod 7} enters into the cycle (1, 3, 6) from the 1st term on, so a(7) = 1.
A002065(n) mod 11: 0, 1, 3, (2, 7). {A002065(n) mod 11} enters into the cycle (2, 7) from the 3rd term on, so a(11) = 3.
A002065(n) mod 19: 0, 1, 3, 13, (12, 5). {A002065(n) mod 19} enters into the cycle (12, 5) from the 4th term on, so a(19) = 4.
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.
		

Crossrefs

Cf. A002065, A328701 (cycle length), A328703, 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(j-1))))