A361913 a(n) is the number of steps in the main loop of the Pollard rho integer factorization algorithm for n, with x=2, y=2 and g(x)=x^2-1.

2, 2, 2, 1, 2, 4, 2, 2, 1, 2, 2, 3, 2, 1, 2, 4, 2, 3, 1, 2, 2, 8, 2, 1, 2, 2, 2, 4, 1, 4, 2, 2, 2, 1, 2, 6, 2, 2, 1, 5, 2, 6, 2, 1, 2, 11, 2, 4, 1, 2, 2, 5, 2, 1, 2, 2, 2, 7, 1, 3, 2, 2, 2, 1, 2, 4, 2, 2, 1, 3, 2, 8, 2, 1, 2, 2, 2, 10, 1, 2, 2, 12, 2, 1, 2, 2

Offset: 2

Author

Darío Clavijo, Mar 29 2023

Keywords

• nonn

Comments

x=2 and y=2 are the minimum effective values for Pollard rho, but any x = y > 2 would give the same answer.

n is in A217562 if gcd(n, a(n)) > 1.

n is in A047201 if gcd(phi(n), a(n)) > 1, where phi is Euler's totient function.

Links

• Eric Weisstein's World of Mathematics, Pollard rho Factorization Method.
• Wikipedia, Pollard's rho algorithm

Crossrefs

Cf. A005563.

Programs

Python

from gmpy2 import *
def a(n):
  c,d,x,y,g = 0,1,2,2,lambda x:pow(x,2,n)-1
  while d == 1:
    c,x,y =c+1,g(x),g(g(y))
    d = gcd(abs(x-y), n)
  return c