The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A335791 For any n > 1, let x(0) = 2 and for any k >= 0, x(k+1) = (x(k)^2 + 1) mod n, d(k) = gcd(abs(x(k) - x(2*k)), n); necessarily, d(k) > 1 for some k > 0; a(n) is the first such d(k). 2
 2, 3, 4, 5, 3, 7, 8, 3, 2, 11, 3, 13, 7, 3, 16, 17, 3, 19, 4, 21, 22, 23, 3, 25, 2, 3, 7, 29, 3, 31, 32, 3, 2, 7, 3, 37, 2, 3, 8, 41, 21, 43, 44, 3, 2, 47, 3, 7, 2, 3, 4, 53, 3, 11, 7, 3, 2, 59, 3, 61, 62, 21, 64, 5, 3, 67, 4, 3, 7, 71, 3, 73, 2, 3, 4, 7, 3 (list; graph; refs; listen; history; text; internal format)
 OFFSET 2,1 COMMENTS This sequence is directly inspired by Pollard's rho algorithm for integer factorization; when a(n) < n, a(n) is a nontrivial divisor of n. LINKS Rémy Sigrist, Table of n, a(n) for n = 2..10000 Wikipedia, Pollard's rho algorithm FORMULA a(p) = p for any prime number p. EXAMPLE For n = 65: - we have:     k  x(k)  x(2*k)  d(k)     -  ----  ------  ----     0     2       2    65     1     5      26     1     2    26      15     1     3    27      52     5 - so a(65) = 5. PROG (PARI) a(n, g=x -> x^2+1) = { my (x1=2, x2=2); while (1, x1=g(x1) % n; x2=g(g(x2) % n) % n; my (d=gcd(abs(x1-x2), n)); if (d>1, return (d))) } CROSSREFS Cf. A002522, A335792. Sequence in context: A060653 A274690 A081810 * A071829 A229998 A331469 Adjacent sequences:  A335788 A335789 A335790 * A335792 A335793 A335794 KEYWORD nonn AUTHOR Rémy Sigrist, Jun 23 2020 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.

Last modified September 19 17:51 EDT 2021. Contains 347564 sequences. (Running on oeis4.)