A373461 a(n) = s - t where s = ceiling(sqrt(n*i)), t = sqrt(m), and m = s^2 mod n, for the smallest positive integer i for which m is square.

1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 5, 2, 7, 8, 3, 4, 9, 6, 11, 4, 3, 14, 15, 4, 5, 16, 3, 6, 19, 6, 21, 4, 9, 24, 5, 6, 25, 26, 9, 4, 29, 6, 31, 12, 5, 34, 35, 6, 7, 10, 9, 14, 39, 12, 5, 8, 9, 44, 45, 6, 47, 48, 7, 8, 5, 12, 51, 20

Offset: 1

Author

Darío Clavijo, Jun 06 2024

Keywords

• nonn

Comments

This is "s - t" in Hart's factoring algorithm.

The quantities found have s^2 - t^2 = (s-t)*(s+t) = n*i when n >= 3 and Hart notes that g = gcd(s-t, n) is a nontrivial factor of n (when n is composite).

Examples

			For n=9, i=1, s=ceiling(sqrt(9*1))=3 and m=0 then s-floor(sqrt(m))=3-0=3, so a(9)=3.
Also gcd(9, 3) gives a divisor of 3.
		

References

• S. S. Wagstaff, Jr., The Joy of Factoring, AMS, 2013, pages 119-120.

Links

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

Crossrefs

Cf. A003059, A362502.

Programs

PARI

a(n) = my(i=1,s,t); while(!issquare((s=sqrtint((n*i)-1)+1)^2 % n, &t), i++); s-t;

Python

from sympy.ntheory.primetest import is_square
from sympy.core.power import isqrt
A003059 = lambda n: isqrt((n)-1)+1
def a(n):
  i = 1
  while True:
    s = A003059(n*i)
    if is_square(m:=pow(s,2,n)):
      return s-isqrt(m)
    i+=1
print([a(n) for n in range(1, 69)])