show/hide this revision's text 3 Corrected typo

First of all as you remark above, it is easy to see by elementary means that the error is at most $2^k$. It was an old conjecture of Erdos that this error term could be improved to $o(2^k)$. However this conjecture turns out not to be true!

In 1951 Vijayaraghavan proved that the error term $O(2^k)$ is best possible in the sense that for any $k\in\mathbb{N}$ and $\delta >0$ you can find an integer $n$ with exactly $k$ distinct prime factors, and a real number $x$, such that

$$\Phi(n,x)>2^{k-1}-\delta.$$$\Phi(n,x)-xr>2^{k-1}-\delta.$$

Vijayaraghavan's paper is On a problem in elementary number theory. J. Indian Math. Soc. 15, (1951).

For a more detailed and up to date discussion you could look at the more recent paper Codecà, Nair, An extension of a result of Lehmer on numbers coprime to n. Ramanujan J. 16 (2008), no. 1, 59–71.
show/hide this revision's text 2 deleted 31 characters in body

This is an excellent question.

First of all as you remark above, it is easy to see by elementary means that the error is at most $2^k$. It was an old conjecture of Erdos that this error term could be improved to $o(2^k)$. However this conjecture turns out not to be true!

In 1951 Vijayaraghavan proved that the error term $O(2^k)$ is best possible in the sense that for any $k\in\mathbb{N}$ and $\delta >0$ you can find an integer $n$ with exactly $k$ distinct prime factors, and a real number $x$, such that

$$\Phi(n,x)>2^{k-1}-\delta.$$

Vijayaraghavan's paper is On a problem in elementary number theory. J. Indian Math. Soc. 15, (1951).

For a more detailed and up to date discussion you could look at the more recent paper Codecà, Nair, An extension of a result of Lehmer on numbers coprime to n. Ramanujan J. 16 (2008), no. 1, 59–71.
show/hide this revision's text 1

This is an excellent question. First of all as you remark above, it is easy to see by elementary means that the error is at most $2^k$. It was an old conjecture of Erdos that this error term could be improved to $o(2^k)$. However this conjecture turns out not to be true!

In 1951 Vijayaraghavan proved that the error term $O(2^k)$ is best possible in the sense that for any $k\in\mathbb{N}$ and $\delta >0$ you can find an integer $n$ with exactly $k$ distinct prime factors, and a real number $x$, such that

$$\Phi(n,x)>2^{k-1}-\delta.$$

Vijayaraghavan's paper is On a problem in elementary number theory. J. Indian Math. Soc. 15, (1951).

For a more detailed and up to date discussion you could look at the more recent paper Codecà, Nair, An extension of a result of Lehmer on numbers coprime to n. Ramanujan J. 16 (2008), no. 1, 59–71.