How many coprimes ?

Greens

The Euler totient function gives the count of coprimes less than some $n$, which can also mean the number of ordered pairs of the form $(n,k)$ for all the $k \leq n$ that are also coprime.

By summing the totient of every number up to 100 we get the number of ordered coprime pairs (including $(1,1)$)

$\displaystyle \sum_{n=1}^{100} \phi(n) = 3044$

Now, to count the reverse of each ordered pair, we multiply by $2$. We also have to subtract one from this since $(1,1)$ is counted for twice otherwise.

$\displaystyle 2 \left(\sum_{n=1}^{100} \phi(n)\right) -1 = 6087$

This Desmos graph is nice to work with, but I don't know who made it ( CoprimePairStuff )

skipjack

Forum Staff
I checked my program against results for smaller intervals given here.

Greens

Greens

I've checked the totient method as well and it also seems to hold for these smaller intervals.

Also, the number of coprime pairs less than $t$ can also be represented by

$\displaystyle p(t) = 2\sum_{n=1}^{t} \sum_{k=1}^{n} \text{gcd}(k,n) \cos{\left( \frac{2 \pi k}{n} \right)} -1$

which is the expansion of totient, so calculation is easier.

idontknow

Maschke

6087 it is. I found my error.