### 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 :
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
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 .
```
```
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