$30$ is the largest number $n$ such that $ω(n) + φ(n) = π(n) + 1$ Recently, a friend told me that $30$ is the largest integer $n$ such that $ω(n) + φ(n) = π(n) + 1$. $\omega(n)$ is the number of distinct prime factors of $n$, $\phi(n)$ is the Euler phi function, and $\pi(n)$ is the prime counting function.
How to prove it?
My efforts:
$ω(n) + φ(n) = π(n) + 1$ means that, all numbers that are less than $n$ and coprime to $n$ are $1$ and prime numbers. Therefore, all non-prime numbers coprime to $n$ are greater than $n$ (except $1$).
Suppose a prime $p$ doesn't divide $n$, then $p^2$ is nonprime and coprime to $n$, therefore $n < p^2$. So, for each prime number $p$ such that $p^2 \le n$, we have $p\mid n$.
Therefore, if $p_1,\dots, p_k$ are all the prime numbers less than $\sqrt{n}$, then $p_1\dots p_k\mid n$, therefore $p_1\dots p_k\le n\le p_{k+1}^2$. ($p_{k+1}$ is the next prime number.)
I guess that $p_1\dots p_k\le p_{k+1}^2$ can only hold for $p_{k+1} \le 7$, as $2\times 3\times 5\times 7 = 210 > 11^2$, so $n\le 7^2 = 49$. I checked all numbers below $49$, and $30$ is indeed the greatest solution.
The fact that $p_1\dots p_k\le p_{k+1}^2$ can only hold for $p_{k+1} \le 7$ is the only thing we need to show. How to show this? Maybe some estimations of the density of prime numbers could help.
I know there are extremely strong and advanced theorems on the density of prime numbers, for example, the Wikipedia says that for $n>56$ we have $\pi(n) \ge n/(\log(n) + 2)$. However, I think these theorems are too great to be used here. For example, we shouldn't use the Fermat's last theorem to prove that $2^{1/3}$ is irrational. Here, we only need a very weak estimation. Is there an easy way to show this? "Easy" means easier than using PNT-tier theorems.
I also tried this: Assume that $p_1,\dots,p_k$ are the only prime numbers below $K = \sqrt{p_1\dots p_k}$. Then, there "should be" about $(1-1/p_1)\dots(1-1/p_k) \cdot K$ numbers below $K$ that are not divisible by any of the $k$ prime numbers. One of them is 1, and if there are any other such numbers, there must be a prime number $p_{k+1}$, and then $p_{k+1}^2 < p_1\dots p_k$. We only need to show that there are at least $2$ such numbers (less than $K$ and not divisible by any of $p_1,\dots p_k$) .
I tried to estimate the number of such numbers by the inclusion-exclusion principal:
Among $1,\dots,K$, there are about $K/p_i$ numbers divisible by $p_i$, with an error at most $1$; there are about $K/p_i p_j$ numbers divisible by $p_ip_j$, with an error at most $1$; $\dots$. But the total error is about $2^k$, which is too big.
 A: I'd say that the correct approach to this problem IS to use results about the density of prime numbers. Namely, we have the following:

*

*$\omega(n)$ tends to be very small (think $\log(\log(n))$)


*$\varphi(n)$ tends to be rather large (think $n/\log(\log(n))$)


*$\pi(n)$ tends to be in the middle (think $n/\log(n)$).
Since the $\varphi(n)$ side is larger than the $\pi(n)$ side, you will only have to check finitely many values. If your conjecture is correct, then the desired result will be output.
If you want to do this with the strongest possible results ("PNT-tier theorems" as you call them), you could. However, those theorems are way overkill in this situation. The power of those results isn't that they give you an estimate on the magnitude size, but it's that they give you percise values and error. If you just want a general idea, then things simplify.
Sitting in front of me I have a copy of George E. Andrew's dover book "Number Theory": On page 107, they prove that
$$\pi(x)<30\log(2)\cdot \frac{x}{\log(x)}.$$
If you can't accept this level of theorem on your proof, I don't think I can help you.
To lower bound $\varphi(n)$, you can use the following. The formula for $\varphi(n)$ says that
$$\varphi(n)/n=\prod_{p|n}(1-1/p).$$
We thus get the elementary lower bound
$$\varphi(n)/n\geq\prod_{p\leq k}(1-1/p),$$
where $k$ is the smallest value such that $\prod_{p\leq k}p\geq n$. The rationnelle behind this pick is that the "worst case scenario" is when lots of distinct small primes divide $k$, and this is the most small primes that can.
Now, Mertens' theorems (which are much easier to prove than PNT) say that
$$\prod_{p\leq k}(1-1/p)\sim e^{-\gamma}/\log(k).$$
If you don't want to appeal to this level of theorem, then you should find a more elementary proof which gives you a less sharp result. Just like how we can find one for PNT, I am sure one exist for Mertens. Taking an explicit lower bound, we get that
$$\varphi(n)\geq C\cdot n/\log(\log(n))$$
for some explicit (small) value $C$. I don't know what $C$ is here is the best possible, and surely this will depend on how elementary you want your proof to be. Comparing, we get that the left hand side of
$$\pi(x)+\varphi(x)=\pi(x)+1$$
grows faster than the right hand side. Depending on the value of $C$ you get, you will get a different finite set of values to check. Hopefully this helps.
