A373352 - OEIS

%I #18 Jun 23 2024 09:34:41

%S 1,2,1,2,1,2,1,2,3,2,1,2,1,2,3,4,1,6,1,4,3,2,1,4,5,2,3,2,1,6,1,4,3,2,

%T 5,6,1,2,3,4,1,6,1,4,5,2,1,6,7,10,3,2,1,6,5,8,3,2,1,6,1,2,7,8,5,6,1,4,

%U 3,10,1,6,1,2,15,4,7,6,1,8,9,2,1,6,5,2

%N Factor of n generated by William B. Hart's 'one line' factoring algorithm.

%C The algorithm finds a nontrivial factor of n. If it returns 1 then n is an odd prime or 1. It has heuristic running time O(n^(1/3 + eps)).

%H William B. Hart, <a href="https://doi.org/10.1017/S1446788712000146">A One Line Factoring Algorithm</a>, J. Aust. Math. Soc. 92 (2012), 61-69.

%o (Python)

%o from sympy.ntheory.primetest import is_square

%o from sympy.core.power import isqrt

%o from sympy import igcd

%o def a(n):

%o     k = -1

%o     while True:

%o         k += n

%o         s = isqrt(k) + 1

%o         m = pow(s, 2, n)

%o         if is_square(m):

%o             return igcd(n, s - isqrt(m))

%o print([a(n) for n in range(1, 87)])

%Y Cf. A373461.

%K nonn

%O 1,2

%A _Peter Luschny_, Jun 22 2024