login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A309916 a(n) = N^(1/4) * log(N) / sqrt(log(log(N))) rounded to nearest integer, with N=2^n. Related to operation count of the deterministic factorization of an integer N using an improved Pollard-Strassen method. 1
3, 4, 5, 7, 10, 13, 17, 22, 28, 36, 46, 58, 73, 91, 114, 143, 178, 221, 274, 338, 418, 516, 635, 781, 959, 1177, 1443, 1766, 2161, 2641, 3225, 3936, 4800, 5849, 7123, 8669, 10545, 12819, 15576, 18916, 22961, 27859, 33786, 40958, 49631, 60119, 72795, 88113, 106618 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

The article by Costa and Harvey provides an improved unconditional deterministic complexity bound for computing the prime factorization of an integer N as O(M_int(N^(1/4)*log(N)/sqrt(log(log(N))))), where M_int(k) denotes the cost of multiplying k-bit integers. The sequence shows values of the M_int argument for N=2^n.

LINKS

Table of n, a(n) for n=2..50.

Edgar Costa, David Harvey, Faster deterministic integer factorization, arXiv:1201.2116v1 [math.NT] 10 Jan 2012.

Edgar Costa, David Harvey, Faster deterministic integer factorization, Math. Comp. 83 (2014), 339-345.

PROG

(PARI) cn(N)=N^0.25*log(N)/sqrt(log(log(N)));

for(k=2, 50, print1(round(cn(2^k)), ", "))

CROSSREFS

Cf. A309917.

Sequence in context: A288451 A236384 A073957 * A162311 A003312 A022440

Adjacent sequences:  A309913 A309914 A309915 * A309917 A309918 A309919

KEYWORD

nonn

AUTHOR

Hugo Pfoertner, Aug 23 2019

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 17:59 EST 2020. Contains 331051 sequences. (Running on oeis4.)