[SDOI2018] Old Exam Problems

The question

Can the source-listed reference complexity O(n sqrt(n) log^3 n) be substantially improved?

Algorithmic frontier

Reference frontier: $\mathcal{O}\!\left(n \sqrt{n} \log^{3} n\right)$
Latest reported AI result: $\mathcal{O}\!\left(n \log^{3} n \Psi(n)\right)$

Normalized growth proxy · not benchmark data

This compares source-reported bounds; it is not a correctness or novelty finding.

Results

2026-09-12

Claimed result: $\mathcal{O}\!\left(n \log^{3} n \Psi(n)\right)$

AI / model: ChatGPT

Reported method

The page expands tau(ijk) into five per-prime corrections, yielding a fourfold squarefree sum over d, r, s, t; it enumerates t by divisor blocks so each block needs only one coprime-restricted Mobius interval sum, and proves that the extra factor Psi(N) is N^{o(1)}, giving O(N log^3 N · Psi(N)) = O(N^{1+o(1)}). Derivation only — no code.

Verification

Source: Source reviewed
Theory: Theory not checked
Implementation: Theory only · code pending
Prior art: Prior art not reviewed

The result page was opened and compared with the collection claim. Legacy audit state: audited_public.

The table cell says O(n log^3 n Ψ(n)) while the QOJ page title says O(N^{1+o(1)}). Reading the body resolves this: it states the algorithm runs in O(N log^3 N · Psi(N)) with Psi(N) = N^{o(1)}, so the two are the same claim in explicit and simplified notation. Not a contradiction, hence not marked disputed.