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

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