5
$\begingroup$

Is there some way to use Euler's Totient function to represent the amount of odd composites that share a factor with integer $n$ less than $n$? For instance,

$n-\phi(n)$ represents the total amount of composites less than $n$ that share a factor with $n$. How might I reduce this to only the odd composites?

$\endgroup$
2
  • $\begingroup$ For odd numbers it's still $n-\phi(n)$. For $n=2^rp$ with $p$ prime and $r\ge 1$, it's $2^{r-1}$. $\endgroup$
    – Mastrem
    Mar 23, 2017 at 21:14
  • $\begingroup$ Can you use the prime counting function $\pi(n)$? If so, you might have to adjust by $+1$ or $-1$. $\endgroup$
    – Bob Happ
    Mar 23, 2017 at 21:23

1 Answer 1

Reset to default
1
$\begingroup$

If $n$ is even, then no even number is relatively prime to $n,$ so the $n-\phi(n)$ numbers not-relatively-prime-to-n include the $n/2$ even numbers, so in that case, your number is: $$n/2 - \phi(n).$$

If $n$ is odd, then the number of even numbers not-relatively-prime to $n$ is the same as the number of number $\leq \lfloor \frac{n}{2}\rfloor$ not-relatively-prime to $n.$ Now the number of integers relatively prime to $n$ and less than or equal to $n/2$ is $\Phi(n, \lfloor \frac{n}{2}\rfloor),$ where $\Phi(n, x)$ is defined (see this question) as $$\Phi(n,x)=x-\sum_i\lfloor{x/{p_i}}\rfloor+\sum_{i \lt j}\lfloor x/{p_ip_j}\rfloor-\cdots+(-1)^{k}\lfloor x/{n}\rfloor,$$ and thus the number of even numbers not-relatively-prime-to-n equals $$E(n) = \lfloor \frac{n}{2}\rfloor - \Phi(n, \lfloor \frac{n}{2}\rfloor).$$ So, the number of odd non-relativel-prime integers is $$n-\phi(n) - E(n).$$ I am not sure if you can simplify this further.

$\endgroup$
7
  • $\begingroup$ Can't you simplify $E(n)$ to $\sum_i\lfloor{x/{p_i}}\rfloor+\sum_{i \lt j}\lfloor x/{p_ip_j}\rfloor-\cdots+(-1)^{k}\lfloor x/{n}\rfloor$? $\endgroup$
    – Linus Rastegar
    Mar 23, 2017 at 21:41
  • $\begingroup$ @LinusRastegar Indeed! I was wondering whether one can avoid alternating sums altogether ... $\endgroup$
    – Igor Rivin
    Mar 23, 2017 at 21:46
  • $\begingroup$ If $x = \lfloor \frac{n}{2}\rfloor$ I think there is a way to simplify $E(n)$ further because this means that $\Phi(n,x)$ can somehow be related the product of $1-\frac{1}{p_i}$, as the question you linked claimed with a simpler version of $\Phi$. $\endgroup$
    – Linus Rastegar
    Mar 23, 2017 at 21:57
  • $\begingroup$ @LinusRastegar Yes, but it is not clear that there is a closed form. In fact, each $\lfloor \frac{x}{p_1 \dots p_k}\rfloor$ equals $$\lfloor \frac{n}{2 p_1 \dots p_k}\rfloor,$$ but the trick is getting rid of the floors... $\endgroup$
    – Igor Rivin
    Mar 23, 2017 at 21:59
  • $\begingroup$ You could split the floors into two separate cases. $\lfloor \frac{n}{2}\rfloor$ could be rewritten as $\frac{n}{2}$ when $n$ is even and $\frac{n}{2} - 1$ when $n$ is odd. $\endgroup$
    – Linus Rastegar
    Mar 23, 2017 at 23:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .