How many coprimes ?

Oct 2018
129
96
USA
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
Dec 2006
21,482
2,472
I checked my program against results for smaller intervals given here.
 
  • Like
Reactions: Greens
Oct 2018
129
96
USA
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.
 
  • Like
Reactions: idontknow