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!)
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.

License Agreements, Terms of Use, Privacy Policy. .

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