Dtyjlui

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

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 = 3cdot 5 cdot 7$ and its odd multiples $315, 525, 735,...$




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




• $195 = 3cdot 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 = 3cdot 7 cdot 11 cdot 13$ and its odd multiples $9009, 15015, 21021, ...$




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




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




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




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




• $5,313= 3cdot 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 = 3cdot 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 = 2cdot 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 = 2cdot 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 + acdot 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".)