Euler's totient function has a lower bound for large values, but is there any way to pick out maximums for specific values of the function?
That is, how would I find the maximum number n such that phi(n) = 1000, for example?
[Math] Finding the maximum number with a certain Euler’s totient value
elementary-number-theorynumber theorytotient-function
Best Answer
This could be a hard problem, in general, but let's look at 1000.
$n$ can't be odd, since we'd have $2n\gt n$ and $\phi(2n)=\phi(n)$. Let $n=2m$.
$m$ can't have more than 3 distinct prime factors, since that would force $\phi(n)$ to be divisible by $2^4$, which it isn't.
If $p$ is prime and $p^2$ divides $n$ then $p$ divides $\phi(n)$ so $p$ is 2 or 5.
Now you can start loking at the numbers $2^r5^s$ for $r=1,2,3$ and $s=0,1,2,3$ to see which ones are $\phi(p)$ for some prime $p$ (other than 2 and 5, which can be treated separately). So for example, $\phi(11)=10$, $\phi(101)=100$, $\phi(41)=40$, and so on. Once you have the whole (finite) list, you can test the ways of putting together products of these numbers (and powers of 2 and/or 5) to see how to get $\phi(n)=1000$ and which way maximizes $n$.
It's a bit ad hoc, but I'm not sure that can be helped.