From: erick@sfu.ca (Erick Bryce Wong)
Subject: Re: Sum of Factors of an Integer
Date: 10 Dec 1999 23:43:34 GMT
Newsgroups: sci.math
Keywords: minimal value for sum of divisors function

Paul Bodenstab <prb@fc.hp.com> wrote:
>Does there exist a formula that gives the highest lower
>bound on the estimate of the sum of all prime factors of 
>a positive integer?
>
>For example, let N=12. The prime factorization of N is
>
>12=2*2*3
>
>so the sum of the factors is 2+2+3=7. 

The largest product you can get out of parts adding up to exactly n is
obtained by making all the parts equal to 3 with at most a couple 2's
left over.  So if the sum of the primes is, say 10 = 3+3+2+2, the number
is at most 3*3*2*2 = 36.  Conversely, any N > 36 cannot have F(N) = 10.
It remains to show a sufficient monotonicity to obtain F(N) > 10.

We have:

F(N) = 3k   implies N <= 3^k,
F(N) = 3k+1 implies N <= 2^2*3^(k-1) = (4/3)*3^k,
F(N) = 3k+2 implies N <= 2*3^k,

from  which we see that our upper bound for N, given F(N), is monotonic.
We may therefore safely invert it to get a lower bound for F(N) given N.

It grows as 3*log(N)/log(3) + C, where C varies between 0 and 0.2144...,
depending on how close N is to the next lowest power of 3.  As luck would
have it, 2 and 3 are both prime, so this bound is quite sharp :).

 -- Erick
==============================================================================

From: Kurt Foster <kfoster@rmi.net>
Subject: Re: Sum of Factors of an Integer
Date: Sat, 11 Dec 1999 04:38:20 GMT
Newsgroups: sci.math

In <82rqj6$jsi$1@fcnews.fc.hp.com>, Paul Bodenstab <prb@fc.hp.com> said:
. Does there exist a formula that gives the highest lower
. bound on the estimate of the sum of all prime factors of 
. a positive integer?
 [reply also E-mailed]

  Yes, F(n) >= (3/ln(3)) * ln(n), with equality precisely when n is an
integer power of 3.
  One way of proving this is as follows.  It is easy to show that, if A_1,
B_1, A_2 and B_2 are positive, and A_1/B_1 =< A_2/B_2, then

A_1/B_1 < (A_1+A_2)/(B_1+B_2) < A_2/B_2.

This result is then easily extended as follows:  If all A_i and B_i
are positive, and if

A_1/B_1 < A_2/B_2 < ... < A_k/B_k, then

A_1/B_1 < (A_1+A_2+...+A_k)/(B_1+B_2+...+B_k) < B_k.

  Now, let n = PRODUCT, p_i^a_i where the p_i are distinct primes and the
a_i are positive integers.  Then

 F(n) = SUM, a_i * p_i, and
ln(n) = SUM, a_i * ln(p_i).

Now x/ln(x) is increasing for x > e; 2/ln(2) = 4/ln(4), hence

3/ln(3) < 2/ln(2) < 5/ln(5) < 7/ln(7) < 11/ln(11) < ...

Using the previous result we have, if n has more than one prime factor,

MIN, p|n, p/ln(p) < F(n)/ln(n) < MAX, p|n, p/ln(p)

Therefore, the smallest possible value of F(n)/ln(n) is 3/ln(3), and it
only occurs precisely when n is an integer power of 3.