Re: counting divisors/submultisets

On Jan 2, 4:19 am, hv <h...@xxxxxxxxx> wrote:
On Jan 1, 10:21 pm, Robert Israel <isr...@xxxxxxxxxxx> wrote:



On Dec 31 2007, 5:08 am, hv <h...@xxxxxxxxx> wrote:
On Dec 31, 3:58 am, Robert Israel
<isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
hv <h...@xxxxxxxxx> writes:
To do so, however, I believe I need to understand the solution to a
subproblem: finding tau_k(n) = |{ d : d | n, \Omega(d) == k }|. That
is to say, the number of divisors of n that have precisely k (not
necessarily distinct) prime factors. This is equivalent to finding the
number of k-element submultisets of a multiset that has multiplicities
corresponding to the prime powers in n.

I'd think of it this way: given nonnegative integers n_1,...,n_m (the
multiplicities) you want to count the number of m-tuples (x_1,...,x_m)
such that 0 <= x_i <= n_i for all i, and sum_i x_i = k. This is the
coefficient of t^k in G(t) = product_{i=1}^m (1 + t + ... + t^{n_i})
= (1-t)^(-m) product_{i=1}^m (1-t^{1+n_i}).
Another way to get it is with recursion: you want
F_m(n_1,...,n_m; k) where
F_1(n_1; j) = 1 for 0 <= j <= n_1, 0 otherwise,
and
F_{m+1}(n_1,...,n_{m+1};j)
= sum_{i=max(0,j-n_1-...-n_m)}^{min(j,n_{m+1})} F_m(n_1,...,n_m; j-i)

Thanks Robert - when you put it like that it doesn't look so
promising.

I also considered constructing them in another way, with another
auxiliary
function: given n = prod{p_i^a_i}, let g_k = |{ i : a_i >= k }|. Then
we get:
tau_1(n) = g_1
tau_2(n) = C(g_1, 2) + g_2
tau_3(n) = C(g_1, 3) + g_2(g_1 - 1) + g_3
etc. But that's essentially iterating over partitions, and doesn't
offer me
any additional hope for a closed form or fast calculation.

However I have observed (and do not know how to prove) that it seems:
sum{k == 0 (mod 2)}{tau_k(n)} = ceil(tau(n)/2)
sum(k == 1 (mod 2)}{tau_k(n)} = floor(tau(n)/2)
and this was one of the things that gave me hope further regularity
could
be found, and perhaps that prior study of sum C(n,k) over arithmetic
progressions of k would provide hints as to where to look for more.

Hugo

Well, this should be one of the things the generating function is good
for. If tau_k(n) is the coefficient of t^k in G(t),
the sum of tau_k(n) for even k is (G(1) + G(-1))/2. Now, as I said,
G(t) = product_{i=1}^m (1 + t + ... + t^{n_i})
so G(1) = product_i (n_i+1) = tau(n).
If any n_i is odd, G(-1) = 0,
making (G(1) + G(-1))/2 = tau(n)/2.
If all n_i are even, tau(n) is odd and G(-1) = 1, so
(G(1)+G(-1))/2 = (tau(n)+1)/2 = ceil(tau(n)/2).

More generally, I guess you could look at the sum of tau_k(n)
for k in a congruence class mod p, and relate this to the values
of G at the p'th roots of unity.

Robert Israel isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Ah, gotcha, it hadn't occurred to me you could do things like that
with the generating function. I had better go read up on them a bit.

For mod 3, and with n = \prod{i=1..m}{p_i^a_i} I then get:

Let k = sum{ c(a_i==1 (mod 3)) }

G_3 = G(1) + G(1^(1/3)) + G(1^(2/3)) = tau(n) +
{ 0 (exists i: a_i==2 (mod 3))
{ 2 (k==0 (mod 6))
{ 1 (k==1 (mod 6) or k==5 (mod 6))
{ -1 (k==2 (mod 6) or k==4 (mod 6))
{ -2 (k==3 (mod 6))

.. which nicely generates the count of divisors with 0 (mod 3) factors
as G_3/3. I don't immediately see how to extend that to yield a count
for 1 or 2 (mod 3), but I'll go away and try a few things out.

Thanks very much,

Hugo

Let w be a primitive cube root of 1.
If w is a primitive cube root of 1, I get G(w) = 0 if some a_i == -1
mod 3, otherwise (1+w)^K = (-1/w)^K where K is the number of a_i == 1
mod 3.

The sum of tau_k(n) for k == 1 mod 3 is
(G(1) + 1/w G(w) + w G(1/w))/3.
The sum of tau_k(n) for k == 2 mod 3 is
(G(1) + w G(w) + 1/w G(1/w))/3.

If some a_i == -1 mod 3 we have G(w) = G(1/w) = 0 so the counts for k
== 0, 1 and 2 mod 3 are all tau(n)/3.
Otherwise, let K be the number of a_i == 1 mod 3. Then I get
G(w) = (-1/w)^K and G(1/w) = (-w)^K, so the counts should be (tau(n)
+a(k,K))/3, where a(k,K) is given by the following table, the columns
being labelled by K mod 6 and the rows by k mod 3:

0 1 2 3 4 5
------------------
0 | 2 1 -1 -2 -1 1
1 | -1 1 2 1 -1 -2
2 | -1 -2 -1 1 2 1

--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada


.

Relevant Pages

  • Re: counting divisors/submultisets
    ... necessarily distinct) prime factors. ... number of k-element submultisets of a multiset that has multiplicities ... If all n_i are even, tauis odd and G= 1, so ... I guess you could look at the sum of tau_k ...
    (sci.math)
  • Re: counting divisors/submultisets
    ... number of k-element submultisets of a multiset that has multiplicities ... this should be one of the things the generating function is good ... If all n_i are even, tauis odd and G= 1, so ... I guess you could look at the sum of tau_k ...
    (sci.math)
  • Re: counting divisors/submultisets
    ... be found, and perhaps that prior study of sum Cover arithmetic ... If all n_i are even, tauis odd and G= 1, so ... with the generating function. ... Let w be a primitive cube root of 1. ...
    (sci.math)
  • Re: While statement
    ... > sum off all the odd numbers. ... > inputed value some of the eben integers and sum of odd integers. ... > start loop ... It sounds like your pseudocode will more or less actually do what the ...
    (comp.lang.java.programmer)
  • Re: Enigma 1539 - Board with numbers
    ... consists of a 10-by-10 grid of squares. ... Since successive rows have numbers in opposite orders, the sum of pairs of numbers in consecutive rows is a constant for a given pair of rows - that is, it doesn't change with column number. ... We can choose r so that it's odd ...
    (rec.puzzles)