A335791 - OEIS

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

%I #11 Jun 27 2020 17:00:35

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

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

%U 3,61,62,21,64,5,3,67,4,3,7,71,3,73,2,3,4,7,3

%N 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).

%C 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.

%H Rémy Sigrist, <a href="/A335791/b335791.txt">Table of n, a(n) for n = 2..10000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Pollard's_rho_algorithm#Algorithm">Pollard's rho algorithm</a>

%F a(p) = p for any prime number p.

%e For n = 65:

%e - we have:

%e k x(k) x(2*k) d(k)

%e - ---- ------ ----

%e 0 2 2 65

%e 1 5 26 1

%e 2 26 15 1

%e 3 27 52 5

%e - so a(65) = 5.

%o (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))) }

%Y Cf. A002522, A335792.

%K nonn

%O 2,1

%A _Rémy Sigrist_, Jun 23 2020