6
\$\begingroup\$

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ @doubleunary There's a sublinear Python solution in the OEIS page \$\endgroup\$ Sep 15, 2023 at 17:32
  • \$\begingroup\$ 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) \$\endgroup\$
    – pxeger
    Sep 16, 2023 at 10:07
  • \$\begingroup\$ @pxeger No, but \$O(\log n)\$ shouldn't be problematic since all numbers involved are \$O(n^2)\$ \$\endgroup\$ Sep 16, 2023 at 10:37

4 Answers 4

3
\$\begingroup\$

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!

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

Charcoal, 121 99 98 bytes

⊞υN≔⦃⦄ηFυF¬§ηι«≔ιζ≔²ε≔÷ιεδ≔⟦⟧κW›δ¹«≔⊕÷ιδλ¿§ηδ≧⁺×⁻λε⊖⊗§ηδζ⊞κδ≔λε≔÷ιλδ»¿κF⊞Oκι⊞υλ§≔ηι÷⁺⁻×ιιζε²»I§η⊟υ

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

⊞υN

Input n.

≔⦃⦄η

Set up a dictionary to cache calculated results.

Fυ

Loop over the values that need to be calculated.

F¬§ηι«

Verify that this value hasn't actually been calculated.

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

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

¿κF⊞Oκι⊞υλ

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.

»I§η⊟υ

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

Edit: Saved 1 byte thanks to @JonathanAllan.

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

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
\$\endgroup\$
2
\$\begingroup\$

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);
}
\$\endgroup\$
2
  • \$\begingroup\$ Doesn't the golfed version need the cache to make it run in sublinear time? \$\endgroup\$
    – Neil
    Sep 17, 2023 at 7:39
  • \$\begingroup\$ @Neil Thanks for your comment, I have corrected it. \$\endgroup\$
    – 138 Aspen
    Sep 18, 2023 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.