OFFSET
1,1
COMMENTS
Hart's algorithm begins with trial division to the cube root of the number and a check for squares, so numbers factored by these means are removed (leaving A138109). The remaining numbers are compared on the basis of the number of steps Hart's algorithm requires to factor them; new records are members of this sequence.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..214
William B. Hart, A one line factoring algorithm, Journal of the Australian Mathematical Society 92 (2012), pp. 61-69.
EXAMPLE
OLF factors 6 on step 2: s = ceil(sqrt(2*6)) = 4, s^2 = 4 mod 6; 4 = 2^2, gcd(6, 4-2) = 2.
OLF factors 85 on step 3: s = ceil(sqrt(3*85)) = 16, s^2 = 1 mod 85; 1 = 1^2, gcd(85, 16-1) = 5.
OLF factors 259 on step 5: s = ceil(sqrt(5*259)) = 36, s^2 = 1 mod 259; 1 = 1^2, gcd(259, 36-1) = 7.
OLF factors 527 on step 8: s = ceil(sqrt(8*527)) = 65, s^2 = 9 mod 527; 9 = 3^2, gcd(527, 65-3) = 31.
OLF factors 1177 on step 9: s = ceil(sqrt(9*1177)) = 103, s^2 = 16 mod 1177; 16 = 4^2, gcd(1177, 103-4) = 11.
PROG
(PARI) listA138109(lim)=if(lim<6, return([])); my(v=List([6])); forprime(p=3, sqrtint(1+lim\=1)-1, forprime(q=p+2, min(p^2-2, lim\p), listput(v, p*q))); Set(v)
g(n)=for(i=1, n, if(issquare((sqrtint(i*n-1)+1)^2%n), return(i)))
list(lim)=my(u=Vecsmall(listA138109(lim)), v=List(), r, t); for(i=1, #u, t=g(u[i]); if(t>r, r=t; listput(v, u[i]))); u=0; Vec(v) \\ Charles R Greathouse IV, Mar 28 2017
(PARI) make(from, to)=my(v=List()); from=ceil(from); forprime(p=max(sqrtnint(from, 3)+1, 3), sqrtint(1+to\=1)-1, forprime(q=max(p+2, from/p), min(p^2-2, to\p), listput(v, p*q))); Set(v)
g(n)=for(i=1, n, if(issquare((sqrtint(i*n-1)+1)^2%n), return(i)))
list(lim)=my(u, v=List([6]), r, t, step=10^7); forstep(n=85, lim, step, u=make(n, min(n+step-1, lim)); for(i=1, #u, t=g(u[i]); if(t>r, r=t; listput(v, u[i]); print1(u[i]", ")))); Vec(v) \\ Charles R Greathouse IV, Apr 03 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Charles R Greathouse IV, Mar 28 2017
STATUS
approved