Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #6 Aug 23 2019 14:12:13
%S 3,4,5,7,10,13,17,22,28,36,46,58,73,91,114,143,178,221,274,338,418,
%T 516,635,781,959,1177,1443,1766,2161,2641,3225,3936,4800,5849,7123,
%U 8669,10545,12819,15576,18916,22961,27859,33786,40958,49631,60119,72795,88113,106618
%N 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.
%C 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.
%H Edgar Costa, David Harvey, <a href="https://arxiv.org/abs/1201.2116">Faster deterministic integer factorization</a>, arXiv:1201.2116v1 [math.NT] 10 Jan 2012.
%H Edgar Costa, David Harvey, <a href="https://doi.org/10.1090/S0025-5718-2013-02707-X">Faster deterministic integer factorization</a>, Math. Comp. 83 (2014), 339-345.
%o (PARI) cn(N)=N^0.25*log(N)/sqrt(log(log(N)));
%o for(k=2,50,print1(round(cn(2^k)),", "))
%Y Cf. A309917.
%K nonn
%O 2,1
%A _Hugo Pfoertner_, Aug 23 2019