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
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Jun 23 2020
STATUS
approved