login
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.
0
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,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
PROG
(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
CROSSREFS
Cf. A005563.
Sequence in context: A132225 A263923 A331248 * A253196 A353981 A377289
KEYWORD
nonn
AUTHOR
Darío Clavijo, Mar 29 2023
STATUS
approved