Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I checked up to 10^7 and found no examples. I'll run something overnight and see how far it gets. –  Matthew Conroy Feb 1 '11 at 0:57
    
Shoot: Pari/GP has a bound on vectors somewhere less than 1.7x10^7. I'll have to use a different method. –  Matthew Conroy Feb 1 '11 at 4:08
    
I wrote a quick program to compute some values of your function ($\Phi$ that is). It seems like you should certainly be able to get a better lower bound. I've computed into the twenty thousands and the ratio of the terms appears to be approaching 1/5 for instance $\Phi(25000)=5032$. It may be going lower, I'll let it run over night and see how far it gets. It may actually be slowing down more now that I look at a few values. –  JSchlather Feb 1 '11 at 8:24
    
@Matthew: Thanks for that! It makes me glad that I decided to give up on the hand calculations, post the question and go to bed. Please let me know if your program finds a solution. Thanks. –  Derek Jennings Feb 1 '11 at 9:31
    
@Jacob: Thanks for your time. I, too, think that a better lower bound than that implied by the PNT should be within reasonable reach, but I haven't yet given much thought to that side. My question arose when I was looking at the upper bound. Thanks for posting those numbers. I'm still trying to understand the behaviour of $\Phi(n),$ so please let me know if you have any further interesting results. Thanks. –  Derek Jennings Feb 1 '11 at 9:39
show 5 more comments

1 Answer

up vote 11 down vote accepted

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;
        }
    }
}
share|improve this answer
1  
+1: Nice one! Thanks. –  Derek Jennings Feb 14 '11 at 21:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.