cp's OEIS Frontend

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

%I A373352 #25 Jun 22 2025 03:08:15
%S A373352 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 A373352 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 A373352 3,10,1,6,1,2,15,4,7,6,1,8,9,2,1,6,5,2
%N A373352 Factor of n generated by William B. Hart's 'one line' factoring algorithm.
%C A373352 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 A373352 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 A373352 (Python)
%o A373352 from math import isqrt
%o A373352 from sympy.ntheory.primetest import is_square
%o A373352 from sympy import igcd
%o A373352 def a(n):
%o A373352     k = -1
%o A373352     while True:
%o A373352         k += n
%o A373352         s = isqrt(k) + 1
%o A373352         m = pow(s, 2, n)
%o A373352         if is_square(m):
%o A373352             return igcd(n, s - isqrt(m))
%o A373352 print([a(n) for n in range(1, 87)])
%Y A373352 Cf. A373461.
%K A373352 nonn
%O A373352 1,2
%A A373352 _Peter Luschny_, Jun 22 2024