|
%I #54 Jun 22 2024 08:12:16
%S 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,
%T 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,
%U 45,6,47,48,7,8,5,12,51,20
%N 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.
%C This is "s - t" in Hart's factoring algorithm.
%C 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).
%D S. S. Wagstaff, Jr., The Joy of Factoring, AMS, 2013, pages 119-120.
%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.
%e 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.
%e Also gcd(9, 3) gives a divisor of 3.
%o (Python)
%o from sympy.ntheory.primetest import is_square
%o from sympy.core.power import isqrt
%o A003059 = lambda n: isqrt((n)-1)+1
%o def a(n):
%o i = 1
%o while True:
%o s = A003059(n*i)
%o if is_square(m:=pow(s,2,n)):
%o return s-isqrt(m)
%o i+=1
%o print([a(n) for n in range(1, 69)])
%o (PARI)
%o a(n) = my(i=1,s,t); while(!issquare((s=sqrtint((n*i)-1)+1)^2 % n, &t), i++); s-t;
%Y Cf. A003059, A362502.
%K nonn
%O 1,2
%A _Darío Clavijo_, Jun 06 2024
|
