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 = 3and 5 solutions , for

p = 3 , 7 , 13 , 71 , and 103He 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 * rwere 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 122010 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