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.

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, 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, 2, 2, 93, 5, 2, 15, 53, 2, 7, 4, 2, 19, 3, 2, 3, 6, 2, 9, 126

Offset

1,1

Comments

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

Even m are not considered since they would be always 1 step to reach x = 2, y = 4 with g = 2.

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.

Links

Table of n, a(n) for n=1..81.

Wikipedia, Pollard's rho algorithm

Example

For n = 117, m = 235 and the a(117) = 3 steps until finding g != 1 are
   x = 1, 2,   4, 16,
   y = 1  4, 206, 96,
with g = gcd(96-16, 235) = 5 in this case being a proper factor of m.

Maple

coprime := (a, b) -> NumberTheory:-AreCoprime(a, b):
a := proc(n) local m, c, x, y, f;
  if n = 1 then return 2 fi;
  m := 2*n + 1; x := 2; y := 4;
  f := x -> 2 &^ x mod m;
  for c while coprime(x - y, m) do
      x := f(x); y := f(f(y));
  od; c end:
seq(a(n), n = 1..81);  # Peter Luschny, Jan 07 2025

Prog

(Python)
from math import gcd
def a(n):
    m = 2*n+1
    c, g, x, y = 0, 1, 1, 1
    f = lambda x: pow(2, x, m)
    while g == 1:
        x = f(x)
        y = f(f(y))
        g = gcd(x - y, m)
        c += 1
    return c
print([a(n) for n in range(1, 82)])

Crossrefs

Cf. A000079, A005408, A361913.

Sequence in context: A199334 A330903 A278910 * A337982 A235669 A118088

Adjacent sequences: A379860 A379861 A379862 * A379864 A379865 A379866

Keyword

nonn,new

Author

Darío Clavijo, Jan 04 2025

Status

approved