# Partitions of $2n$ and factorizations of $n$

Let $$n$$ be any positive integer.

Let $$p_1,p_2,...,p_m$$ be any positive integers such that no more than one of the $$p_i$$s is $$1$$ and $$\prod_{i=1}^mp_i=n$$.

Finally, let $$s_1,s_2,...,s_m$$ be any nonnegative integers such that $$\sum_{i=1}^ms_i=2n$$.

Do there always exist integers $$k_1,k_2,...,k_m$$ such that: $$\sum_{i=1}^m(k_ip_i)=n$$

And, for each $$i$$: $$k_ip_i\leq s_i$$

?
Initially, I tried induction on $$m$$ (the number of factors, $$p_i$$). I assumed the hypothesis held for all cases when $$m$$ was less than $$t$$ for a fixed $$n$$ and tried proving it for the case of $$m=t$$ (for the same $$n$$) but got nowhere.

I also tried induction on the number of (not necessarily distinct) prime factors of $$n$$ but, again, only got past the base case.
(I couldn't really get past viewing this through an induction lens)

It seems as if it should be true given that the $$s_i$$'s need to sum to $$2n$$ whereas the $$k_ip_i$$'s need to sum to only $$n$$ (and the size of the $$p_i$$ terms are limited by the constraint that their product equal $$n$$) but I can't find a way to prove it (or a counterexample).

Are there any hints anyone can provide for a proof (or for generating a good counterexample)?

• What is the source of this problem? – Carl Schildkraut Feb 28 at 19:24
• @CarlSchildkraut Uh it kind of popped up out of a few different things. It's related to something I thought up while studying partitions under the framework of generating functions but I returned to this more specific version recently because it turned out to be related to a special case of a particular problem to do with groups. Always been a bit skeptical of (versions of) this problem, though. – Cardioid_Ass_22 Feb 28 at 19:39

Consider the number N=p∗q=7∗13=91. If you look at 91, it's the point in the multiplication table where the line $$L_1$$ of numbers with the same (p−q) meets the line $$L_2$$ with the same (p+q). $$L_1$$ starts at 7 and $$L_2$$ starts at 19 since p−q=13−7=7−1=6 and p+q=17+13=20=1+19. So you can write for N=91=7+9+11+13+15+17+19 but also N=19+17+15+13+11+9+7 depending on where you start. If you add both sums term by term you get $2N=182=(7+19)+(9+17)+(11+15)+(13+13)+(15+11)+(17+9)+(19+7)=7*(26)=7*2*13=2*(7*13). This can be done for any composite number. The problem is we don't know (p−q) or (p+q) so we can't do that. So basically we can't use it since we don't even have a good approximation to (p−q) or (p+q). For you summation $$sum(k_ip_i)$$, I think it cannot be done in general. you can write $$N=91=13+13+13+13+13+13+13=13(1+1+1+1+1+1+1)=13*7$$. Once a number $$N$$ is given, the factors are fixed, one p and one q for the case $$N=pq$$, so I am not sure you can sum up over $$p_{i}$$. However, because $$91$$ is a triangular number you can write it as a sum from $$1$$ to $$13$$ but in this case you don't need two variables $$k_i$$ and $$p_i$$. • With$m=2$, it is always possible: From$s_1+s_2=2n$, one of the$s_i$must be$\ge n$. Then we can let$k_i=n/p_i$for that$i$and$k_j=0\$ for the other index. – Hagen von Eitzen Mar 14 at 13:03