# [seqfan] Re: Asymptotic for A074753

drew at math.mit.edu drew at math.mit.edu
Wed Jan 13 15:44:15 CET 2010

I believe you can obtain asymptotic lower (and upper) bounds on a(n)/n by
applying the results of

[1] "Density Bounds for the Sum of Divisors Function", Charles R. Wall,
Phillip L. Crews and Donald B. Johnson, Mathematics of Computation, Vol.
26, No. 119, 1972, pages 773-777,

which builds on earlier work by Behrend and Davenport (from 1933). The
reference above is available online at http://www.jstor.org/stable/2005106.
The bound one can obtain is certainly not tight, but it is above 0.36.

I realize that not everyone on this list has convenient access to JSTOR, so
I will briefly summarize the key points that are relevant to A074753.

Let pi_A(N,x) count the positive integers m <= N for which sigma(m) >= mx,
where x is a real number in the interval [1,5].

It was proven by Davenport (see reference in [1]) that

A(x) = lim_{N\to\infty} pi_A(N,x)/N

exists and is a continuous function of x. The reference [1] above gives a
table of upper and lower bounds for A(x) for x = 1.0, 1.1 ...., 4.9, 5.0,
for example, A(2) lies between 0.2441 and 0.2909.

For a(n)=A074753(n), we may use this table to asymptotically bound a(n)/n.
Indeed, for any real number x in [1,5] and positive integer n we have

(*)    floor(n/x) - pi_A(n/x,x) <=  a(n)

This is obtained by counting integers m <= n/x for which sigma(m) < mx <= n.

Dividing (*) by n and taking limits as n tends to infinity yields

(**)   lim inf a(n)/n >= (1-A(x)) / x.

>From Table 1 of [1], we have A(2.1) <= .2372, which implies that

(1)   lim inf a(n)/n > 0.363238.

This bound above can be likely be improved slightly by further subdividing
the interval from [1,n] and applying multiple bounds on A(x).

Regards,

Drew

> On Jan 12, 2010, at 9:22 AM, franktaw at netscape.net wrote:
>
> Since my last asymptotic question got no response :-(, I thought I
> would try another one :-).
>
> For a(n) = http://www.research.att.com/~njas/sequences/A074753 (Number
> of integers k such that sigma(k) < n), what is the limit n->infinity
> a(n) / n?
>
> Up to 1 million, it appears to be about .673.
>
> Certainly the limit is less than 1; any 2k > 2n/3 will have sigma
> (2k) >
> n, so the limit must be < 5/6.  Similar arguments with other factors
> can refine this; looking only at prime factors up to 100000, I get an
> upper bound of .7044..., and this clearly converges to something in
> this neighborhood.  I don't see any way to prove the actual limit is >
> 0, however.
>