A309917 a(n) = N^(1/4) * log(N) / sqrt(log(log(N))) rounded to nearest integer, with N=10^n. Related to operation count of the deterministic factorization of an integer N using an improved Pollard-Strassen method.

4, 12, 28, 62, 131, 270, 544, 1079, 2117, 4111, 7923, 15167, 28873, 54700, 103200, 193993, 363492, 679141, 1265643, 2353204, 4366164, 8085640, 14947693, 27589371, 50847817, 93586753, 172032816, 315865168, 579322476, 1061447338, 1942961421, 3553392144, 6493197325

Offset

1,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=10^n.

References

See A309916.

Links

Table of n, a(n) for n=1..33.

Prog

(PARI) cn(N)=N^0.25*log(N)/sqrt(log(log(N)));
for(k=1, 33, print1(round(cn(10^k)), ", "))

Crossrefs

Cf. A309916.

Sequence in context: A173033 A339124 A317233 * A034508 A173380 A002932

Adjacent sequences: A309914 A309915 A309916 * A309918 A309919 A309920

Keyword

nonn

Author

Hugo Pfoertner, Aug 23 2019

Status

approved