### sigma ( phi ( ) ) : From "5" to "5 figures"

```(a) an elegant equation with 5 published solutions  and
(b) 2 straight-forward methods which produce 4509 odd solutions and
14000 even solutions.

In his "Unsolved Problems in Number Theory", 2e, 1994, section B42,
Richard Guy gives an expression of Golomb, and 5 solutions, for
phi ( sigma ( n ) ) = sigma ( phi ( n ) )
noting that for  p = 3, 7, 13, 71, and 103;  n = 3 ^ (p-1) .
He does not mention Fermat numbers in this connection.

Fermat numbers are of the form  2 ^ 2^n  +  1.  E.g.,
for  n = 0, 1, 2, 3, and 4,  they are  3, 5, 17, 257 and 65537.
These are the only known primes of such form.

sigma  is the multiplicative sum-of-divisors function and
phi  is Euler's totient, i.e., the number of relatively prime 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:
(I hope you are reading this in fixed pitch)
sigma ( phi (n) ) =
n      phi ( n )      sigma ( n )      phi ( sigma (n) )
9              6               13                       12

p-1
I note that Golomb's  3    is the first of a sequence of products of
powers of consecutive Fermat 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.  p3, ..., p65537 are primes.

There are at least 4509 of these odd solutions.
Are there odd solutions of any other form?

Conjecture.   It would seem possibly not.  None are < 306766128 .

smallest suitable values
------ -----------------------------------------------------------------
p3     3,     7,     13,     71, 103,         541,      1091, 1367, 1627
p5     3,     7, 11, 13, 47,      127, 149, 181, 619, 929
p17    3, 5,  7, 11,     47, 71,             419
p257                   23, 59
p65537        7, 11

The first five of these, in the first line, are those given by Golomb.
E.g., the last value in the second line,  929,  is included because
( 5^929 - 1 ) / 4  is prime and
59  is included because  ( 257^59 - 1 ) / 256  is prime.

cardinalities (so far)
exponents                       solutions
#p3      >=  9                  9                   >=    9
#p5      >= 10                  9 * 10              >=   90
#p17     >=  7                  9 * 10 * 7          >=  630
#p257    >=  2                  9 * 10 * 7 * 2      >= 1260
#p65537  >=  2                  9 * 10 * 7 * 2 * 2  >= 2520
----
total number of small solutions verified (so far)   >= 4509

Examples:

3-1  3-1
3    5     =  225  is a solution where  3  is a prime and

3                   3
( 3 - 1 ) / 2  and  ( 5 - 1 ) / 4  are each prime.

-

1627-1  929-1   419-1    59-1      11-1
3       5      17      257     65537

is a solution where  1627, 929, 419, 59, and 11  are primes and

1627               929                419
( 3    - 1 ) / 2 , ( 5   - 1 ) / 4 , ( 17   - 1 ) / 16 ,

59                         11
( 257  - 1 ) / 256 , and ( 65537  - 1 ) / 65536  are each prime.

-

Turning from odd solutions to even solutions, this gives at least 14000
solutions:

For  p = 7  or  prime p >= 59,  if  (p-1)/2  and  (5^p5-1) / 2^2  are
prime, and  p+1  has no prime factors other than  2, 3, 5, 7, and 79,
then  2^5 * 3 * 5^(p5-1) * 23^2 * 29 * p  is a solution.

There are 1400, exactly, suitable values of  p  with both sigmas <=
2^53,  the least of which are  p = 7, 59, 83, 107, 167, 179, 359, 383,
479, 503, 587, 719, and 839.  The greatest of these 1400 least is
p = 8795354824703999.  Each of these 1400 may be paired with a  p5
taken from, at least, these 10 values:  3, 7, 11, 13, 47, 127, 149, 181,
619, and 929.

The least of the resulting 14000 solutions has  p5 = 3  and  p = 7  and
is  2^5 * 3 * 5^2 * 23^2 * 29 * 7  =  257728800.
sigma ( phi (n) ) =
n      phi ( n )      sigma ( n )      phi ( sigma (n) )
257728800       54405120       1036808640                226437120

There are dozens of similar expressions which collectively provide
many thousands of additional even solutions.

Walter Nissen
2000-11-14
```