# Multiplicative Partitions $abcd=2^8\cdot 3^8$

Suppose $a,b,c,d$ are positive integers and $abcd=2^8\cdot 3^8$.

We consider permutations of an $(a,b,c,d)$ solution identical.

For example, solutions $(1,1,1,2^8\cdot 3^8),(1,1,2^8\cdot 3^8,1), (1,2^8\cdot 3^8,1,1), (2^8\cdot 3^8,1,1,1)$ are considered equivalent.

How many solutions $(a,b,c,d)$ are there?

• you have a total of 16 factors (2^8 and 3^8), so find however many ways you canof splitting that up into 4 factors Apr 9, 2017 at 21:34
• Unfortunately you are wrong. This is more than well known the distribution problem. Because some quadruples can be identical. Apr 9, 2017 at 21:58
• Couldn't you just solve $abcd = 2^8$ and $abcd = 3^8$ separately and then take the pairwise component-wise products of their quadruples? For example: $(1,1,1,2^8) \times (1, 1, 1, 3^8) = (1,1,1,2^83^8)$ Apr 9, 2017 at 22:01
• Unfortunately, we can't. Apr 9, 2017 at 22:02
• I think you are looking for multiplicative partitions. Also called unordered factorization by MathWorld.
– Jens
Apr 9, 2017 at 22:24

Up to ordering, there are $15$ distinct ways to partition $8$ into the sum of $4$ digits using only the numbers $\{0,\ldots,8\}$. Using a simple $4$-digit sequence to denote these partitions we have: $$\begin{array}{ccccc} 0008 & 0017 & 0026 & 0035 & 0044\\ 0116 & 0125 & 0134 & 0224 & 0233\\ 1115 & 1124 & 1133 & 1223 & 2222 \end{array}$$ So if I choose a partition of the powers of $2$ and a partition of the powers of $3$, we would like to know how many distinct ways can I combine them in our desired product. Let's illustrate this with the choices of $0116$ for the $2$'s and $0026$ for the $3$'s. To count this, we fix the order of the $2$'s and permute the order of $3$'s in each of the possible $12$ distinct ways: \begin{align*} 0116 \cdot 0026&=(00)(10)(12)(66)=2^03^0\cdot2^13^0\cdot2^13^2\cdot2^63^6\\ 0116 \cdot 0206 &= (00)(12)(10)(66) ~~(duplicate)\\ 0116 \cdot 2006 &= (02)(10)(10)(66) \\ 0116 \cdot 0062 &= (00)(10)(16)(62) \\ 0116 \cdot 0260 &= (00)(12)(16)(60) \\ 0116 \cdot 2060 &= (02)(10)(16)(60) \\ 0116 \cdot 0602 &= (00)(16)(10)(62) ~~(duplicate)\\ 0116 \cdot 0620 &= (00)(16)(12)(60) ~~(duplicate)\\ 0116 \cdot 2600 &= (02)(16)(10)(60) ~~(duplicate)\\ 0116 \cdot 6002 &= (06)(10)(10)(62) \\ 0116 \cdot 6020 &= (06)(10)(12)(60) \\ 0116 \cdot 6200 &= (06)(12)(10)(60) ~~(duplicate) \end{align*} and we see that there are $7$ distinct permutations of the powers of $3$ that yield distinct products equal to $2^8\cdot 3^8$.

Calculating this for each of the $225$ possible combinations of powers of $2$ and $3$, this brute force method gives $1297$ distinct products. This approach isn't as daunting as it seems at first. Combinatorially speaking, there are only $5$ distinct types of products based on the different fixed patterns of the powers of $2$: $$xxxx\cdot\text{ all permutations (1 of these) which produces 15 products each}\\ xxxy\cdot\text{ all permutations (2 of these) which produces 41 products each}\\ xxyy\cdot\text{ all permutations (2 of these) which produces 55 products each}\\ xyyz\cdot\text{ all permutations (8 of these) which produces 95 products each}\\ wxyz\cdot\text{ all permutations (2 of these) which produces 165 products each.}$$ Thus we have $$1\cdot 15+2\cdot 41+2\cdot 55+8\cdot 95+2\cdot 165=1297$$ distinct products.

• Laars Helenius,Thanks for your efforts. Can you explain your solution with more delatils. I didn't understand some points. Let's take $2222$ for $2$'s power and $1223$ for $3$'s power. There are $12$ permutations of $1223$. So we have to yields $12$ non-identical solution. Some of them: $2222$ and $1223$ gives $2^23^1\cdot 2^23^2\cdot 2^23^2\cdot 2^23^3$ and $2222$ and $2123$ gives $2^23^2\cdot 2^23^1\cdot 2^23^2\cdot 2^23^3$ and this: $2222$ and $2213$ gives $2^23^2\cdot 2^23^2\cdot 2^23^1\cdot 2^23^3$. Aren't they same identical solutions? Apr 10, 2017 at 19:26
• You are correct. Any combination of powers of 3 multiplied with 2222 will yield only one distinct product. I will elaborate my answer above to clarify. Apr 10, 2017 at 23:44
• @scarface Thanks for asking for more detail. I found a mistake in my calculations and now my answer matches yours! Apr 11, 2017 at 0:07

If $a_i=2^{x_i}\cdot 3^{y_i}$ then the $x_i$ as well as the $y_i$ form a partition of $8$ into four parts $\geq0$. There are $15$ such partitions. We can sort these $15$ partitions into five types according to the multiplicities of the occurring sizes as follows: \eqalign{1{\rm\ of\ type\ 1}:\quad &2222\cr 2{\rm\ of\ type\ 2}:\quad &8000, 5111\cr 2{\rm\ of\ type\ 3}:\quad &4400, 3311\cr 8{\rm\ of\ type\ 4}:\quad &7100, 6200, 5300, 6011, 4211, 4022, 3122, 2033\cr 2{\rm\ of\ type\ 5}:\quad &5210, 4310\cr}\tag{1} We now have to determine for each choice of two types $j$ and $k$ the number $q_{jk}$ of different quadruples $(a_1,a_2,a_3,a_4)$ that can be formed by a partition of type $j$ used with base $2$ and a partition of type $k$ used with base $3$. This has to be done "by hand". The symmetric matrix $Q=\bigl[q_{jk}\bigr]$ defined in this way looks as follows: $$Q=\left[\matrix{ 1&1&1&1&1 \cr 1&2&2&3&4 \cr 1&2&3&4&6 \cr 1&3&4&7&12 \cr 1&4&6&12&24 \cr}\right]\ .$$ Let $s=[1\ 2\ 2\ 8\ 2]$ be the vector listing the cardinalities of the five types in $(1)$. Then the total number $N$ of quadruples of the described kind is given by $$N=s\>Q\>s'=1297\ .$$

• Using a matrix to organize the work is nice! Aug 6, 2017 at 3:29

The fundamental theorem of arithmetic tells us that each $a,b,c,d$ is of the form $2^n \cdot 3^m$. Consequently, $$abcd = 2^{n_a + n_b + n_c + n_d} \cdot 3^{m_a + m_b + m_c + m_d} = 2^8 \cdot 3^8.$$ The problem is reduced to finding non-negative integers $n_i$ and $m_i$ such that the sum of the $n_i = 8$, and the sum of the $m_i = 8$.

To eliminate permutations of $a,b,c,d$, let us say without loss of generality that $n_a \geq n_b \geq n_c \geq n_d$ and that in the case $n_i = n_{i+1}$, we require that $m_i \geq m_{i+1}$. i.e. we join the digits $n$ and $m$ and order the numbers $n_i m_i$ from highest to lowest; highest assigned to $a$ and lowest assigned to $d$. With these constraints, we need only count the number of choices for $n_i,m_i$.

First, take a look at this answer for an understanding of how we partition an integer $n$ into $k$ non-negative integers up to permutation of the parts. (Although I believe the recurrence relations here are written incorrectly! I've used another source for my formula.) These are called partitions. I'll denote this $p_0(k,n)$ to distinguish it from the usual notion of a partition consisting of only positive integers.

Note that a composition of an integer is the same as a partition, except that permutations are not considered equivalent.

On a case-by-case basis, I'll go through the possibilities for $(n_a,n_b,n_c,n_d)$ and reason about the corresponding choices for $m_i$. There are essentially only five cases.

\begin{aligned} && \text{Choices for }n_i && \text{#Choices for }m_i\\ n_a < 2 : && \textrm{no solution} && \textrm{no solution}\\ n_a = 2 : && (2,2,2,2) && p_0(4,8) && \text{The problem reduces to partitioning } 8\\ n_a = 3 : && (3,3,2,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j) && \text{Choose } j=(m_a+m_b)\text{, and then }(m_c,m_d)\\ &&(3,3,1,1) && \sum_{j=0}^8 p_0(2,j) \cdot p_0(2,8-j) && \text{Choose } j= (m_a+m_b)\\ &&(3,2,2,1) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 4 : && (4,4,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot p_0(2,8-j)\\ &&(4,3,1,0) && \frac{(8+4-1)!}{(4-1)!8!} && \text{Choose any composition of }8\\ &&(4,2,2,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ &&(4,2,1,1) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 5 : && (5,3,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ &&(5,2,1,0) && \frac{(8+4-1)!}{(4-1)!8!}\\ &&(5,1,1,1) && \sum_{j=0}^8 p_0(3,j) && \text{Choose } j=(m_b+m_c+m_d)\\ n_a = 6 : && (6,2,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ &&(6,1,1,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 7 : && (7,1,0,0) && \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)\\ n_a = 8 : && (8,0,0,0) && \sum_{j=0}^8 p_0(3,j) \end{aligned}

Adding these together, there are $1297$ choices for $a,b,c,d$ up to permutation.

Let me explain where each of these terms comes from.

$$(2,2,2,2): \quad p_0(4,8)$$

In this case, the $n_i$ are equal and so by the rules I set out at the top, we must order the $m_i$ fro highest to lowest. Consequently, we are looking for the number of unordered sums of four integers $m_i$ which make $8$. This is equal to $p_0(4,8)$.

$$(3,3,2,0): \quad \sum_{j=0}^8 p_0(2,j) \cdot (1+8-j)$$

First, we may choose the sum $(m_a+m_b)$. Since $n_a = n_b$, we have no say in how these first two $m_i$ are ordered. We must order them from highest to lowest. So we have $p_0(j,2)$ choices given that we want them to sum to $j$. After having chosen one of these, we may choose $m_c$ and $m_d$ however we please so that they sum to $8-j$. There are $1+8-j$ ways to do this.

$$(4,4,0,0): \quad \sum_{j=0}^8 p_0(2,j) \cdot p_0(2,8-j)$$

In this case, we have two pairs of $n_i$ which are equal. This means we have no say over how the corresponding pairs of $m_i$ are ordered, though we may still choose the unordered sums. First, choose what $m_a+m_b$ will sum to by picking a $j$. Then we pick which unordered sum we want to yield $m_a+m_b = j$, giving us $p_0(2,j)$ choices. After that, we still have $8-j$ left to distribute to $m_c+m_d$, again with no say over their ordering. So we have $p_0(2,8-j)$ choices for a particular $j$.

$$(4,3,1,0): \quad \frac{(8+4-1)!}{(4-1)!8!}$$

Here, each $n_i$ is distinct and so there is no ordering imposed on the $m_i$. We may choose any combination, in any order, which yields a sum of $8$.

$$(5,1,1,1): \quad \sum_{j=0}^8 p_0(3,j)$$

Because three of the $n_i$ are identical, we have no say in the ordering of their corresponding $m_i$; only the sum of $m_b+m_c+m_d$. For a given sum $j$, we have $p_0(3,j)$ such choices. A choice of $j$ obviously fixes $m_a$ too.

I'd be interested to see if there's a general formula for partitioning tuples, as this problem is equivalent to partitioning $(8,8)$ into an unordered sum of $2$-tuples.

• Thanks for your efforts @Myridium. I find $1452$ with using a different method. Probably, I made a mistake in my calculations. I will check it. Apr 10, 2017 at 0:51
• @scarface - I may be wrong! I've been trying to confirm it using a method in Mathematica, but the algorithm is too slow for me to compute. Apr 10, 2017 at 1:00
• @scarface - for $2^n 3^n$ where $n \in \{1,2,3,4,5\}$, my Mathematica algorithm says $2,9,27,74,168$. Is this what your working produces? Apr 10, 2017 at 1:05
• Firstly solve $n_a+n_b+n_c+n_d=8$ and $m_a+m_b+m_c+m_d=8$. There are $\dbinom{11}{3}^2=165^2=27225$ solutions. But in these $27225$, some solutions repeated. $aaab, aabb, aabc, aaaa$ repeated $4,6,12,1$ times respectively. Some calculating I find that $$\dfrac{165^2-4\cdot 8 - 6\cdot 24 -12\cdot 584 -1}{4!} + 8 + 24 + 584 + 1 = 1452$$ Apr 10, 2017 at 1:29
• @scarface - It turns out that my method was correct; I just made a silly error. I've fixed it now. $(8-j)$ should have been $(9-j)$ in one of the terms (we can choose any integer from $0$ to $8$ and I was counting this as being $8$ choices). My new answer matches yours: $1297$. Apr 11, 2017 at 9:45

Number of non-identical solutions is $1297$. Let's solve it!

$abcd = 2^{n_a + n_b + n_c + n_d} \cdot 3^{m_a + m_b + m_c + m_d} = 2^8 \cdot 3^8$. We need number of solutions in the form $a\ge b \ge c \ge d$. In this case there is no identical solution. By the distribution principle, number of solutions of the system $n_a + n_b + n_c + n_d=8$, $m_a + m_b + m_c + m_d=8$ is $\dbinom{11}{3}^2=27225$. But this is so big for us. Because it has some identical solutions.

1. Case: Solutions in the form $(a,a,a,b)$ and $a \ne b$. \begin{array}{lcr} 3n_a + n_b & = & 8 \\ 3m_a +m_b & = & 8 \end{array} Solutions $(n_a,n_b)=(0,8),(1,5),(2,2)$ and $(m_a,m_b)=(0,8),(1,5),(2,2)$. There are $3\cdot 3 =9$ solutions. But for $(n_a,n_b)=(m_a,m_b)=(2,2)$, we find $a=b$. So, number of the solutions $9-1=\boxed 8$.

Remember 1: This case includes $a=b=c>d$ and $a>b=c=d$ non-identical sub cases.

2. Case: Solutions in the form $(a,a,b,b)$ and $a \ne b$. \begin{array}{lcr} 2n_a + 2_b & = & 8 \\ 2m_a +2_b & = & 8 \end{array}

Solutions $(n_a,n_b)=(0,4),(1,3),(2,2),(3,1),(4,0)$ and $(m_a,m_b)=(0,4),(1,3),(2,2),(3,1),(4,0)$. There are $5\cdot 5 =25$ solutions. But for $(n_a,n_b)=(m_a,m_b)=(2,2)$, we find $a=b$. So, number of the solutions $25-1=24$.

Remember 2: This case includes $a=b>c=d$ and $a=b<c=d$ identical sub cases. So non-identicals are $\dfrac{24}{2}=\boxed{12}$.

3. Case: Solutions in the form $(a,a,b,c)$ and $a \ne b \ne c \ne a$.

\begin{array}{lcr} 2n_a + n_b +n_c & = & 8 \\ 2m_a +m_b +m_c & = & 8 \end{array}

Solutions $(n_a,n_b,n_c)=(0,8,0),\dots ,(4,0,0)$ and $(m_a,m_b,m_c)=(0,8,0),\dots ,(4,0,0)$ . There are $25\cdot 25 =625$ solutions. But;

for $(n_a,n_b),(m_a,m_b)\in \{(0,0),(1,1),(2,2)\}$, we find $a=b$. There are $3\cdot3=9$ solutions. For $(n_a,n_c),(m_a,m_c)\in \{(0,0),(1,1),(2,2)\}$, we find $a=c$. There are $3\cdot3=9$ solutions. For $(n_b,n_c),(m_b,m_c)\in \{(0,0),(1,1),(2,2),(3,3),(4,4)\}$, we find $b=c$. There are $5\cdot5=25$ solutions. Also $(n_a=n_b,n_c)=(m_a=m_b,m_c)=(2,2,2)$ count $3$times. Therefore $625-9-9-25+2=584$

Remember 3: This case includes $a=b>c>d$ and $a=b>d>c$ identical sub cases. So non-identicals are $\dfrac{584}{2}=\boxed{292}$.

The Last Case: Solutions in the form $(a,a,a,a)$. Clearly, there is only $1$ solution.

Now we can find number of solutions in the form $abcd$ that all of them different each other. Amount of these $\dfrac{27225-\binom{4}1\cdot 8 -\binom{4}2\cdot 12 -\frac{4!}{2!}\cdot 292 -1 }{4!}= 984$.

Total amount of non-identical solutions $984 + 8 +12 + 292 +1=1297$.