Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find all triplets of $a, b,c$ such that $abc=200$ provided that $a,b,c$ are positive integers. How to approach this?

$$abc=(5^2) (2^3)$$

Then how to select $a,b,c$?

What will be the general approach if we have something like $$abcde.....=k$$

share|improve this question
    
I'm confused with what you mean by abcde....=k –  mez Jan 24 '13 at 20:34
    
As you've noted, by considering the prime decomposition of $k=p_1^{k_1}p_2^{k_2}...p_n^{k_n}$ and your factors $a=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$ so the problem reduces to finding vectors $A=(a_1,a_2,...,a_n)$ which sum to $K=(k_1,k_2,...,k_n)$, so $k_1=a_1+b_1+c_1+...$ etc. –  Shard Jan 24 '13 at 20:34
    
k is any positive constant. –  Bazinga Jan 25 '13 at 12:52

2 Answers 2

The first observation is that the number of decompositions for $n = abc$ depends only on the exponents (the shape) of the prime factorization of $n$. Suppose $$ n = p_1^{w_1} p_2^{w_2} p_3^{w_3} \cdots p_k^{w_k}.$$ Then we are distributing combinations (cartesian products) of objects of $k$ different types (one for each prime $p_m$) into three slots, where each object may occur between $0$ and $w_m$ times. Say the objects of type $p_m$ are represented by the variable $v_m.$ The slots are being permuted by the symmetric group $S_3$, with cycle index $$ Z(S_3) = \frac{1}{6} \left( a_1^3 + 3 a_1 a_2 + 2 a_3 \right).$$ It follows by Polya's enumeration theorem that the count we are looking for is given by the coefficient $$ [v_1^{w_1} v_2^{w_2} v_3^{w_3} \cdots v_k^{w_k} ] Z(S_3)$$ evaluated at $$a_1=g(v_1, v_2, v_3, \ldots v_k)\\ a_2=g(v_1^2, v_2^2, v_3^2, \ldots v_k^2) \\ a_3=g(v_1^3, v_2^3, v_3^3, \ldots v_k^3).$$ where $$g(v_1, v_2, v_3, \ldots v_k) = \prod_{m=1}^k \sum_{j=0}^{w_m} v_m^j.$$ The product above ensures that we get all possible combinations of objects. It is these combinations that go into the slots. The procedure is the same for a different number $q$ of factors, you just replace the symmetric group on $3$ elements with the one on $q$ elements.

Maple code to calculate this follows.


cnt1 :=
proc(n)
        option remember;
        local a, b, c, cnt, s;

        s:= {};

        for a to n do
            for b from a to n do
                for c from b to n do
                    if a*b*c = n then
                       s := s union {convert([a,b,c], multiset)};                       
                    fi;
                od;
            od;
        od;

        nops(s);
end;

pet_varinto_cind :=
proc(poly, ind)
           local subs1, subs2, polyvars, indvars, v, pot, res;

           res := ind;

           polyvars := indets(poly);
           indvars := indets(ind);

           for v in indvars do
               pot := op(1, v);

               subs1 := 
               [seq(polyvars[k]=polyvars[k]^pot, 
               k=1..nops(polyvars))];

               subs2 := [v=subs(subs1, poly)];

               res := subs(subs2, res);
           od;

           res;
end;

cnt2 :=
proc(n)
        local f, p, t, v, ind, gf;

        f := op(2, ifactors(n));
        p := 1;

        v := 1;

        for t in f do
            p := p * add(cat('v', v)^k, k=0..t[2]);
            v := v+1;
        od;

        ind := 1/6*(a[1]^3+3*a[1]*a[2]+2*a[3]);
        gf := expand(pet_varinto_cind(p, ind));


        v := 1;

        for t in f do
            gf := coeff(gf, cat('v', v), t[2]);
            v := v+1;
        od;

        gf;
end;

share|improve this answer
    
Here is the result for six factors instead of three, starting at the value at $n=10000$: $$ 105, 2, 5, 2, 11, 15, 2, 1, 52, 1, 52, 5, 4, 5, 5, 2, 19, 21, 2, 2, 36, 2, 2, 5, 21, 4, 11, 2, 11, 2, 15, 2, 140, 2, 5, 11, 11, 1, 15, 1, 21, 2, 2, 4, 97, 11, 2, 5, 29, 2, 36 $$. These would of course be impossible to compute by brute force, as $10000^6 = 1000000000000000000000000.$ –  Marko Riedel Jan 24 '13 at 22:00
    
The cycle index in the case of six factors is $$Z(S_6) = {\frac {1}{720}}\,{a_{{1}}}^{6}+1/48\,{a_{{1}}}^{4}a_{{2}}+1/18\,{a_{{1}}}^{3}a_{{3}}+1‌​/16 \,{a_{{1}}}^{2}{a_{{2}}}^{2}+1/8\,{a_{{1}}}^{2}a_{{4}}+1/6\,a_{{1}}a_{{2}}a_{{3}‌​}+1/5\,a_{ {1}}a_{{5}}\\+1/48\,{a_{{2}}}^{3}+1/8\,a_{{2}}a_{{4}}+1/18\,{a_{{3}}}^{2}+1/6\,a_‌​{{6}}.$$ Code to compute these cycle indices is available on request. –  Marko Riedel Jan 24 '13 at 22:07

The previous answer from an hour ago does not do any overcounting. If you are willing to do some overcounting, you can get your complexity down to the number of prime factors of $n$ counted according to multiplicity. That avoids using the cycle index. You factor $n$ and go though all possible assignments of primes to slots. There is some overcounting here, so you still need to check for duplicates. While the brute force algorithm is $\Theta(n^q)$, this will get you $\Theta(q^K)$, with $K$ the total number of prime factors according to multiplicity. Now $K$ is $O(\log_2 n)$, so this is $O(q^{log_2 n}) = O(2^{\log_2 q \log_2 n}) = O(n^{\log_2 q}).$ We are doing better than brute force on average but we still get an exponential worst case for powers of $2$, say $2^w$, which has complexity $q^w.$ So in the end, the cycle index algorithm wins. The salient feature is that the below algorithm preserves the factorizations of the solutions, where as the cycle index algorithm really just counts and we cannot reconstruct the factorizations from the output.

This is the code.

cnt_fact :=
proc(n, slots)
        option remember;
        local f, pfacts, t, pot, allsols, pos, ppos, c, sol, p;

        f := op(2, ifactors(n));

        pfacts := [];

        for t in f do
            for pot to t[2] do
                pfacts := [op(pfacts), t[1]];
            od;
        od;

        allsols := {};

        for pos from 0 to slots^nops(pfacts)-1 do
            sol := [seq(1, k=1..slots)]; ppos := pos;

            for c from 1 to nops(pfacts) do
                p := pfacts[c];
                sol[1+(ppos mod slots)] := sol[1+(ppos mod slots)] * p;
                ppos := iquo(ppos, slots);
            od;

            allsols := allsols union
            {convert(convert(sol, multiset), set)};
        od;

        nops(allsols);
end;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.