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