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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284522 Worst cases for Hart's one-line factorization (OLF) method with multiplier M = 1, see comments. 1

%I

%S 6,85,259,527,1177,1963,2881,6403,6887,12319,23701,40363,65473,93011,

%T 144377,181429,273487,337499,426347,557983,702157,851927,1044413,

%U 1295017,1437599,1763537,2211119,2556751,2982503,3553027,3853327

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

%C 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 Charles R Greathouse IV, <a href="/A284522/b284522.txt">Table of n, a(n) for n = 1..214</a>

%H 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 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 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 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 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 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 (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 g(n)=for(i=1, n, if(issquare((sqrtint(i*n-1)+1)^2%n), return(i)))

%o 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 (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 g(n)=for(i=1, n, if(issquare((sqrtint(i*n-1)+1)^2%n), return(i)))

%o 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 Subsequence of A138109.

%K nonn

%O 1,1

%A _Charles R Greathouse IV_, Mar 28 2017

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 09:37 EDT 2022. Contains 353785 sequences. (Running on oeis4.)