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

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

Offset

1,3

Comments

Let f(0) = 0, f(k+1) = (f(k)^2+1) mod n, then a(n) is the smallest i such that f(i) = f(j) for some j > i.

Obviously a(n) <= A000224(n): f(1), f(2), ..., f(A000224(n)+1) are all of the form (s^2+1) mod n, so there must exists 0 <= i < j <= A000224(n)+1 such that f(i) = f(j), and a(n) <= i <= A000224(n). The equality seems to hold only for n = 3.

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

Links

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

Example

A003095(n) mod 3: 0, 1, (2). {A003095(n) mod 3} enters into the cycle (2) from the 2nd term on, so a(3) = 2.
A003095(n) mod 7: 0, 1, 2, (5). {A003095(n) mod 7} enters into the cycle (5) from the 3rd term on, so a(7) = 3.
A003095(n) mod 29: 0, 1, 2, 5, 26, 10, 14, 23, 8, (7, 21). {A003095(n) mod 29} enters into the cycle (7, 21) from the 9th term on, so a(29) = 9.
A003095(n) mod 37: 0, 1, 2, 5, 26, (11). {A003095(n) mod 37} enters into the cycle (11) from the 5th term on, so a(37) = 5.
A003095(n) mod 41: (0, 1, 2, 5, 26, 21, 32). {A003095(n) mod 41} enters into the cycle (0, 1, 2, 5, 26, 21, 32) from the very beginning, so a(41) = 0.

Prog

(PARI) a(n) = my(v=[0], k); for(i=2, n+1, k=(v[#v]^2+1)%n; v=concat(v, k); for(j=1, i-1, if(v[j]==k, return(j-1))))

Crossrefs

Cf. A003095, A248218 (cycle length), A328700, A000224.

Sequence in context: A111374 A325181 A072739 * A030399 A128763 A127597

Adjacent sequences: A328696 A328697 A328698 * A328700 A328701 A328702

Keyword

nonn

Author

Jianing Song, Oct 26 2019

Status

approved