login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328699 Start with 0, a(n) is the smallest number of iterations: x -> (x^2+1) mod n needed to run into a cycle. 1
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 (list; graph; refs; listen; history; text; internal format)
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 23 17:41 EDT 2021. Contains 346259 sequences. (Running on oeis4.)