What is the smallest value of $n$ for which $\phi(n) \ne \phi(k)$ for any $k<n,$ where $n=4m$?

Solution 1:

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;
        }
    }
}