Re: counting divisors/submultisets

On Jan 2, 10:38 pm, Robert Israel <isr...@xxxxxxxxxxx> wrote:
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 isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

I conjecture that this generalizes as:

sum{k=0..tau(n), k==v (mod m)}{tau_k(n)}
= 1/m sum{k=1..m}{w_m^(-kv) G(w_m^k)}

where w_m is any (fixed) primitive m'th root of 1.

I won't have time to work further on this for a couple of days, but I'll try to pick it up again at the weekend.

Well, maybe I just won't be able to leave it alone. :)

Hugo
.

Relevant Pages

  • 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: 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: Fortran vs Python - Newbie Question
    ... crunching" involves anything beyond linear systems, run, don't walk, to ... the foibles of numerical computation, ... square root, then do the sum and the difference of the square root with ... either the sum or the difference will be a difference between two ...
    (comp.lang.python)
  • Re: Numerical for you ....from vectors
    ... other when placed tail to tail.Prove,by taking components along two ... Say that the vector c is the sum of a and b. ... To simplify the computation we can look at the square of the magnitude of c so we do not have to carry on any square root until the final answer. ...
    (sci.math)
  • Re: counting divisors/submultisets
    ... number of k-element submultisets of a multiset that has multiplicities ... be found, and perhaps that prior study of sum Cover arithmetic ... If all n_i are even, tauis odd and G= 1, so ... Let w be a primitive cube root of 1. ...
    (sci.math)