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
Keywords
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.
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)])
Comments