Given $k$, what is the largest number $n$, such that $\phi(n) \le k$

Question

Let $k$ be a positive integer and $n$ be the largest number $n$ with the property $\phi(n) \le k$.

Does such a number $n$ exist for every $k$ ?

How can I determine the number $n$ ?

Such a number $n$ should exists because $\phi(n)$ gets particularly small compared to $n$, if $n$ is of the form $p\#$, but I do not know a rigorous proof.

Some examples :

$k=20$ : $n=66=2\times3\times 11$

$k=130$ : $n=510=2\times3\times5\times17$

$k=190$ : $n=690=2\times3\times5\times23$

$k=680$ : $n=2940=2^2\times3\times5\times7^2$

So, the number $n$ seems to be a small multiple of some primorial $p\#$.

Answer 1

For the first question: Yes. If $p^r\mid n$ then $p^{r-1}\le (p-1)p^{r-1}\mid \phi(n)$ so that $\phi(n)\le k$ implies $r-1\le \log_p k$. This gives us the very crude estimate $$ n\le\prod_{p\le k}p^{1+\lceil\log_p k\rceil}$$

Answer 2

Since $p \mid n \implies (p-1) \mid \varphi(n)$, an $n$ with $\varphi(n) \leqslant k$ cannot be divisible by any prime greater than $k+1$. Further, the formula $\varphi(n) = n\prod\limits_{p\mid n}\frac{p-1}{p}$ yields the bound

$$b(k) = k\prod_{p \leqslant k+1}\frac{p}{p-1} \sim k e^{\gamma} \log k.$$

This bound wildly overestimates the largest $n$ when $k$ is large, but is reasonable for smallish $k$ - we have $b(1) = 2$ and $b(2) = 6$, so the bound is sharp for very small $k$. For $k = 4$, we have $b(4) = 15$ while the maximal $n$ is $12$, and $b(6) = \frac{105}{4}$ while the largest $n$ with $\varphi(n) \leqslant 6$ is $n = 14$, so that's not too bad yet. Even $b(680) \approx 7956$ isn't totally absurd.

We have the further condition that $\prod\limits_{p\mid n} (p-1) \leqslant k$, and that limits $n$ much more when $k$ is not small. For $k = 680$, the inequality $k < 6!$ shows that an $n$ with $\varphi(n) \leqslant k$ can have at most five distinct prime divisors and that yields a bound of

$$n \leqslant 680 \cdot \frac{2}{1}\cdot \frac{3}{2} \cdot \frac{5}{4} \cdot \frac{7}{6}\cdot \frac{11}{10} = 3272.5$$

which already is in the right ball park.

For a useful bound, find the largest prime $q$ with $\prod\limits_{p \leqslant q} (p-1) \leqslant k$, and set

$$c(k) = k\prod_{p \leqslant q} \frac{p}{p-1}.$$

Since $q$ is about $\log k$ when $k$ is large, we have the asymptotic behaviour $c(k) \sim k e^{\gamma} \log \log k$.

This - $c(k)$ - will still overestimate (except for very small $k$) but not by too much, the asymptotic behaviour is correct.

Since $\frac{p}{p-1}$ is decreasing, the ratio $\frac{n}{\varphi(n)}$ is largest when $n$ has many small prime factors, whence it is to be expected that the maximal $n$ with $\varphi(n)$ is almost a primorial - "almost a primorial" meaning that it is a primorial multiplied with few if any further primes. But since apart from the ratio $\frac{n}{\varphi(n)}$ also values of $\varphi(n)$ close to $k$ make $n$ large, it is to be expected that often multiplying by a larger prime at the end yields a larger $n$ than taking the smallest prime not yet used, and using some small primes more than once can also bring $\varphi(n)$ closer to $k$ and thus lead to a larger $n$ than a squarefree number would.

However, I can't give an algorithm that doesn't need some trial and error.

If you want to find the maximal $n$ with $\varphi(n) \leqslant k$ for all $k$ not exceeding a medium-sized bound $K$, the best method is probably to compute $\varphi(n)$ for all $n \leqslant c(K)$ - a variation of the sieve of Eratosthenes makes that efficient - and then scan the array noting the largest values with a given totient.

To find the largest $n$ with $\varphi(n) \leqslant k$ for a single (large) $k$, I would start with the primorial $q\#$, where $q$ is the largest prime with $\prod\limits_{p \leqslant q}(p-1) \leqslant k$, then possibly replacing $q$ with a larger prime, and/or dropping $q$ and multiplying with some small primes to get the totient closer to $k$. This should give a not too bad lower bound. One can then either try some more replacements to look for a larger $n$, or if the range between the lower and upper bound is small enough, compute the totients of the numbers between those bounds and look for the best $n$.

Concerning your comment

The inverse totient function would solve the problem. How can I get the largest number $n$ with $\phi(n) = k$ for some given $k$?

I am not too optimistic. If there is a known algorithm to compute the largest $n$ with $\varphi(n) = k$ efficiently, that would probably work well enough. Although one has to check several candidate totients $k$, one would likely soon hit one that yields the optimal $n$, and then there would hopefully not remain too many candidates to check. But I am not aware of an efficient algorithm. (That doesn't mean much, though, since I'm not an expert in the field.)