sigma ( phi ( n ) )   =   phi ( sigma ( n ) )

A tiny bit of history :
In his "Unsolved Problems in Number Theory" , 2e , 1994 , section B42 , Richard Guy considers 

  phi ( sigma ( n ) )  =  sigma ( phi ( n ) )
giving an expression of Golomb 
       p-1
  n = 3
and 5 solutions , for 
  p = 3 , 7 , 13 , 71 , and 103
He does not mention Fermat numbers , safe primes , nor Sophie Germain primes in this connection .
Now :
On this page , you will find
1) a "geometric" formula which produces thousands of odd solutions and
2) 2 more prosaic formulae which produce more than a billion even solutions and
3) a fascinating conjecture .
Odd solutions : 
           p-1
Golomb's  3    is the first of a sequence of sets of
solutions which are products of powers of consecutive
Fermat primes based on generalized repunit primes .

   p3-1
  3    ,

   p3-1  p5-1
  3     5    ,

   p3-1  p5-1   p17-1
  3     5     17     ,

   p3-1  p5-1   p17-1    p257-1
  3     5     17      257      , and

   p3-1  p5-1   p17-1    p257-1      p65537-1
  3     5     17      257       65537

are all solutions when all pertinent values of

         p65537        /  16
  ( 65537      - 1 )  /  2

         p257          /  8
    ( 257      - 1 )  /  2

         p17           /  4
     ( 17      - 1 )  /  2

         p5            /  2
      ( 5      - 1 )  /  2

  and    p3            /
      ( 3      - 1 )  /  2

are prime.
This requires  p3 , p5 , p17 , p257 , and p65537  to be prime .
The number of these odd solutions is , at least ,
10130 .

Conjecture :
There are no odd solutions of any other form for 

  phi ( sigma ( n ) )  =  sigma ( phi ( n ) )

Computation : 

The only odd solutions less than
80012456400  are :
          1
          9
        225
        729
      18225
      65025
     140625
     531441
    5267025
   11390625
   13286025
   18792225
   40640625
   87890625
 1522170225
 2197265625
 3291890625
 3839661225
 5430953025
 7119140625
 8303765625
11745140625
25400390625
These are all of the "geometric" form shown above .
Even solutions : 
The expression  2 * 3^e * 5 * 7506823 * 17^(p17-1) * p * q * r
produces at least  962950480  solutions .

For  prime p >= 11  with  (p-1) / 2  prime ,
and  prime q >= 11  with  (q-1) / 2  prime ,
and  prime r >= 11  with  (r-1) / 2  prime , and if
p+1  has no prime factors other than  2 , 3 , 13 , 19 , 29 , or 131 ,
q+1  has no prime factors other than  2 , 3 , 13 , 19 , 29 , or 131 ,
r+1  has no prime factors other than  2 , 3 , 13 , 19 , 29 , or 131 ,
with  p , q , and r  distinct ,
and  (17^p17-1) / 2^4  is prime ,
and  e = 1 or 2 ,
then  2 * 3^e * 5 * 7506823 * 17^(p17-1) * p * q * r is a solution .

There are  662  suitable values of each of  p , q , and r , <= 2^53 ,
and , at least , 7  suitable values of  p17 .
These give  673876280  solutions for the general expression , for which
the "bucket" of possible factors of  p+1  contains the 6 values :
2 , 3 , 13 , 19 , 29 , and 131 .
But by specializing the value  p17 = 3 , sigma ( 17^2 ) = 307  can be
added to the "bucket" giving  330  additional suitable values and
228145720  more solutions .
Additional values of  p17 = 5  give another  50057040 solutions , and
p17 = 7  another  10871440  solutions , for a total of  962950480
solutions , nearly a billion .


For  p = 2 or prime p >= 7  with  (p-1) / 2  prime ,
and  q = 2 or prime q >= 7  with  (q-1) / 2  prime ,
and  r = 2 or prime r >= 7  with  (r-1) / 2  prime , if
p+1  has no prime factors other than  2 , 3 , 7 , 19 , 661 , or 911 ,
q+1  has no prime factors other than  2 , 3 , 7 , 19 , 661 , or 911 ,
r+1  has no prime factors other than  2 , 3 , 7 , 19 , 661 , or 911 ,
with  p , q , and r  distinct ,
and  (17^p17-1) / 2^4  is prime ,
then  2^2 * 3 * 68647493 * 17^(p17-1) * p * q * r
is a solution .

There are  539  suitable values of each of  p , q , and r , <= 2^53 .
These give  181673723  solutions .
Sophie Germain primes , and their upper story , the safe primes , have played a key role in expediting the search for these solutions .
The expressions 
  2 * 3^e * 5 * 7506823 * 17^(p17-1) * p * q * r
  2^2 * 3 * 68647493 * 17^(p17-1) * p * q * r
were taken into captivity by searching for multiples of safe primes . 
Specifically ,
multiples of  2 * 17^2 * 11 * 23 * 47  were sought as solutions .

Because  phi ( a safe prime )  =  2 * a Sophie Germain prime ,
and , by the way , this expression may serve as
a very good definition of both types of primes ,
they have a gentle effect on the expression which is the argument
to  sigma ( )  in  sigma ( phi ( n ) ) .
Rather like a tetris .
Additional details and additional solutions in earlier writing :
In the original sigma ( phi ( ) ) : From "5" to "5 figures" appear 2 straight-forward methods which produced an odd number of odd solutions and even more even solutions to this elegant equation .
An update of additional odd solutions
A fragmentary update of additional even solutions

Oystein Ore's highly meritorious , even if slightly dated , "Number Theory and Its History" , McGraw-Hill , 1948 , has been reprinted .
Details may be found in this bibliography of abundancy .
Richard Guy's "Unsolved Problems in Number Theory" has been updated .
Also highly meritorious . 


A few definitions and examples :
sigma  is the multiplicative sum-of-divisors function and
  phi  is Euler's totient , i.e. , the number of coprime naturals < n .
One of the solutions is  9 .
phi ( 9 ) = 6 ,  because of  1 , 2 , 4 , 5 , 7 , and 8 .
sigma ( 6 ) = 1 + 2 + 3 + 6 = 12 .  ( 6 is thus perfect ) .
sigma ( 9 ) = 1 + 3 + 9 = 13 .  phi ( p ) = p - 1 , for  p  prime .
phi ( 13 ) = 12 .  Or as computed :
                                               sigma ( phi (n) ) =
        n      phi ( n )      sigma ( n )      phi ( sigma (n) )
        9              6               13                       12
2010 Mathematics Subject Classification : Primary 11A25 ; Secondary 11A05 , 11A41 , 11A51 , 11N25 , 11N80 , 11Y05 , 11Y11 , 11Y55 , 11Y70

Walter Nissen
2009-03-03
conjecture computation updated 2014-03-12