# Sums of Euler's totient function in sublinear time

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.

• @doubleunary There's a sublinear Python solution in the OEIS page Sep 15, 2023 at 17:32
• Are we allowed to assume all basic integer operations are O(1)? (even though in reality they are necessarily O(log(n)) for arbitrary-precision integers) Sep 16, 2023 at 10:07
• @pxeger No, but $O(\log n)$ shouldn't be problematic since all numbers involved are $O(n^2)$ Sep 16, 2023 at 10:37

# 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!

• Could you start with c=n and end with (n*n-c+i)/2 for -2 bytes? Sep 15, 2023 at 20:35
• @JonathanAllan good catch. This also let me wrap the assignment inside the cache lookup for an extra -2. Sep 15, 2023 at 21:51

# Charcoal, 12199 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.

• Like my comment under Value Ink's answer, I think you could start with z=i and square i avoiding the Decremented(i) - ATO Sep 15, 2023 at 20:57

# 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

# 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);
}

• Doesn't the golfed version need the cache to make it run in sublinear time?
– Neil
Sep 17, 2023 at 7:39
• @Neil Thanks for your comment, I have corrected it. Sep 18, 2023 at 1:54