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
Keywords
Examples
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.
Links
- Wikipedia, Pollard's rho algorithm
Programs
-
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 -
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)])
Comments