Let $\phi(n)$ be Euler's totient function. For $n=4m$ what is the smallest $n$ for which
$$\phi(n) \ne \phi(k) \textrm{ for any } k<n \textrm{ ?} \quad (1)$$
When $n=4m+1$ and $n>1$ the smallest is $n=5$ and when $n=4m+3$ it's $n=3.$ However, when
$n=4m+2$ the above condition can never be satisfied since
$$\phi(4m+2) = (4m+2) \prod_{p | 4m+2} \left( 1 – \frac{1}{p} \right)$$
$$ = (2m+1) \prod_{p | 2m+1} \left( 1 – \frac{1}{p} \right) = \phi(2m+1).$$
In the case $n=4m,$ $n=2^{33}$ is a candidate and $\phi(2^{33})=2^{32}.$ This value satisfies $(1)$ because $\phi(n)$ is a power of $2$ precisely when $n$ is the product of a power of $2$ and any number of distinct Fermat primes:
$$2^1+1,2^2+1,2^4+1,2^8+1 \textrm{ and } 2^{16}+1.$$
Note the $n=2^{32}$ does not satisfy condition $(1)$ because the product of the above Fermat primes is $2^{32}-1$ and so $\phi(2^{32})=2^{31}=\phi(2^{32}-1)$ and
$2^{32}-1 < 2^{32}.$
The only solutions to $\phi(n)=2^{32}$ are given by numbers of the form
$n=2^a \prod (2^{x_i}+1)$ where $x_i \in \lbrace 1,2,4,8,16 \rbrace $ and
$a+ \sum x_i = 33$ (note that the product could be empty),
so all these numbers are necessarily $ \ge 2^{33}.$
Why don't many "small" multiples of $4$ satisfy condition $(1)$? Well, note that for $n=2^a(2m+1)$ we have
$$\phi(2^a(2m+1))= 2^a(2m+1) \prod_{p | 2^a(2m+1)} \left( 1 – \frac{1}{p} \right)$$
$$ = 2^{a-1}(2m+1) \prod_{p | 2m+1} \left( 1 – \frac{1}{p} \right) = 2^{a-1}\phi(2m+1),$$
and so, for $a \ge 2,$ if $2^{a-1}\phi(2m+1)+1$ is prime we can take this as our value of $k<n$ and we have $\phi(n)=\phi(k).$ This, together with the existence of the Fermat primes, seems to be why it's difficult to satisfy when $n=4m.$
I have only made hand calculations so far, so I would not be too surprised if the answer is much smaller than my suggestion. The problem is well within the
reach of a computer, and possibly further analysis without the aid of a computer. But, anyway, I've decided to ask here as many of you have ready access to good mathematical
software and I'm very intrigued to know whether there is a smaller solution than $2^{33}.$
Some background information:
This question arose in my search to bound the function $\Phi(n)$ defined as follows.
Let $\Phi(n)$ be the number of distinct values taken on by $\phi(k)$ for $1 \le k \le n.$
For example, $\Phi(13)=6$ since $\phi(k)$ takes on the values $\lbrace 1,2,4,6,10,12 \rbrace$ for $1 \le k \le 13.$
It is clear that $\Phi(n)$ is increasing and increases by $1$ at each prime value of $n,$ except $n=2,$ but it also increases at other values as well. For example, $\Phi(14)=6$ and $\Phi(15)=7.$
Currently, for an upper bound, I'm hoping to do better than $\Phi(n) \le \lfloor (n+1)/2 \rfloor .$
But this this not the issue at the moment, although it may well become a separate question.
This work originates from this stackexchange problem.
Best Answer
The answer is
\[33817088 = 2^9 \cdot 257^2 = 2^9 \cdot (2^8 + 1)^2\]
with
\[\phi(33817088) = 16842752 = 2^{16} \cdot (2^8 + 1) = 2^{16} \cdot 257\;.\]
Here's the Java code to find it (it takes a couple of seconds to run on a MacBook Pro):