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

Question

When coloring the squares of the Ulam spiral not only by black and white (for being prime or non-prime) but by shades of grey representing the normalized totient function $\varphi(n)/n$

and displaying only those numbers with $\varphi(n)/n > 0.5$, i.e. $2\varphi(n) > n$, one finds that for most $n$ – but not all – it holds that

$$\boxed{2\varphi(n) > n \ \ \equiv\ \ n \text{ is odd }}$$

There are two kinds of possible exceptions:

1. $2\varphi(n) > n \ \ \text{ and }\ \ n \text{ is even} $
   These exceptions would appear as dark crosses, but there are none since $\varphi(n)/n \leq 1/2$ for all even $n$.

2. $2\varphi(n) \leq n \ \ \text{ and }\ \ n \text{ is odd } $
   These exceptions appear as light crosses, and there are some.

The 52 exceptions less than 5000 are

$105, 165, 195, 315, 495, 525, 585, 735, 825, 945, 975, 1155, 1365, 1485, 1575, 1755, 1785, 1815, 1995, 2145, 2205, 2415, 2475, 2535, 2625, 2805, 2835, 2925, 3003, 3045, 3135, 3255, 3315, 3465, 3675, 3705, 3795, 3885, 3927, 4095, 4125, 4305, 4389, 4455, 4485, 4515, 4641, 4725, 4785, 4845, 4875, 4935$

They come in two groups:

1. $n \equiv 0 \pmod{3}$ and $n \equiv 0 \pmod{5}$ $105, 165, 195, 315, 495, 525, 585, 735, 825, 945, 975, 1155, 1365, 1485, 1575, 1755, 1785, 1815, 1995, 2145, 2205, 2415, 2475, 2535, 2625, 2805, 2835, 2925, 3045, 3135, 3255, 3315, 3465, 3675, 3705, 3795, 3885, 4095, 4125, 4305, 4455, 4485, 4515, 4725, 4785, 4845, 4875, 4935$

2. $n \equiv 0 \pmod{3}$ and $n \not\equiv 0 \pmod{5}$
   $3003, 3927, 4389, 4641$ (yellow squares)

If one could find two characterizations $\phi_1(n)$ and $\phi_2(n)$ for these two sequences, one would have the general result

$$\boxed{2\varphi(n) > n \ \ \equiv\ \ n \text{ is odd } \wedge \neg\phi_1(n) \wedge \neg\phi_2(n)}$$

In the first sequence some kind of regularity is visible:

$$n_{k+1} = n_k + m_k\cdot 30$$

But it's not at all clear to me, how the $m_k$ behave. These are the first values:

$$m_k = 2,1,4,6,1,2,5,3,4,1,6,\dots$$

With the second sequence I'm totally stuck. How can these numbers be characterized?

My question is:

Can someone give characterizations $\phi_1(n)$ and $\phi_2(n)$ such that

$$2\varphi(n) > n \ \ \equiv\ \ n \text{ is odd } \wedge \neg\phi_1(n) \wedge \neg\phi_2(n)$$

holds - together with a proof?

---

The frequency of exceptions seems to be approximately $0.1$. It might be interesting to see, if a better asymptotic limit can be calculated (if there is one).

Answer 1

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.

Answer 2

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.

Answer 3

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$