cp's OEIS Frontend

A284522 Worst cases for Hart's one-line factorization (OLF) method with multiplier M = 1, see comments.

%I A284522 #11 Apr 05 2017 16:36:13
%S A284522 6,85,259,527,1177,1963,2881,6403,6887,12319,23701,40363,65473,93011,
%T A284522 144377,181429,273487,337499,426347,557983,702157,851927,1044413,
%U A284522 1295017,1437599,1763537,2211119,2556751,2982503,3553027,3853327
%N A284522 Worst cases for Hart's one-line factorization (OLF) method with multiplier M = 1, see comments.
%C A284522 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.
%H A284522 Charles R Greathouse IV, <a href="/A284522/b284522.txt">Table of n, a(n) for n = 1..214</a>
%H A284522 William B. Hart, <a href="http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf">A one line factoring algorithm</a>, Journal of the Australian Mathematical Society 92 (2012), pp. 61-69.
%e A284522 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.
%e A284522 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.
%e A284522 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.
%e A284522 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.
%e A284522 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.
%o A284522 (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)
%o A284522 g(n)=for(i=1, n, if(issquare((sqrtint(i*n-1)+1)^2%n), return(i)))
%o A284522 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
%o A284522 (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)
%o A284522 g(n)=for(i=1, n, if(issquare((sqrtint(i*n-1)+1)^2%n), return(i)))
%o A284522 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
%Y A284522 Subsequence of A138109.
%K A284522 nonn
%O A284522 1,1
%A A284522 _Charles R Greathouse IV_, Mar 28 2017