Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP
Newsgroups: ut.theory
Subject: THEORY NET: an answer ...
Message-ID: <5227@utcsri.UUCP>
Date: Mon, 10-Aug-87 21:22:30 EDT
Article-I.D.: utcsri.5227
Posted: Mon Aug 10 21:22:30 1987
Date-Received: Tue, 11-Aug-87 06:24:20 EDT
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 57

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.