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.

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

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: A236384 A351741 A073957 * A162311 A003312 A022440

Adjacent sequences: A309913 A309914 A309915 * A309917 A309918 A309919

Keyword

nonn

Author

Hugo Pfoertner, Aug 23 2019

Status

approved