|
|
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.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
LINKS
|
|
|
PROG
|
(PARI) cn(N)=N^0.25*log(N)/sqrt(log(log(N)));
for(k=1, 33, print1(round(cn(10^k)), ", "))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|