When is $2\varphi(n) > n$ – and how to prove it?

It is well-known that $\varphi(n)/n=\prod_{p\mid n}(1-1/p)$, so the question is about when such a product will be greater than $1/2$. If $n$ is even, one of the factors is $1/2$, so $\varphi(n)\leq n/2$. If we only restrict to odd numbers, it's still possible for that to happen, but the number has to have more prime factors. For instance, if $n$ is divisible by $3,5$ and $7$ (so by $105$), $\varphi(n)/n\leq 2/3\cdot 4/5\cdot 6/7=16/35<1/2$. Same if $n$ is divisible by $3,5,11$.

Even excluding more small primes won't make the product always greater than $1/2$, because the product $\prod_p(1-1/p)$ over primes tends to zero. For instance, taking the product over primes from $5$ to $23$ gives us less than $1/2$.

Summarizing, there isn't going to be any simple condition for $2\varphi(n)>n$, except for the almost tautological one $\prod_{p\mid n}(1-1/p)>1/2$.

---

In comments a question was asked regarding smallest counterexamples not divisible by some fixed primes. I'm going to answer a bit more specific question: depending on $x$, what is the smallest $n$ not divisible by primes $p\leq x$ satisfying $2\varphi(n)<n$? It's easy to see that the answer is equal to the product of primes between $x$ and $y$, where $y$ is the smallest such that $\prod_{x<p\leq y}(1-1/p)<1/2$.

To study such products we have Mertens' third theorem, which says that asymptotically we have $$\prod_{p\leq x}\left(1-\frac{1}{p}\right)\sim\frac{e^{-\gamma}}{\ln x},$$ where $\gamma$ is the Euler-Mascheroni constant and $\ln$ is natural logarithm. It follows that for large $x,y$, $$\prod_{x<p\leq y}\left(1-\frac{1}{p}\right)\sim\frac{\ln x}{\ln y}.$$ Therefore the question is: for what $y$ is $\ln x/\ln y<1/2$, and the answer is of course $y>x^2$. This is, of course, only an approximate answer. I have used the following SageMath script to compute some exact values:

for x in prime_range(100):
for y in prime_range(x^2/2,2*x^2):
        if product([1-1/p for p in prime_range(x,y+1)])<1/2:
            x,y,y/x^2.n()
            break

The results are (in the form $(x,y,y/x^2)$, the last one to see how good the approximation is):

(2, 3, 0.750000000000000)
(3, 7, 0.777777777777778)
(5, 23, 0.920000000000000)
(7, 61, 1.24489795918367)
(11, 127, 1.04958677685950)
(13, 199, 1.17751479289941)
(17, 337, 1.16608996539792)
(19, 479, 1.32686980609418)
(23, 677, 1.27977315689981)
(29, 937, 1.11414982164090)
(31, 1193, 1.24141519250780)
(37, 1511, 1.10372534696859)
(41, 1871, 1.11302795954789)
(43, 2267, 1.22606814494321)
(47, 2707, 1.22544137618832)
(53, 3251, 1.15735137059452)
(59, 3769, 1.08273484630853)
(61, 4349, 1.16877183552808)
(67, 5009, 1.11583871686344)
(71, 5711, 1.13291013687760)
(73, 6451, 1.21054606868080)
(79, 7321, 1.17304919083480)
(83, 8231, 1.19480330962404)
(89, 9173, 1.15806085090266)
(97, 10151, 1.07886066532044)

So approximation $y\approx x^2$ seems to hold up somewhat well.

Here is a script which is a lot faster:

x = 2
P = 1
for y in prime_range(10^6):
    P = (1-1/y)*P
    if P<1/2:
        x,y,y/x^2.n()
        P = P/(1-1/x)
        x = next_prime(x)

The ratio $y/x^2$ seems to converge to $1$ from above.

A proof for the even part: For the even numbers, you can say $2\phi(n) \leq n$ easily. Because for each even number the format of $\phi(n)$ is $n(1-\frac{1}{2})c = \frac{n}{2}\times c$ which $c \leq 1$. Hence, $2\phi(n) \leq n$.

For the odd part as $\phi(n) = n(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_k})$, we should consider that such odd numbers which $(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_k}) > \frac{1}{2}$. Hence, all odd numbers which their prime factors satisfy this inequality, they can satisfy the specified inequality. As different set of numbers satisfy this, you can't say any specific about that number unless finding that all said. However, we can say if the prime factor of a number is greater, it has more chance to satisfy the inequality.

I'd like to sum up some specific parts of Wojowu's answer:

1. The smallest odd $n$ with $\varphi(n)/n = \prod_{p|n}(1-1/p) \leq 1/2$ is $105 = 3\cdot 5\cdot 7$

2. $\varphi(n)/n < 1/2$ also for

   • $3 \cdot 5 \cdot p \cdot q$ with $7 \leq p \leq 13$ prime and $q\in\mathbb{N}^+$ odd

3. The smallest odd $n$ with $\varphi(n)/n \leq 1/2$ not found yet is $3003 = 3\cdot 7 \cdot 11 \cdot 13$

4. $\varphi(n)/n < 1/2$ also for

   • $3 \cdot 7 \cdot 11 \cdot p \cdot q$ with $13 \leq p \leq 23$ prime and $q\in\mathbb{N}^+$ odd

   • $3 \cdot 7 \cdot 13 \cdot p \cdot q$ with $17 \leq p \leq 19$ prime and $q\in\mathbb{N}^+$ odd

---

The natural question then is: What comes next, what is the smallest $n$ with $\varphi(n)/n \leq 1/2$ not found yet? And so on, and so on. (I have to admit, @Wojowu, that I'm still not able to answer this.)

---

Some shortest sequences of primes $p_1,\dots,p_k$ with $\prod_{p_i}(1-1/p_i) \leq 1/2$ and their products:

• $3\cdot 11 \cdot 13 \cdot 17 \cdot 19 = 138,567$ (is this the next one?)
• $3 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 = 260,468,169$
• $5\cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 = 37,182,145$