Is there a formula that counts the number of positive odd integers up to a given integer N that are relatively prime to N.

Question

This is similar to the totient function, but obviously somewhat different. I would be interested to know if formulae exist for counting the positive odd integers and the positive even integers up to a given integer N that are relatively prime to N.

Answer 1

Let f(n) = count of all co-prime integers and g(n) = count of odd co-prime integers. If n is even then all co-prime numbers are odd, so f(n) = g(n).

For odd n: If k is co-prime to 2n then so is 2n-k, and both are odd. So exactly half the numbers co-prime to 2n are less than n, and they are all odd. So g(n) = f(2n) / 2 if n is odd.

(The proof may be a bit dodgy but the principle and the result are right).

Answer 2

A little more generally. For an arithmetic function $f(n)$ and odd $n$ $$\sum_{{k=1}\\{k=odd}}^n f(gcd(n,k)) = \frac{1}{2}\cdot \left((f*\phi)(n)+f(n) \right)$$ and for even $n$ $$\sum_{{k=1}\\{k=odd}}^n f(gcd(n,k)) = (\phi*(L \cdot f)(n)$$ where $\phi$ is the totient function, $*$ is the Dirichlet convolution and $L(n)$ is $1$ for odd $n$ and $0$ for even $n$. Specially for $f(n)=e(n)$ where $e(n)$ is unit function, i.e. $e(n)1$ for $n=1$ and $e(n)=0$ for $n>1$. For odd $n$ $$\sum_{{k=1}\\{k=odd}\\{gcd(n,k)=1}}^n 1 = \frac{1}{2}\cdot(\phi(n)+e(n)))$$ and for even $n$ $$\sum_{{k=1}\\{k=odd}\\{gcd(n,k)=1}}^n 1 = \phi(n)$$