The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 2

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 8 00:04 EDT 2024. Contains 375749 sequences. (Running on oeis4.)