Product of sigma(k)/phi(k)
hv at crypt.org
hv at crypt.org
Fri Jul 8 17:55:15 CEST 2005
Earlier I wrote:
:The limiting factor seems to be powers of 2: let o(n) represent the
:index of the highest power of 2 dividing n. sigma(n) and phi(n) are
:both multiplicative, so we can calculate the contributions from the
:individual prime power factors independently.
:
:If n is divisible by 2^k, the contribution to o(sigma(n)) is 0 since
:sigma(2^k) is odd; the contribution to o(phi(n)) is (k-1).
:
:If n is divisible by p^k for some odd prime p, it looks like the
:contribution to o(sigma(n)) is o(p+1) + o((k+1)/2) for odd k, and
:0 for even k; the contribution to o(phi(n)) is o(p-1) for all k.
:
:If I have this right, the average contribution to o(sigma(n)) from p^k
:for arbitrary k is (o(p+1) + 1)/2, which simplifies to 3/2 when averaged
:over arbitrary p; the contribution to o(phi(n)) similarly averages to 2.
:(Making substantial assumptions about the distribution of primes, of
:course.)
This is wrong - I treated p^k as occuring with probability 1/2^k instead
of (p-1)/p^k, so the average contribution to o(sigma(n)) from p^k is less
than stated here; over arbitrary k it averages to:
p(p-1)/2 . [ o(p+1)/p^2 + sum_{i=1..\inf}{ 1 / p^(2^i) } ]
.. which is a bit less than p/(p+1) . (o(p+1) + 1)/2.
(Does sum {1/x^(2^i)} have a known formula?)
The rest of the argument is still valid, only slightly more so.
:Thus the greatest power of 2 in the phi product will tend to be
:increased a bit more than in the sigma product for odd p^k factors,
:and much more for 2^k factors; it is random enough to allow the sigma
:product to edge ahead for some early values, but as n increases the
:phi product must get and stay ahead.
:
:I'd welcome a more rigorous treatment.
Hugo
More information about the SeqFan
mailing list