

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



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(x1x2), n)); if (d>1, return (d))) }


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



