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?
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?
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.
Combining Theorem 329 in Hardy and Wright with the upper bound on $\sigma(n)$ in Robin (1984), we get $ \phi(n) > \frac{6 n \log \log n}{\pi^2 \left( e^\gamma (\log \log n)^2 + 0.6482 \right)},$ where $\gamma = 0.5772156649...$ is the Euler-Masceroni constant.
As a result, $\phi(n) > 1000$ unless $ n \leq 6872.$
I'm just saying.
1111 = 11 * 101 phi = 1000 = 2^3 * 5^3 1255 = 5 * 251 phi = 1000 = 2^3 * 5^3 1375 = 5^3 * 11 phi = 1000 = 2^3 * 5^3 1875 = 3 * 5^4 phi = 1000 = 2^3 * 5^3 2008 = 2^3 * 251 phi = 1000 = 2^3 * 5^3 2222 = 2 * 11 * 101 phi = 1000 = 2^3 * 5^3 2500 = 2^2 * 5^4 phi = 1000 = 2^3 * 5^3 2510 = 2 * 5 * 251 phi = 1000 = 2^3 * 5^3 2750 = 2 * 5^3 * 11 phi = 1000 = 2^3 * 5^3 3012 = 2^2 * 3 * 251 phi = 1000 = 2^3 * 5^3 3750 = 2 * 3 * 5^4 phi = 1000 = 2^3 * 5^3 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus
One thing I noticed after the fact is that 41 does not appear. This is as it should be. For 2 and powers of 2, we have \phi(2^{k+1} = 2^k.$ However, for any odd prime $p$ such as 5, it is not possible to have any $\phi(n) = p$ or $\phi(n) = p^2$ or, in general, $\phi(n) = p^k.$ In particular it is impossible to have $\phi(n) = 25.$ As a result, if $\phi(n) = 1000,$ it is impossible to have $41 | n.$ Oh, any prime dividing this $n$ must have $(p-1) | 1000,$ and if the exponent is going to be larger than 1 we also need $p | 1000.$ So, with 41, the exponent is 1, and we then need to find some relatively prime $m$ with $\phi(m) = 25,$ impossible.