Computation of the Totient Summatory Function

Lucas Augustus Brown

REVIEW 3 major objections 5 minor 10 references

Computation of the Totient Summatory Function

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes an algorithm that computes the totient summatory function in nearly n^{2/3} time with only cube-root memory, and reports a new value at 10^19.

desk verdict Genuinely useful space-reduction trick and a new Φ(10^19), but the key time bound depends on an integral split in Lemma 14 that doesn't work as written. read the letter →

arxiv 2506.07386 v1 pith:LXH5YQBM submitted 2025-06-09 math.NT

Lucas Augustus Brown This is my paper

classification math.NT MSC 11Y1611-0411A2511Y5511Y70

keywords totientsummatoryfunctionEuler'sMertensMöbiusDirichlethyperbolamethodsegmentedsievespace-timetradeoffA064018

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that the totient summatory function $\Phi(n)=\sum_{k\le n}\phi(k)$ can be computed in $\widetilde{\Theta}(n^{2/3})$ time while storing only $\widetilde{\Theta}(n^{1/3})$ integers, a cube-root memory footprint. The route is to take the known Mertens-first Dirichlet-hyperbola algorithm, which needs $\Theta(\sqrt n)$ storage, and reorganize its loops so that Mertens values are accumulated in blocks and flushed into a short array $M'$ of length about $n^{1/3}$ instead of being kept all at once. A reader should care because the memory reduction is what lets the computation advance from the desktop-limited value $\Phi(10^{18})$ to the new value $\Phi(10^{19})=30396355092701331435065976498046398788$, reported after two agreeing runs. The paper's own analysis sets the optimal balance at $a=\Theta((n/\ln\ln n)^{2/3})$, giving $\Theta(n^{2/3}(\ln\ln n)^{1/3})$ time and $\Theta(n^{1/3}(\ln\ln n)^{2/3})$ space.

What carries the argument

The load-bearing object is the short accumulator array $M'$, indexed from 1 to $b$, which holds the partial contributions to the $Y$ sum in the hyperbola formula. The carrying identity is $\Phi=\mu*\mathrm{id}$ decomposed by the Dirichlet hyperbola method into an $X$ sum over Möbius values, a $Y$ sum over Mertens values, and an overlap correction $Z$; the workhorse is the loop reordering that turns the phase-3 Mertens loop into phase-1 and phase-2 updates, so that no Mertens value beyond $b$ needs to be kept. When a batch of saved Mertens values fills the temporary array $M$, condition (4) determines which pairs $(y,t)$ receive each stored value, and the batch is flushed into $M'$.

What would settle it

Instrument a run of Algorithm 13 to count hits to line 13.38 and to record the saved Mertens indices x and batch bounds A and B; if the total hit count differs from Theta($\sqrt$(n) ln b) by more than a constant factor, the time bound in Theorem 7 does not follow. A separate direct check is to compute Phi(n) by brute-force summation for n up to $10^{8}$ and compare with the algorithm's output; any mismatch would refute the claimed correctness.

Watch

Extended reading notes

Core claim

The central claim is Theorem 7: with $a=\Theta((n/\ln\ln n)^{2/3})$, Algorithm 13 evaluates the identity $\Phi(n)=\sum_{x\le a}\mu(x)\lfloor n/x\rfloor(\lfloor n/x\rfloor+1)/2 + \sum_{y\le b} y\,M(\lfloor n/y\rfloor) - b(b+1)M(a)/2$ in $\Theta(n^{2/3}(\ln\ln n)^{1/3})$ time and $\Theta(n^{1/3}(\ln\ln n)^{2/3})$ space, where $M(k)=\sum_{i\le k}\mu(i)$ is the Mertens function and $b=\lfloor n/a\rfloor$. The discovery is that the $\Theta(\sqrt n)$ arrays of stored Möbius and Mertens values in the earlier algorithm can be replaced by an array $M'$ of length $b$ plus a temporary batch array $M$ of length $b$, because every contribution that the third phase needs can be precomputed into $M'$ during the first two phases by summing over $x$ first rather than over $y$. That reorganization is what makes the reported $\Phi(10^{19})$ computation feasible in less than nine days and about 6.6 GB.

Load-bearing premise

The claimed running time depends on the unproved approximation that the k-th Mertens value saved during the middle phase has index near n/(sqrt(n)-k), and the algorithm's correctness is stated as evident from its construction rather than proved.

Editorial extensions

If this is right

With optimal parameters, Algorithm 13 achieves $\Theta(n^{2/3}(\ln\ln n)^{1/3})$ time and $\Theta(n^{1/3}(\ln\ln n)^{2/3})$ space, so the asymptotic time loss relative to the square-root-space version is only a $(\ln\ln n)^{1/3}$ factor.
The new value $\Phi(10^{19})=30396355092701331435065976498046398788$ extends the sequence by one term and was verified by running the computation twice; the values at $10^{13},\dots,10^{18}$ match the previously published ones.
The space reduction means the algorithm can run in a few gigabytes rather than needing the $\Theta(\sqrt n)$ integers that put $10^{19}$-scale compute out of reach of a desktop machine.
The phase-3 loop simplification, using the bound $n/(b+1)\ge\lfloor v/t\rfloor$ to break early, makes the final Mertens sweep cost only $\Theta(b\ln b)$ time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same block-flush idea should transfer to other summatory functions evaluated by the Dirichlet hyperbola method with a Mertens-type prefix, potentially lowering their space from square-root to cube-root scale at a log-log factor cost; the paper only applies it to $\Phi$.
The large wall-clock jump between $10^{18}$ and $10^{19}$ suggests multiword arithmetic dominates at $10^{19}$; if so, a tighter big-integer implementation should bring the runtime back toward the asymptotic ratio, which is a testable prediction.
Lemma 5's saved-index approximation $x\approx n/(\sqrt n-k)$ can be checked empirically by instrumenting phase 2; such a check would either confirm the $\Theta(\sqrt n\ln b)$ bound or pinpoint where the proof needs repair.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the algorithmic idea is real, the new Φ(10^19) is a nice data point, but the proof of the headline time bound has a concrete error in Lemma 14, so I wouldn't take the Θ(n^{2/3}(ln ln n)^{1/3}) claim at face value yet.

What's genuinely new: the space reduction from Θ(√n) to Θ(n^{1/3}) by batching Mertens values and swapping loop order in the Macris algorithm. That's a clever, practical trick. The paper is honest about its lineage, and the small-n values match OEIS. The 10^19 computation was run twice and the timings scale roughly as claimed.

The soft spot is in the analysis. Lemma 4's bound for line 13.27 is delegated to Lemma 14. In the proof of Lemma 14, after substituting u = bχ + 1 and setting T = n/(u-b)^2, the text splits the t-integral over [1,b] as ∫_b^T ... + ∫_T^1 ... . That is not a valid split. For most u in the range, T ≫ b, so the first integral ranges outside [1,b] and the second has reversed limits. The displayed Θ(a ln(n^2 a^{-3})) total therefore is not actually derived. Since Lemma 4 is the load-bearing step for the upper bound in Theorem 7, the headline time complexity is unproven as written. It may be true, but the argument doesn't show it.

The reader's worry about Lemma 5 is not the real issue; the saved phase-2 values are exactly the consecutive floor(n/x) values, and that contribution is only O(√n ln b). The bigger gap is the integral error and the fact that correctness is asserted 'evident by its development' rather than demonstrated. Also, no code is shipped, which makes it harder to check the finer details of the loops.

Who should read this: anyone working on practical algorithms for summatory functions. The batching idea is worth borrowing, and the new value is a real data point. But the paper needs a corrected Lemma 14 (or a different proof) before I'd trust the asymptotic claim.

Recommendation: send it to peer review. A referee who checks Lemma 14 carefully can tell whether the bound is repairable. This is not a desk reject; it's a paper with a promising core and a proof gap that needs real work.

Referee Report

3 major / 5 minor

Summary. The paper presents an algorithm (Algorithm 13) for computing the totient summatory function Φ(n) in claimed time Θ(n^{2/3}(ln ln n)^{1/3}) and space Θ(n^{1/3}(ln ln n)^{2/3}), starting from an existing Mertens-first Dirichlet-hyperbola algorithm and progressively reordering its loops to eliminate the need to store the Mertens array M′ beyond index b. The author reports a new computation Φ(10^19) = 30396355092701331435065976498046398788, alongside reproductions of known values for 10^13 through 10^18.

Significance. If the complexity claims and the computed value are correct, the paper makes a useful contribution: it lowers the space requirement from Θ(n^{1/2}) to soft-Θ(n^{1/3}) with essentially the same soft-O(n^{2/3}) runtime, and it provides a new, independently reproducible computational data point. The paper is honest in reporting wall-clock times and memory, and the verification against OEIS A064018 for smaller n strengthens confidence in the implementation. The algorithm is also described with enough pseudocode detail that an expert could reimplement it. However, the rigorous derivation of the central time bound is incomplete, and the correctness of the batched loop transformations is asserted rather than proved, so the significance is conditional on a repaired analysis.

major comments (3)

[Lemma 14 (Section 4)] The proof of Lemma 14, which provides the crucial estimate Θ(a ln(n^2 a^{-3})) for line 13.27, contains an invalid integral manipulation. After the substitution u = bχ + 1 and the definition T = n/(u−b)^2, the text states that 'for lesser t, the first argument prevails' and then splits the inner integral as ∫_b^T ... dt + ∫_T^1 ... dt. But for the relevant range u ∈ [1+2b, 1+√n], T is in fact smaller than b throughout: at u = 1+2b, T ≈ n/b^2 = a^2/n ≈ n^{1/3}(ln ln n)^{−4/3}, while b ≈ n^{1/3}(ln ln n)^{2/3}; at u = 1+√n, T ≈ 1. Hence the first integral should run from T to b, and the second from 1 to T; writing the limits in reverse order changes the sign. The subsequent equality chain treats these oriented integrals as positive quantities, so the displayed Θ(a ln(n^2 a^{-3})) is not obtained by a valid sequence of estimates. Since Lemma 14 is the load-bearing estimate that prevents line 13.27 from exceeding the target Θ(n^{2/3}(ln ln n)^{1/3}) time, Theorem 7's upper bound is currently unproved.
[Theorem 7 proof (Section 4)] The proof of Theorem 7 states that 'the correctness of the algorithm is evident by its development' and provides no formal equivalence proof for the batched loop reorderings. This matters because the transformations leading from Algorithm 1 to Algorithm 13 are nontrivial: Algorithms 9, 12, and 13 replace inner loops with batched updates that change the order of accumulation and introduce conditions such as (4), and line 13.38 is not visibly equivalent to the original line 10.50. The paper should supply an invariant or a bijection between the pairs (y, t, ℓ) processed in the batched versions and the pairs (y, x) in the original loop, so that a reader can verify that each M′ entry receives exactly the same set of contributions.
[Lemma 5 (Section 4)] The proof of Lemma 5 relies on the approximation that the k-th Mertens value saved during phase 2 has index x ≈ n/(√n − k), and that batches therefore have A ≈ √n − b(j−1) and B ≈ √n − bj. No rigorous error bound or justification for this approximation is given. Since the total contribution of line 13.38 is claimed to be Θ(√n ln b), which is below the target bound, a rigorous bound with a constant factor would likely suffice; nevertheless, the current proof is heuristic and does not establish the stated Θ(√n ln b) claim in the form used.

minor comments (5)

[Section 1.1 and throughout] The notation eΘ is used without a formal definition; please define it explicitly (e.g., up to polylogarithmic factors).
[Algorithm 1 line 1.1 and Algorithm 13 line 13.1] The assignment a ← ⌊eΘ(n^{2/3})⌋ is not a concrete algorithmic instruction, since eΘ hides constant and logarithmic factors. For an algorithm to be reproducible, a should be set to a specific function, for example a = ⌊c (n/ln ln n)^{2/3}⌋ with an explicit constant c, and the analysis should state how the constant affects the Θ bounds.
[Section 1] The introductory formula writes Φ(n) = Σ_{k=1}^n φ(n); this is a typo and should be φ(k).
[Throughout] There are several typographical inconsistencies, including 'M¨obius' (encoding artifacts), 'parmeter' in the proof of Theorem 7, and 'modifed' in Section 2. A careful proofreading pass is recommended.
[Section 5, Table 1] It would be helpful to state the exact value of a used for each run, or at least the asymptotic parameter choice, so that the reported timings can be interpreted and the run is reproducible.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithm's claimed complexity and the new Φ(10^19) value are produced by independent arithmetic identities and an external starting point, not by fitting or self-citation.

full rationale

The paper's derivation chain is not circular. The starting point is the Dirichlet hyperbola identity (1), ϕ = µ ∗ I, which is a standard convolution identity, and the Mertens-first algorithm is explicitly attributed to an external blog post [6]. No result is defined in terms of the target Φ(n), and no fitted parameter is renamed as a prediction: the only free parameter is the loop cutoff a, whose value Θ((n/ln ln n)^{2/3}) is chosen by balancing the independently counted costs of sieving (Lemma 1) and line 13.16 (Lemma 2). The new numerical value Φ(10^19) is an output of the program, not an input; the program is checked against previously known OEIS values in Table 1. The author has no self-citations, so no self-citation chain or imported uniqueness theorem supports the conclusion. The assertion in Theorem 7 that correctness is 'evident by its development' is an under-supported proof claim, and the possible flaw in Lemma 14 identified by a skeptical reading is a mathematical correctness concern, but neither is a case of a conclusion reducing to its own inputs. Under the hard rules, unsupported assertions and possible gaps are not circularity; therefore score 0 is appropriate.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The core computation relies only on standard number-theoretic identities and sieve results. The split parameter a is an analytic optimization choice rather than a fitted constant. The non-standard assumptions are the unproved equivalence of the batched loops and the approximate distribution of saved Mertens values, which are the main sources of uncertainty in the complexity proof.

free parameters (1)

a (Dirichlet hyperbola split point) = Θ((n/ln ln n)^{2/3}); exact constant not disclosed
Selecting a balances the Θ(a ln ln a) Möbius sieve time against the Θ(n/√a) hyperbola-loop time. The analysis assumes this specific asymptotic order, and the implementation must choose a concrete value, which is not reported in the paper.

assumptions (4)

standard math φ = μ * I, with I(x)=x, and the Dirichlet hyperbola method
Used to derive formula (1) for Φ(n) in Section 2.1.
domain assumption A segmented sieve can generate μ(1..a) in Θ(a ln ln a) time and Θ(√a) space
Invoked in Lemma 1 and at line 13.4 as a standard result.
ad hoc to paper The batched loop reorderings in Algorithms 9, 12, and 13 exactly reproduce the contributions of the original loops in Algorithm 1
Correctness of the algorithm is asserted as 'evident by its development' in Theorem 7, but no formal equivalence proof is given.
ad hoc to paper The k-th Mertens value saved during phase 2 has index approximately n/(√n − k)
Used without proof in Lemma 5 to bound the cost of line 13.38; the paper states it is approximate.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Computation of the Totient Summatory Function." pith.science (2026). https://pith.science/paper/LXH5YQBM

@misc{pith2026250607386,
  author       = {Pith},
  title        = {Pith review of: Computation of the Totient Summatory Function},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LXH5YQBM}},
  note         = {Machine review of arXiv:2506.07386}
}

abstract

An algorithm is devised for computing $\Phi(n) = \phi(1) + \phi(2) + \cdots + \phi(n)$ in time $\widetilde{\Theta}(n^{2/3})$ and space $\widetilde{\Theta}(n^{1/3})$. The starting point is an existing algorithm based on the Dirichlet hyperbola method and the Mertens function. The algorithm is then used to compute $\Phi(10^{19}) = 30396355092701331435065976498046398788$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 8 canonical work pages

[1]

In the zeroth phase, lines 1.1–1.6 initialize the computation

work page
[2]

In the first phase, covered in lines 1.7–1.13, we sieve the M ¨obius function up to ⌊√n⌋, ac- cumulate its values to compute the Mertens function, save bothµ and M, and accumulate terms into X

work page
[3]

We continue to accumulate M ¨obius values to compute Mertens values, and we continue to accumulate terms into X, but we do not save any µ, and only some Mertens values are saved

In the second phase, covered in lines 1.7–1.10 and 1.29–1.40, we continue the sieve up toa. We continue to accumulate M ¨obius values to compute Mertens values, and we continue to accumulate terms into X, but we do not save any µ, and only some Mertens values are saved. As the final act of phase 2, we compute Z. At this point, X and Z are fully evaluated,...

work page
[4]

and µ(x) ̸= 0

In the third phase, lines 1.42–1.52 feed the stored M ¨obius and Mertens values into (2) to compute the remaining Mertens values in order of increasing argument—that is, we first compute M (n/b), then M (n/(b − 1)), then ..., and finally M (n). As each Mertens value is computed, a term from Y becomes available, and we evaluate it accordingly. 2025–07–21 P...

work page 2025
[5]

Computing the summation of the M¨obius function

Marc Del ´eglise and Jo¨ol Rivat. “Computing the summation of the M¨obius function”. In:Ex- perimental Mathematics 5.4 (1996), pages 291–295. ISSN : 1944-950X. DOI: 10.1080/10586458. 1996 . 10504594. URL: https : / / projecteuclid . org / euclid . em / 1047565447(cited on pages 2, 3)

doi:10.1080/10586458 1996
[6]

Summing µ(n): a faster elementary algo- rithm

Harald Andr ´es Helfgott and Lola Thompson. “Summing µ(n): a faster elementary algo- rithm”. In: Research in Number Theory 9.6 (2023). ISSN : 2363-9555. DOI: 10.1007/s40993- 022 - 00408 - 8. arXiv: 2101 . 08773v4 [math.NT]. URL: https : / / link . springer . com / article/10.1007/s40993-022-00408-8 (cited on page 3)

work page doi:10.1007/s40993- 2023
[7]

Personal communication

Dean Hirsch, Ido Kessler, and Uri Mendlovic. Personal communication. May 1, 2025 (cited on page 2)

work page 2025
[8]

Computing π(N ): An elementary approach in ˜O( √ N ) time

Dean Hirsch, Ido Kessler, and Uri Mendlovic. “Computing π(N ): An elementary approach in ˜O( √ N ) time”. In: Mathematics of Computation (2022). ISSN : 1088-6842. DOI: 10 . 1090 / mcom/4039. arXiv: 2212.09857 [math.NT]. URL: https://www.ams.org/journals/mcom/ 0000-000-00/S0025-5718-2024-04039-5/ (cited on page 2)

arXiv 2022

Show all 10 references

[9]

Dirichlet convolution

Oleksandr Kulkov. Dirichlet convolution. Part 1: Fast prefix sum computations . 2023. URL: https://codeforces.com/blog/entry/117635 (cited on page 1)

2023
[10]

Summing Multiplicative Functions (Pt

Griffin Macris. Summing Multiplicative Functions (Pt. 1) . 2023. URL: https : / / gbroxey . github.io/blog/2023/04/30/mult-sum-1.html (cited on pages 1, 4). 2020 Mathematics Subject Classification: Primary 11Y16; Secondary 11-04, 11A25, 11Y55, 11Y70. Keywords: totient, totient...

2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

In the zeroth phase, lines 1.1–1.6 initialize the computation

work page

[2] [2]

In the first phase, covered in lines 1.7–1.13, we sieve the M ¨obius function up to ⌊√n⌋, ac- cumulate its values to compute the Mertens function, save bothµ and M, and accumulate terms into X

work page

[3] [3]

We continue to accumulate M ¨obius values to compute Mertens values, and we continue to accumulate terms into X, but we do not save any µ, and only some Mertens values are saved

In the second phase, covered in lines 1.7–1.10 and 1.29–1.40, we continue the sieve up toa. We continue to accumulate M ¨obius values to compute Mertens values, and we continue to accumulate terms into X, but we do not save any µ, and only some Mertens values are saved. As the final act of phase 2, we compute Z. At this point, X and Z are fully evaluated,...

work page

[4] [4]

and µ(x) ̸= 0

In the third phase, lines 1.42–1.52 feed the stored M ¨obius and Mertens values into (2) to compute the remaining Mertens values in order of increasing argument—that is, we first compute M (n/b), then M (n/(b − 1)), then ..., and finally M (n). As each Mertens value is computed, a term from Y becomes available, and we evaluate it accordingly. 2025–07–21 P...

work page 2025

[5] [5]

Computing the summation of the M¨obius function

Marc Del ´eglise and Jo¨ol Rivat. “Computing the summation of the M¨obius function”. In:Ex- perimental Mathematics 5.4 (1996), pages 291–295. ISSN : 1944-950X. DOI: 10.1080/10586458. 1996 . 10504594. URL: https : / / projecteuclid . org / euclid . em / 1047565447(cited on pages 2, 3)

doi:10.1080/10586458 1996

[6] [6]

Summing µ(n): a faster elementary algo- rithm

Harald Andr ´es Helfgott and Lola Thompson. “Summing µ(n): a faster elementary algo- rithm”. In: Research in Number Theory 9.6 (2023). ISSN : 2363-9555. DOI: 10.1007/s40993- 022 - 00408 - 8. arXiv: 2101 . 08773v4 [math.NT]. URL: https : / / link . springer . com / article/10.1007/s40993-022-00408-8 (cited on page 3)

work page doi:10.1007/s40993- 2023

[7] [7]

Personal communication

Dean Hirsch, Ido Kessler, and Uri Mendlovic. Personal communication. May 1, 2025 (cited on page 2)

work page 2025

[8] [8]

Computing π(N ): An elementary approach in ˜O( √ N ) time

Dean Hirsch, Ido Kessler, and Uri Mendlovic. “Computing π(N ): An elementary approach in ˜O( √ N ) time”. In: Mathematics of Computation (2022). ISSN : 1088-6842. DOI: 10 . 1090 / mcom/4039. arXiv: 2212.09857 [math.NT]. URL: https://www.ams.org/journals/mcom/ 0000-000-00/S0025-5718-2024-04039-5/ (cited on page 2)

arXiv 2022