Smallest $k$ such that $\phi(\phi(\phi(…_k(\phi(n)))))=1$

abstract-algebraprime numberssequences-and-seriestotient-functionupper-lower-bounds

Let $\phi$ be Euler's totient function and $n$ be a positive integer. Let $\phi^k(n)$ denote $k$ sucessive applications of the totient function.

Since $\phi(n)<n$ for all $n\geq 2$, we know that $\exists k|\phi^k(n)=1$ and we can pick a minimal such $k$.

Question Are there known asymptotic upper bounds on this better than the trivial $k<n$?

We know that $\phi(n)=n-1$ if $n$ is prime. Trivially, $k<n$.

However this upper bound becomes stronger when one accounts for composite numbers: for example, $\phi(n)\leq n-n^{1/2}$ if $n$ has at least $2$ distinct factors. Can we do better than $k<n$?

Best Answer

$\phi(2m)\leq m,$ and $\phi(n)$ is even except when $\phi(n)=1.$ So you get $k\leq 1+\log_2(n-1).$

This upper bound can be achieved when $n=2^{2^j}+1$ is a Fermat prime. There might only be finitely man such $n,$ but we can’t do much better for large $n,$ since when $n=2^m,$ $k=m=\log_2(n).$ Indeed, $\lfloor 1+\log_2(2^m-1)\rfloor =m,$ so this is a maximum again.

Related Solutions

Number Theory – Smallest n with Unique Totient Function Value

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

[Math] Show that the only solution to $\phi(n) =n-2$ is $n=4$

$\varphi(n)$ is even for every $n \ge 3$, so you would need $n$ to be even as well. However, if you write $n = 2^k m$, $m$ odd, then $$ n - 2 = \varphi(n) = \varphi(2^k) \varphi(m) = 2^{k-1} \varphi(m) \le 2^{k-1} m = \frac{n}{2}$$ which severely limits the possibilities for $n$.

Best Answer

Related Solutions

Number Theory – Smallest n with Unique Totient Function Value

[Math] Show that the only solution to $\phi(n) =n-2$ is $n=4$

Related Question