18
$\begingroup$

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

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 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.

  • 0
    @Jacob Schlather: If your program ran overnight to get to 270000, you might glean some ideas for optimization from the Java code I posted along with the answer ;-)2011-02-14

1 Answers 1

12

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

import java.util.Arrays;  public class Totient {     final static int mod4 = 0;     // remainder mod 4 to test                                                                                                                                                                                                                           final static int n = 40000000; // highest number to test                                                                                                                                                                                                                             static boolean [] prime = new boolean [n / 2]; // prime [i] : is 2i + 1 prime?                                                                                                                                                                                                      static boolean [] seen = new boolean [n];      // seen [i] : we've seen phi (n) = i                                                                                                                                                                                                 static int [] phi = new int [n];               // phi [i] : phi (i)                                                                                                                                                                                                                  public static void main (String [] args) {         Arrays.fill (prime,true);         Arrays.fill (seen,false);         Arrays.fill (phi,1);          // calculate the primes we need                                                                                                                                                                                                                                                     int limit = (int) Math.sqrt (n); // highest factor to test                                                                                                                                                                                                                          for (int p = 3;p <= limit;p += 2) // loop over odd integers                                                                                                                                                                                                                             if (prime [p >> 1])            // only test primes p                                                                                                                                                                                                                                    for (int k = 3*p;k < n;k += 2*p) // loop over odd multiples of p                                                                                                                                                                                                                        prime [k >> 1] = false;      // sieve them out                                                                                                                                                                                                                           // fill phi by looping over all primes                                                                                                                                                                                                                                              fill (2);         for (int p = 3;p < n;p += 2)             if (prime [p >> 1])                 fill (p);          // now go through phi, remembering which values we've already seen                                                                                                                                                                                                                  for (int i = 1;i < n;i++) {             if ((i & 3) == mod4 && !seen [phi [i]]) {                 System.out.println ("found " + i + " with phi (" + i + ") = " + phi [i]);                 return;             }             seen [phi [i]] = true;         }     }      // multiply all phi values by their factors of prime p                                                                                                                                                                                                                              static void fill (int p) {         // once for the first factor of p                                                                                                                                                                                                                                                   for (int i = p;i < n;i += p)             phi [i] *= p - 1;          // and then for the remaining factors                                                                                                                                                                                                                                               long pow = p * (long) p; // long to avoid 32-bit overflow                                                                                                                                                                                                                           while (pow < n) {             for (int i = (int) pow;i < n;i += pow)                 phi [i] *= p;             pow *= p;         }     } } 
  • 1
    @Adam: Of course not. "Level of insight" isn't a relevant category here. A question was asked, and I answered it. If you'd written "Posting a programme doesn't demonstrate any insight", I would have fully agreed. That's not what you wrote, though. You wrote "this does not qualify as an answer". It does, and $11$ people agree with me on that. If you don't agree, you can downvote.2018-09-30