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

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, 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, 3, 10, 1, 6, 1, 2, 15, 4, 7, 6, 1, 8, 9, 2, 1, 6, 5, 2

Offset: 1

Author

Peter Luschny, Jun 22 2024

Keywords

• nonn

Comments

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)).

Links

• William B. Hart, A One Line Factoring Algorithm, J. Aust. Math. Soc. 92 (2012), 61-69.

Crossrefs

Cf. A373461.

Programs

Python

from math import isqrt
from sympy.ntheory.primetest import is_square
from sympy import igcd
def a(n):
    k = -1
    while True:
        k += n
        s = isqrt(k) + 1
        m = pow(s, 2, n)
        if is_square(m):
            return igcd(n, s - isqrt(m))
print([a(n) for n in range(1, 87)])