Voozh

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,1

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

Table of n, a(n) for n=2..87.

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

Wikipedia, Pollard's rho algorithm

PROG