8
$\begingroup$

The topic was also discussed in this MathOverflow question.

From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ because the product contains the factor $1/2$ and cannot be larger than that.

But not all odd numbers have $\varphi(n)/n > 1/2$. The smallest number that hasn't is $105$.

You can see the exceptions as bright stars when plotting $\varphi(n)/n$ on a square spiral (where odd and even numbers build a checkerboard pattern), but only, when $\varphi(n)/n > 1/2$:

enter image description here

I wonder if and how one could enumerate or characterize all odd numbers for which $\varphi(n)/n < 1/2$.

This is how one could proceed: Start with an empty list. Determine the smallest square-free odd number $n$ with $\varphi(n)/n < 1/2$ which is not on the list and add it to the list together with its odd multiples. Then find the next, and the next, and so on. The list starts with

  • $105 = 3\cdot 5 \cdot 7$ and its odd multiples $315, 525, 735,...$

  • $165 = 3\cdot 5 \cdot 11$ and its odd multiples $495,825,1155,...$

  • $195 = 3\cdot 5 \cdot 13$ and its odd multiples $195,585,975,1365,...$

These numbers can be seen as white stars (above).

Then a jump occurs:

  • $3,003 = 3\cdot 7 \cdot 11 \cdot 13$ and its odd multiples $9009, 15015, 21021, ...$

  • $3,927 = 3\cdot 7 \cdot 11 \cdot 17$ and its odd multiples $11781, 19635, 27489 ...$

  • $4,389 = 3\cdot 7 \cdot 11 \cdot 19$ and its odd multiples $13167, 21945, 30723, ...$

  • $4,641 = 3\cdot 7 \cdot 13 \cdot 17$ and its odd multiples $13923, 23205, 32487, ...$

  • $5,187 = 3\cdot 7 \cdot 13 \cdot 19$ and its odd multiples $15561, 25935, 36309, ...$

  • $5,313= 3\cdot 7 \cdot 11 \cdot 23$ and its odd multiples $15939, 26565, 37191, ...$

The four smallest of these numbers can be seen as yellow stars (above).

Then the numbers $3 \cdot 5 \cdot 17 \cdot p$ follow for $23 \leq p \leq 251$, the largest one being $64,005$.

Then a larger jump occurs:

  • $138,567 = 3\cdot 11 \cdot 13 \cdot 17 \cdot 19 $

Note that in the first group of numbers (divisible by $3$ and $5$) all differences are multiples of $30 = 2\cdot 3 \cdot 5$. That's because all numbers are multiples of $15$ and the even multiples are omitted. In the second group (divisible by $3$ and $7$) all differences are multiples of $42 = 2\cdot 3 \cdot 7$.


There are several questions related to these findings:

  1. Are there "smallest numbers" I missed?
    This question has been answered thanks to Robert Israel's link to OEIS A119433. I've edited my post accordingly.

  2. How do I systematically find the next "smallest number"?

  3. After ordering the first group, the maximal factor of consecutive numbers in this group is $7$, i.e. when $n_{k+1} = n_k + a\cdot 30$ then $1 \leq a \leq 7$. Furthermore, all factors $1 \leq a \leq 7$ do occur. I wonder why this is so and how to prove it?

  4. What's the maximal factor for the second group?

  5. Which other properties do odd numbers with $\varphi(n)/n < 1/2$ share with even numbers? (They might be considered "quasi-even".)

$\endgroup$
  • $\begingroup$ See OEIS sequence A119434 and A119433. $\endgroup$ – Robert Israel Jan 10 at 15:38
  • $\begingroup$ @RobertIsrael: Thanks, I've seen it. But does it help to answer my question? (Ah, I see that you are the author of this OEIS entry. Very pleased!) $\endgroup$ – Hans-Peter Stricker Jan 10 at 15:40
  • $\begingroup$ @RobertIsrael: I see, the second sequence answers question 1: There are lots of numbers $5,313<n<138,567$ which do qualify, the first one is $5,865 = 3\cdot 5\cdot 17 \cdot 23$. And it may also give me hint to answer question 2. $\endgroup$ – Hans-Peter Stricker Jan 10 at 15:48
  • 1
    $\begingroup$ @HansStricker: Just wait: the smallest odd number that is not a multiple of $3$ or $5$ for which $\frac{\phi(n)}n\lt\frac12$ is $3909612711980232366109$. $\endgroup$ – robjohn Jan 10 at 19:08
  • 1
    $\begingroup$ @Peter: One just multiplies $\left(1-\frac17\right)\left(1-\frac1{11}\right)\left(1-\frac1{13}\right)\left(1-\frac1{17}\right)\cdots\left(1-\frac1{61}\right)$ until the product becomes less than $\frac12$. Then compute $7\cdot11\cdot13\cdot17\cdots61$. $\endgroup$ – robjohn Jan 11 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.