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. 1
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 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). REFERENCES S. S. Wagstaff, Jr., The Joy of Factoring, AMS, 2013, pages 119-120. LINKS Table of n, a(n) for n=1..68. William B. Hart, A One Line Factoring Algorithm, J. Aust. Math. Soc. 92 (2012), 61-69. EXAMPLE 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. PROG (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)]) (PARI) a(n) = my(i=1, s, t); while(!issquare((s=sqrtint((n*i)-1)+1)^2 % n, &t), i++); s-t; CROSSREFS Cf. A003059, A362502. Sequence in context: A325622 A060145 A358997 * A257806 A035391 A242552 Adjacent sequences: A373458 A373459 A373460 * A373462 A373464 A373465 KEYWORD nonn AUTHOR Darío Clavijo, Jun 06 2024 STATUS approved

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 August 5 04:43 EDT 2024. Contains 374935 sequences. (Running on oeis4.)