Product of sigma(k)/phi(k)
hv at crypt.org
hv at crypt.org
Thu Jul 7 00:13:14 CEST 2005
Max <relf at unn.ac.ru> wrote:
:Leroy Quet wrote:
:> Let sigma(k) = sum{j|k} j.
:> Let phi(k) be the number of positive integers <= k and coprime to k.
:>
:> Then for which n's is
:>
:> product{k=1 to n} sigma(k)/phi(k)
:>
:> an integer?
:
:I've got
:1 2 3 4 6 7 8 14 15
:and no other n up to 10000.
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.)
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