2014/04/08 by J. Arias de Reyna, de Reyna, J. Arias, J. van de Lune +1
Mathematics · #11A67 #11Y16 #11Y55 #68Q25 #FOS: Mathematics #Number Theory (math.NT) #math.NT #msc:11A67 #msc:11B75 #msc:11Y16 #msc:11Y55 #msc:68Q25 #secondary 11B75
paper · pdf · doi:10.48550/arxiv.1404.2183
21 pages. v2: We improved the computations to get a better bound for $α$
arxiv created 2014/04/20 · arxiv updated 2014/04/22
We present three algorithms to compute the complexity \Vert n\Vert of all natural numbers n≤ N. The first of them is a brute force algorithm, computing all these complexities in time O(N2) and space O(Nlog2 N). The main problem of this algorithm is the time needed for the computation. In 2008 there appeared three independent solutions to this problem: V. V. Srinivas and B. R. Shankar [11], M. N. Fuller [7], and J. Arias de Reyna and J. van de Lune [3]. All three are very similar. Only [11] gives an estimation of the performance of its algorithm, proving that the algorithm computes the complexities in time O(N1+β), where 1+β=log3/log2≈1.584963. The other two algorithms, presented in [7] and [3], were very similar but both superior to the one in [11]. In Section 2 we present a version of these algorithms and in Section 4 it is shown that they run in time O(Nα) and space O(Nloglog N). (Here α= 1.230175). In Section 2 we present the algorithm of [7] and [3]. The main advantage of this algorithm with respect to that in [11] is the definition of kMax in Section 2.7. This explains the difference in performance from O(N1+β) to O(Nα). In Section 3 we present a detailed description a space-improved algorithm of Fuller and in Section 5 we prove that it runs in time O(Nα) and space O(N(1+β)/2loglog N), where α=1.230175 and (1+β)/2≈0.792481.