when is the sum of divisors[n] prime?

[Simon Colton]

Dear Wouter,

Thanks for taking an interest in the theorem.

> I got stuck where I need to show that
> "Sum[p^i,{i,0,n}] factors if n is non-prime"
> Does rhat follow from Fermat's little one?

I'm not sure why you need to show that 
Sum[p^i,{i,0,n}] factors if n is non-prime

The theorem was

for all n,
tau(sigma(n)) = 2 -> tau(tau(n)) = 2.

and the proof was (sorry about the ascii)

a) Take an n for which tau(sigma(n)) = 2.

b) tau(sigma(n)) = 2 -> n = p^m (p prime, m in N)
   By Thm. 275, Hardy and Wright.

c) Suppose tau(tau(n)) != 2. ie. tau(n) is composite.
   Therefore, tau(n) = xy for x>1, y>1.
   Then tau(n) = tau(p^m) = m+1 = xy.
   So m = xy - 1.

We now look for a contradiction:

d) By Thm. 275 of Hardy and Wright,
   sigma(n) = 1 + p + p^2 + ... + p^{xy-1}
   and #this# can be factorised:

   1 + p + p^2 + ... + p^{xy-1} 
   = (1 + p + ... + p^{x-1})(1 + p^x + p^{2x}... + p^((y-1)x))
   = Sum[p^i,{i,0,x-1}]Sum[p^{(y-i)x},{i,1,y}]

e) This is a contradiction, as sigma(n) factorises 
   non-trivially, but sigma(n) was taken to be prime.

Hence, I think you wanted to show that 
Sum[p^i,{i,0,n-1}] factors if n is non-prime.

By the way, Robert Wilson brought to light yesterday that
an immediate corollary of the theorem is that:

tau(sigma(n)) = 2 -> tau(tau(n)) = tau(sigma(n))

(as both sides of the rhs equality are 2).

Therefore, this sequence:

n s.t. tau(tau(n)) = tau(sigma(n)), which Robert Calculated as:

1, 2, 4, 9, 16, 18, 25, 50, 64, 144, 289, 576, 578,
729, 1458, 1600, 1681, 2401, 2916, 3362, 3481, 3600, 4096, 4624, 4802,
5041, 6962, 7921, 9604, 10082, 10201, 11664, 15625, 15842, 17161, 18225,
18496, 20402, 21609, 24400, 26896, 27889, 28561, 29929, 31250, 34322,
36450, 36864, 43218.
(not in the encyclopedia yet).

is also a supersequence of A023914, as well as the sequence of
integers for which tau(n) is prime (soon to be A009087).

Also, the conjecture found by HR generalises, I think, to a 
more interesting result:

for all n in N, 
tau(sigma_k(n)) = 2 -> tau(tau(n)) = 2,

where sigma_k(n) is the sum of the kth powers of the divisors of n.
The above proof, with a little tweaking should prove this.

Unfortunately, the more general conjecture:
for all a,b,n in N,
tau(sigma_a(n)) = 2 -> tau(sigma_b(n)) = 2,

is not true.

The first counterexample I've found is a=4, b=3, n=2,
because tau(sigma_4(2)) = tau(17) = 2, but
        tau(sigma_3(2)) = tau(9) = 3.

I would like to know if there are any pairs (a,b) for which 
the above more general theorem is true, other than the
pairs (a,0), which we've shown to be true.

Cheers,

Simon
---------------------------------
http://www.dai.ed.ac.uk/~simonco/