Find the sum of all natural numbers less than and coprime to $N=25200$

Solution 1:

Hint: The numbers less than $25200$ and coprime to $25200$ come in pairs of the form $k, 25200 - k$. Then: do you know how many numbers there are coprime to $25200$?

Solution 2:

Since the number of prime factors of $N$ is small, you can find the desired sum by continually correcting for higher and higher numbers of shared prime factors.

You start by adding all the numbers less than $N$, as shown below. Let $n$ be the number of prime factors shared between $N$ and an arbitrary number less than $N$.

$$\begin{matrix} n&0&1&2&3&4 \\ {\rm Times\ counted:}&1&1&1&1&1 \end{matrix}$$

By subtracting numbers for each shared prime factor, we get the following:

$$\begin{matrix} n&0&1&2&3&4 \\ {\rm Times\ counted:}&1&0&-1&-2&-3 \end{matrix}$$

As you noted, you seem to be stuck on the negative values for $n\geq2$. We can simply correct for these by adding back values that share a pair of prime factors (ie. $6,10,15$). For each triple, there are 3 unique pairs, and for each quadruple, there are 6 pairs, so we get the following:

$$\begin{matrix} n&0&1&2&3&4 \\ {\rm Times\ counted:}&1&0&0&1&3 \end{matrix}$$

Now we can subtract the values that are divisible by a triple of prime factors (ie. $30,42$). There are 4 unique triples in the quadruple, so:

$$\begin{matrix} n&0&1&2&3&4 \\ {\rm Times\ counted:}&1&0&0&0&-1 \end{matrix}$$

Finally, we can add back the quadruple shared prime factors (divisible by $210$) to get the following:

$$\begin{matrix} n&0&1&2&3&4 \\ {\rm Times\ counted:}&1&0&0&0&0 \end{matrix}$$

And this is your desired result. In general, you can find the sum of the coprime numbers by subtracting for odd numbers of prime factors, and adding back for even numbers of prime factors.