Sums of Euler's totient function in sublinear time

Question

Related.

Given a number \$n\$, Euler's totient function, \$\varphi(n)\$ is the number of integers up to \$n\$ which are coprime to \$n\$. That is, no number bigger than \$1\$ divides both of them. For example, \$\varphi(6) = 2\$, because the only relevant numbers are \$1, 5\$. This is OEIS A000010.

We can now define the sum of euler's totient function as \$S(n) = \sum_{i=1}^{n}{\varphi(i)}\$, the sum of \$\varphi(i)\$ for all numbers from \$1\$ to \$n\$. This is OEIS A002088.

Your task is to calculate \$S(n)\$, in time sublinear in \$\mathbf{n}\$, \$o(n)\$.

Test cases

10 -> 32
100 -> 3044
123 -> 4636
625 -> 118984
1000 -> 304192
1000000 (10^6) -> 303963552392
1000000000 (10^9) -> 303963551173008414

Rules

• Your complexity must be \$o(n)\$. That is, if your algorithm takes time \$T(n)\$ for input \$n\$, you must have \$\lim_{n\to\infty}\frac{T(n)}n = 0\$. Examples of valid time complexities are \$O(\frac n{\log(n)})\$, \$O(\sqrt n)\$, \$O(n^\frac57 \log^4(n))\$, etc.
• You can use any reasonable I/O format.
• Note that due to the limited complexity you can't take the input in unary nor output in it (because then the I/O takes \$\Omega(n)\$ time), and the challenge might be impossible in some languages.
• Your algorithm should in theory be correct for all inputs, but it's fine if it fails for some of the big test cases (due to overflow or floating-point inaccuracies, for example).
• Standard loopholes are disallowed.

This is code golf, so the shortest answer in each language wins.

Answer 1

Ruby, 104 100 bytes

Ports the algorithm at https://oeis.org/A002088. -4 bytes from Jonathan Allan.

A=->n,r=({0=>0}){r[c=n]||(k=n/i=2
(j=n/k+1;c+=(j-i).*2*A[k,r]-1;k=n/i=j)while k>1
r[n]=(n*n-c+i)/2)}

Attempt This Online!

Answer 2

Charcoal, 121 99 98 bytes

⊞υＮ≔⦃⦄ηＦυＦ¬§ηι«≔ιζ≔²ε≔÷ιεδ≔⟦⟧κＷ›δ¹«≔⊕÷ιδλ¿§ηδ≧⁺×⁻λε⊖⊗§ηδζ⊞κδ≔λε≔÷ιλδ»¿κＦ⊞Ｏκι⊞υλ§≔ηι÷⁺⁻×ιιζε²»Ｉ§η⊟υ

Attempt This Online! Link is to verbose version of code. Explanation: Ports the sublinear Python solution mentioned by @CommandMaster.

⊞υＮ

Input n.

≔⦃⦄η

Set up a dictionary to cache calculated results.

Ｆυ

Loop over the values that need to be calculated.

Ｆ¬§ηι«

Verify that this value hasn't actually been calculated.

≔ιζ≔²ε≔÷ιεδ≔⟦⟧κＷ›δ¹«≔⊕÷ιδλ¿§ηδ≧⁺×⁻λε⊖⊗§ηδζ⊞κδ≔λε≔÷ιλδ»

Try to calculate the result for this value, but if any dependent values haven't yet been calculated, collect them in a list.

¿κＦ⊞Ｏκι⊞υλ

If there were any dependent values that haven't yet been calculated then add them for processing and add the current value for reprocessing.

§≔ηι÷⁺⁻×ιιζε²

Otherwise actually calculate the result for the current value.

»Ｉ§η⊟υ

Output the result for the initial value, which is always the last value to be calculated.

Edit: Saved 1 byte thanks to @JonathanAllan.

Answer 3

JavaScript (ES12), 75 bytes

Adapted from the Python code provided on OEIS.

f=(n,j=2,K)=>f[n]||=n>j?f(K=n/j|0)*(j+=J=~(n/K))-j/2+f(n,-J):n&&(n*~-n+j)/2

Attempt This Online!

Statistics

Assuming the cache is cleared after each call to f:

\$n\$	total number of calls
10	15
100	193
1000	1407
10000	9111
100000	55009

Answer 4

Rust, 161 bytes

Adapted from the Python code provided on A002088

---

Golfed version. Try it online!(TIO has no cached crate, you need to run it locally.)

use cached::proc_macro::cached;
#[cached]
fn f(n:i32)->i32{let(mut c,mut j,mut v)=(0,2,n/2);while v>1{let b=n/v+1;c+=(b-j)*(2*f(v)-1);j=b;v=n/b;}(n*(n-1)-c+j)/2}

Ungolfed version. Try it online!

use std::collections::HashMap;

struct A002088 {
    cache: HashMap<i32, i32>,
}

impl A002088 {
    fn new() -> Self {
        let mut cache = HashMap::new();
        cache.insert(0, 0);
        A002088 { cache }
    }

    fn get(&mut self, n: i32) -> i32 {
        match self.cache.get(&n) {
            Some(&result) => result,
            _ => {
                let mut c = 0;
                let mut j = 2;
                let mut k1 = n / j;
                while k1 > 1 {
                    let j2 = n / k1 + 1;
                    c += (j2 - j) * (2*self.get(k1) - 1);
                    j = j2;
                    k1 = n / j2;
                }
                let result = (n * (n - 1) - c + j) / 2;
                self.cache.insert(n, result);
                result
            }
        }
    }
}

fn main() {
    let mut a002088 = A002088::new();
    let result = a002088.get(10000);
    println!("{}", result);
}