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