login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #8 Oct 27 2019 14:29:51

%S 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,

%T 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,

%U 1,2,2,2,3,2,2,4,3,1,4,2,4,4,14,1,3,5,1,3,8,2,1

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

%C 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.

%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 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.

%C 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, ...

%e 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.

%e 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.

%e 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.

%e 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.

%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.

%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(j-1))))

%Y Cf. A002065, A328701 (cycle length), A328703, A290731.

%K nonn

%O 1,5

%A _Jianing Song_, Oct 26 2019