cp's OEIS Frontend

A379863 a(n) is the number of steps in a Pollard rho like integer factorization algorithm for m = 2*n + 1 with f(x) = 2^x mod m and starting from x = y = 1.

%I A379863 #23 Jan 08 2025 16:38:30
%S A379863 2,3,2,3,5,9,3,4,10,2,6,7,2,10,3,2,3,26,2,7,2,2,4,3,2,42,4,2,21,32,2,
%T A379863 3,52,2,6,4,2,5,6,2,73,4,2,5,3,2,4,10,2,33,10,2,7,9,2,7,7,2,6,27,2,5,
%U A379863 2,2,93,5,2,15,53,2,7,4,2,19,3,2,3,6,2,9,126
%N A379863 a(n) is the number of steps in a Pollard rho like integer factorization algorithm for m = 2*n + 1 with f(x) = 2^x mod m and starting from x = y = 1.
%C A379863 Each step is x -> f(x) and y -> f(f(y)), until finding g = gcd(x-y, m) != 1, since then g is a factor of m (though if x = y is reached then merely g = m).
%C A379863 Even m are not considered since they would be always 1 step to reach x = 2, y = 4 with g = 2.
%C A379863 Sometimes this f finds a factor with less work than the more common x^2+1, as for instance at m = 4295229443 which is a(2147614721) = 3 steps and about 57 modular squares in the powering, as against x^2 + 1 taking 172 steps with 516 squares.
%H A379863 Wikipedia, <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm">Pollard's rho algorithm</a>
%e A379863 For n = 117, m = 235 and the a(117) = 3 steps until finding g != 1 are
%e A379863    x = 1, 2,   4, 16,
%e A379863    y = 1  4, 206, 96,
%e A379863 with g = gcd(96-16, 235) = 5 in this case being a proper factor of m.
%p A379863 coprime := (a, b) -> NumberTheory:-AreCoprime(a, b):
%p A379863 a := proc(n) local m, c, x, y, f;
%p A379863   if n = 1 then return 2 fi;
%p A379863   m := 2*n + 1; x := 2; y := 4;
%p A379863   f := x -> 2 &^ x mod m;
%p A379863   for c while coprime(x - y, m) do
%p A379863       x := f(x); y := f(f(y));
%p A379863   od; c end:
%p A379863 seq(a(n), n = 1..81);  # _Peter Luschny_, Jan 07 2025
%o A379863 (Python)
%o A379863 from math import gcd
%o A379863 def a(n):
%o A379863     m = 2*n+1
%o A379863     c,g,x,y = 0,1,1,1
%o A379863     f = lambda x: pow(2,x,m)
%o A379863     while g == 1:
%o A379863         x = f(x)
%o A379863         y = f(f(y))
%o A379863         g = gcd(x - y, m)
%o A379863         c += 1
%o A379863     return c
%o A379863 print([a(n) for n in range(1,82)])
%Y A379863 Cf. A000079, A005408, A361913.
%K A379863 nonn
%O A379863 1,1
%A A379863 _Darío Clavijo_, Jan 04 2025