Sum of co-primes of a number $n \le k$

Question

Problem Given a number $n$ and a number $k$ ($k\leq n$) we are to find sum of co-primes of $n$ less than or equal to $k$

My thoughts

• factorise $n$
• and then do $k(k + 1)/2$ - sum_of_divisors_less_equls_k

but this wrongly counts multiples of divisors as a co-prime as well. Then as I try to eliminate those multiples of divisors of $n$ which are not divisors themselves things get bit complicated.

If $k=n$ then it gets reduced to https://oeis.org/A023896

Answer 1

Well so long as we're all right with algorithms, the simplest thing would seem to me is to do a an inclusion/exclusion.

Find the divisors of $n$, calling them $d$. Remove any that are multiples of a smaller divisor.

Start with the sum $S=T(k) = \frac12 k(k+1)$, that is, the $k$th triangular number. If $n$ has no smaller divisors, then we also end here.

Now we do exclusion/inclusion. We take the prime divisors first, and subtract all their multiples. That sum is $d \cdot T(\lfloor\ k/d \rfloor)$. (For example, for $k=18, d=5$, we would have to subtract $5+10+15=30=5T(3)$). So we need:

$$S = T(k) - \sum_{d \mid n, d \le k}^{\omega(d)=\Omega(d)=1} T\left(\left\lfloor \frac k d \right\rfloor\right)$$

Of course, then we need add back in all the numbers that we removed twice--that is, divisors with two factors and their multiples. And you likely know the drill from here: keep going until we run out. That gives us:

$$S = T(k) + \sum_{i} \sum_{d \mid n, d \le k}^{\omega(d)=\Omega(d)=i} (-1)^i T\left(\left\lfloor \frac k d \right\rfloor\right)$$

if we're all right with some abuse of notation for the outer summation, as $i$ is just the number of divisors of the largest divisor lower than $k$. It's nice and compact but still definitely an algorithm.

Answer 2

The sum of coprimes of n which are less than or equal to k can be written as

$$= \sum_{ \ \ \ r\le k \\ (r, n) = 1}{r}$$

$$= \sum_{d \mid n}{\mu(d) \sum_{r \le k \\ d \mid r}{r}}$$ via inclusion-exclusion,

$$= \sum_{d\mid n}{\mu(d) \sum_{ad \le k}{ad}}$$

$$= \sum_{d\mid n}{\mu(d)\cdot d \sum_{a\le \frac{k}{d}}{a}}$$

$$= \sum_{d\mid n}{\mu(d)\cdot d\cdot T\left(\left[\frac{k}{d}\right]\right)}.$$

where $\mu(d)$ is the mobius function, namely

$$\mu(d) = \begin{cases} (-1)^{\omega(d)}: & \text{$d$ is squarefree} \\ 0: & \text{otherwise} \end{cases}.$$