login
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
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.
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
Sequence in context: A060653 A274690 A081810 * A071829 A229998 A331469
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Jun 23 2020
STATUS
approved