cp's OEIS Frontend

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.

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