[Problem proposal] Sum of Multiplicative Function

[FR-vdash-bot]

Problem

Given a multiplicative function $f(x)$, $f(p^e) = ae + bp$. Print $\displaystyle \sum_{i=1}^N f(i) \bmod 469762049$.

Constraint

• $1 \leq N \leq 10^{13}$

Solution / Reference

1. Ren Zhizhou (任之洲)’s method (洲阁筛) (Chinese content): Several methods for summing multiplicative functions (积性函数求和的几种方法). Proceedings of the Chinese National Team Candidates for the 2016 Olympiad in Informatics (2016年信息学奥林匹克中国国家队候选队员论文集)
2. Introduction to Min_25 sieve and some other algorithm (Chinese content): Some special arithmetic function summation problems (一些特殊的数论函数求和问题). Proceedings of IOI2018 China National Candidate Team (IOI2018中国国家候选队论文集)
3. Min_25's newer method: https://web.archive.org/web/20211009144526/https://min-25.hatenablog.com/entry/2018/11/11/172216
4. Zhu Zhenting (朱震霆)’s method (Chinese content): https://blog.csdn.net/whzzt/article/details/104105025
5. On the Min25 sieve and extensions / SPOJ ASSIEVE - Codeforces
6. Reinterpretation of previous methods (Chinese content): https://negiizhao.blog.uoj.ac/blog/7165
7. Further optimization of previous methods (Chinese content): https://negiizhao.blog.uoj.ac/blog/8961
8. $\tilde O(\sqrt N)$ method using FFT: Computing $\pi(N)$: An elementary approach in $\tilde O(\sqrt N)$ time
9. Zhou Kangyang (周康阳)’s method (An independently discovered method similar to 8.) (Chinese content): Some progress on summing multiplicative functions (关于积性函数求和问题的一些进展). Proceedings of IOI2024 China National Training Team (IOI2024中国国家集训队论文集)
10. Further optimization of 8. and 9. (Chinese content): https://negiizhao.blog.uoj.ac/blog/9019

(The titles of Proceedings of the IOI Chinese National Candidate Team are different every year, but they are indeed a series.)

Note

This problem has been uploaded to https://qoj.ac/problem/8327 for experimenting with $\tilde O(\sqrt N)$ methods. This method needs to enumerate factors to fix errors, it's bad implementations may error on specific inputs. So there may be multiple test cases in a single test file. The (badly written) generator is here.

It asks for every $\displaystyle \sum_{i=1}^{\left\lfloor\frac N n\right\rfloor} f(i)$, but some methods can only compute a single partial sum. Also, some methods may be too slow to compute for $N = 10^{13}$. So we may need different versions of this problem (or do not add the $10^{13}$ version?).

I used 469762049 instead of 998244353 because it's easier to compute very long convolutions, which may be needed in $\tilde O(\sqrt N)$ methods.

[maspypy]

Related Problems in Library Checker

• https://judge.yosupo.jp/problem/counting_squarefrees
• https://judge.yosupo.jp/problem/sum_of_totient_function

[maspypy]

Thank you for proposing new problems, and many References!! I only know that they can be computed in O(N^{2/3}) time, so I want to study them soon.

I can't access some of the references. Can you publish them?

I know that some algorithm can compute single partial sum, and some algorithm can compute all $\lfloor N/n \rfloor$-th partial sums. And both can be used to solve problems in competitive programming. So I think it is ok to put both version of the problem.

[FR-vdash-bot]

I forgot to change the permissions. It should be fine now.

By the way, from the practical point of view, experiments on QOJ show that the current $\tilde O(\sqrt n)$ methods are much slower than the $O(n^{2/3} \log^{-4/3} n)$ method below $10^{13}$.

[maspypy]

I have roughly understood the method to calculate the prefix sum in $\tilde{O}(N^{1/2})$ time. However, I still don't understand the method to calculate all $\lfloor N/i\rfloor$-th sum in $\tilde{O}(N^{1/2})$ time. Which part of which resource would be helpful for this method?

[FR-vdash-bot]

In the framework of my method, all you need is to compute exp. After computing an approximation for each sum using exp of power series, use 2.4 of 8 or 4.1 of 9 for error correction.

[maspypy]

Ah, I see.

I first understood how to correct errors in summing up to $n$. Now I understand that the method can be applied to calculate all $\lfloor n/i\rfloor$-th sums. thank you.