A328702 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

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

LINKS

Table of n, a(n) for n=1..91.

EXAMPLE

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.

PROG

(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))))

CROSSREFS

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

Sequence in context: A324341 A271325 A228431 * A165620 A128494 A257696

Adjacent sequences: A328699 A328700 A328701 * A328703 A328704 A328705

KEYWORD

nonn

AUTHOR

Jianing Song, Oct 26 2019

STATUS

approved