arvind@utcsri.UUCP (08/11/87)
Date: Mon, 10 Aug 87 13:55:00 EDT
From: Don Coppersmith <copper@ibm.com>
Subject: an answer to the problem of Don Saari
Theorem: Define
f(n) = sigma(n) - n
= sum of all divisors of n except n itself.
Then the range of n has density at most 47/48 < 1.
Notation: a*b is multiplication, a**b is exponentiation.
Proof: consider integers n such that f(n) is divisible by 12,
and f(n)<N, sorted by the residue n mod 12 = sigma(n) mod 12.
n mod 12 = 0
Then sigma(n)/n >= (7/4)(4/3) = 7/3
N > sigma(n)-n > 4n/3
n < 3N/4, n divisible by 12.
The number of such n is at most (1/12)(3N/4) = N/16.
n mod 12 = 2, 6, or 10.
Since each odd prime occurring to an odd power contributes
at least a factor of 2 to sigma(n), and sigma(n) has only
one factor of 2, we have n=2*p*(s**2), where p is a prime.
Such numbers have density 0.
Also N > sigma(n)-n > (3/2)n - n = n/2, so n<2N.
So the number of such n is o(2N)=o(N).
n mod 12 = 4 or 8.
No primes of the form 6k-1 occur to an odd power in n
(or else 3 would divide sigma(n)). Such n have 0 density.
Further, N > sigma(n)-n > (7/4)n - n = 3n/4, so n<4N/3.
Again the number of such n is o(4N/3)=o(N).
n mod 12 = 1, 5, 7, or 11.
No odd primes occur to an odd power (and 2 doesn't occur at all).
n = s**2. Further no prime p of the form 6k+1 occurs to
the FIRST power in s. (If s is divisible by such p, then it's
divisible by at least p**2.) N>s. The number of s<N of
with no prime p=6k+1 occurring with exponent exactly 1, is
o(N).
n mod 12 = 3 or 9.
n is divisible by 3, so N > sigma(n)-n > (4/3)n - n = n/3,
so n<3N. No prime occurs to odd power, so the number of
such n is less than sqrt(3N) = o(N).
Summing, the number of integers less than N, divisible by 12
which are f(n) for some n, is at most N/16 + o(N),
while there are N/12 integers less than N divisible by 12.
So there are at least N/48 integers less than N, divisible by 12,
outside the range of f, and the density of the range of f is at most
1 - ( (1/12) - (1/16) ) = 47/48.
Don Coppersmith, COPPER@YKTVMV
August 10, 1987.