6
$\begingroup$

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$

enter image description here

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 }}$$

enter image description here

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).

$\endgroup$
1
  • $\begingroup$ One can use a logarithmic form to get sum of logs of (1 -1/p) needs to be greater than log 1/2. However, once one excludes p less than 7, one finds log(1 -1/p) nicely approximated by -1/p, so one can approximate the condition testing the reciprocal sum of primes being less than log 2. Gerhard "Finds Adding Simpler Than Multiplying" Paseman, 2019.01.09. $\endgroup$ Jan 9, 2019 at 16:35

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Thanks! This especially explains how the first exception 105 suddenly pops up. But I'd also like to understand - in a similar fashion - how the first exception not divisible by 5 pops up - 3003. And what will the first exception not divisible by 5 and 3 be? $\endgroup$ Jan 9, 2019 at 10:39
  • 2
    $\begingroup$ $3003$ comes up because $(1-1/3)(1-1/7)(1-1/11)(1-1/13)<1/2$ and this is the first product of primes other than $2,5$ for which inequality holds. For numbers not divisible by $2,3,5$ we have to wait until $(1-1/7)\cdot(1-1/61)$, so the least exception is $7\cdot\dots\cdot 61$. In general, if you exclude primes below $p$, then you have to take primes up to approximately $p^2$, for instance starting from $11$ you have to go up to $127$. I will expand my answer to say something about it. $\endgroup$
    – Wojowu
    Jan 9, 2019 at 10:44
  • $\begingroup$ Thanks a lot for the update! To repeat another question of mine: Do you see a chance to explicitly enumerate the exceptions divisible by 5, which is to explicitly enumerate the $m_k$? $\endgroup$ Jan 9, 2019 at 11:06
  • 1
    $\begingroup$ No. As I've said, they have to be described in terms of the primes which divide them, specifically that they have to have "enough" prime factors for the product to be $<1/2$. I wouldn't hope for anything more explicit than that. $\endgroup$
    – Wojowu
    Jan 9, 2019 at 11:09
  • $\begingroup$ I think the average gap between consecutive prime factors of a $ k $ -factor integer should be an increasing function of $ k $, maybe something like $ \gg k^{\alpha} $ for some $ \alpha>0 $ to be determined. $\endgroup$ Jan 9, 2019 at 11:58
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$
$\endgroup$
4
  • $\begingroup$ Note that if n is at least $2\phi(n)$, the same relation holds for any multiple m of n. So your question is looking for square free odd numbers which satisfy your relation. If $n \lt 2\phi(n)$, one can find m coprime to n so that nm satisfies the same relation. The closer $n$ is to $2\phi( n)$ the larger m needs to be, sometimes exponentially larger. Gerhard "Not Unlike Hunting Odd Perfects" Paseman, 2019.01.09. $\endgroup$ Jan 9, 2019 at 16:58
  • $\begingroup$ @GerhardPaseman: Where does square-freeness come from, I don't see. $\endgroup$ Jan 10, 2019 at 9:05
  • $\begingroup$ @HansStricker The ratio $\varphi(n)/n$ depends solely on the primes dividing $n$. Hence replacing $n$ by its radical (which is squarefree) we get a smaller exception divisible by the same primes. $\endgroup$
    – Wojowu
    Jan 10, 2019 at 10:19
  • $\begingroup$ @Wojowu: Ah, I see. I guess I already reflected this by my edit (dropping the exponents of the primes). $\endgroup$ Jan 10, 2019 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.