login
This site is supported by donations 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
6, 85, 259, 527, 1177, 1963, 2881, 6403, 6887, 12319, 23701, 40363, 65473, 93011, 144377, 181429, 273487, 337499, 426347, 557983, 702157, 851927, 1044413, 1295017, 1437599, 1763537, 2211119, 2556751, 2982503, 3553027, 3853327 (list; graph; refs; listen; history; text; internal format)
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

Subsequence of A138109.

Sequence in context: A293455 A295229 A245232 * A167252 A290011 A164266

Adjacent sequences:  A284519 A284520 A284521 * A284523 A284524 A284525

KEYWORD

nonn

AUTHOR

Charles R Greathouse IV, Mar 28 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 21:23 EST 2018. Contains 299588 sequences. (Running on oeis4.)