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)?

  • $\begingroup$ What is the source of this problem? $\endgroup$ – Carl Schildkraut Feb 28 at 19:24
  • $\begingroup$ @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. $\endgroup$ – Cardioid_Ass_22 Feb 28 at 19:39

This is not an answer, it's a long comment.

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$.

  • 2
    $\begingroup$ 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. $\endgroup$ – Hagen von Eitzen Mar 14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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