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,2

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

Table of n, a(n) for n=1..86.

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

Prog

(Python)
from sympy.ntheory.primetest import is_square
from sympy.core.power import isqrt
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)])

Crossrefs

Cf. A373461.

Sequence in context: A023134 A304536 A272863 * A112632 A254575 A355402

Adjacent sequences: A373349 A373350 A373351 * A373353 A373354 A373355

Keyword

nonn

Author

Peter Luschny, Jun 22 2024

Status

approved