# Unique partitions of two numbers

We say that $$A=\sum_{i=1}^a a_i$$ and $$B=\sum_{j=1}^b b_j$$ is a unique partition of $$A$$ and $$B$$ if there is no other way to partition the $$a+b$$ numbers into two parts that sum to $$A$$ and $$B$$. This is meant to also imply that $$a_i\ne b_j$$, but we allow $$a_i=a_{i'}$$. For example, $$6=3+3$$ and $$53=13\times 4+1$$ is a unique partition of $$6$$ and $$53$$, and so is $$6=3+3$$ and $$53=4\times 13+1$$. Let

$$mup(A,B)=\max \{a+b\mid$$ there is a unique partition $$A=\sum_{i=1}^a a_i$$ and $$B=\sum_{j=1}^b b_j\}$$

so the (bigger) above partition shows that $$mup(6,53)\ge 16$$. Has this been studied? Is there a simple formula for it? I know some bounds for special cases, but no general formula. Let me also mention the following "law:" $$mup(n+\nu(c),c)=mup(n,c)+1$$ for large enough $$n$$, where $$\nu(c)$$ is the smallest natural that does not divide $$c$$. The bounds

$$\frac n{\nu(c)}-O(1)\le mup(n,c)\le \frac n{\nu(c)}+O(c)$$

are easy to see to hold.

• Doesn't your example only show $mup(6,53) \ge 7$? – quarague Nov 8 at 14:33
• In your example for $53$, does $a=4$ or $13$? – Sylvain JULIEN Nov 8 at 15:07
• If $A=B$, there are no unique partitions. – Robert Israel Nov 8 at 15:14
• @SylvainJULIEN I read the example as saying $a=2$ ($2$ threes) and $b=14$ ($13$ fours and $1$ one) making $a+b=16$ – Henry Nov 8 at 17:15
• @Sylvain Both give a unique partition. – domotorp Nov 8 at 17:27

## 2 Answers

If my programming is correct, here are $$mup(i,j)$$ for each $$i$$ and $$j$$ from $$1$$ to $$15$$. $$mup(i,i)$$ is given as $$0$$, since there are no unique partitions in this case.

$$\matrix{& j=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \cr i= 1 & 0 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 & 7 & 8 & 8 \cr i= 2 & 2 & 0 & 3 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 6 & 6 & 6 & 7 \cr i= 3 & 2 & 3 & 0 & 4 & 4 & 4 & 4 & 5 & 5 & 6 & 5 & 7 & 6 & 8 & 7 \cr i= 4 & 3 & 3 & 4 & 0 & 5 & 5 & 5 & 5 & 5 & 6 & 6 & 6 & 6 & 6 & 7 \cr i= 5 & 3 & 3 & 4 & 5 & 0 & 6 & 6 & 6 & 6 & 6 & 6 & 7 & 7 & 8 & 7 \cr i= 6 & 4 & 4 & 4 & 5 & 6 & 0 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 8 & 8 \cr i= 7 & 4 & 4 & 4 & 5 & 6 & 7 & 0 & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8 \cr i= 8 & 5 & 4 & 5 & 5 & 6 & 7 & 8 & 0 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \cr i= 9 & 5 & 5 & 5 & 5 & 6 & 7 & 8 & 9 & 0 & 10 & 10 & 10 & 10 & 10 & 10 \cr i= 10 & 6 & 5 & 6 & 6 & 6 & 7 & 8 & 9 & 10 & 0 & 11 & 11 & 11 & 11 & 11 \cr i= 11 & 6 & 5 & 5 & 6 & 6 & 7 & 8 & 9 & 10 & 11 & 0 & 12 & 12 & 12 & 12 \cr i= 12 & 7 & 6 & 7 & 6 & 7 & 7 & 8 & 9 & 10 & 11 & 12 & 0 & 13 & 13 & 13 \cr i= 13 & 7 & 6 & 6 & 6 & 7 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 0 & 14 & 14 \cr i= 14 & 8 & 6 & 8 & 6 & 8 & 8 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 0 & 15 \cr i= 15 & 8 & 7 & 7 & 7 & 7 & 8 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 0 \cr }$$

It does not seem to be in the OEIS.

EDIT: Here are $$mup(i,j)$$ for $$1 \le i \le 40$$ and $$1 \le j \le 6$$.

$$\left[ \begin {array}{ccccccc} i=1&0&2&2&3&3&4\\ i=2&2&0&3&3&3&4\\ i=3&2&3&0&4&4&4\\ i=4&3&3&4&0&5&5\\ i=5&3&3&4&5&0&6\\ i=6&4&4&4&5&6&0\\ i=7&4&4&4&5&6&7\\ i=8&5&4&5&5&6&7\\ i=9&5&5&5&5&6&7\\ i=10&6&5&6&6&6&7\\ i=11&6&5&5&6&6&7\\ i=12&7&6&7&6&7&7\\ i=13&7&6&6&6&7&7\\ i=14&8&6&8&6&8&8\\ i=15&8&7&7&7&7&8\\ i=16&9&7&9&7&9&8\\ i=17&9&7&8&7&7&8\\ i=18&10&8&10&8&10&8\\ i=19&10&8&9&7&8&8\\ i=20&11&8&11&8&11&8\\ i=21&11&9&10&9&9&9\\ i=22&12&9&12&8&12&9\\ i=23&12&9&11&9&10&9\\ i=24&13&10&13&10&13&9\\ i=25&13&10&12&9&11&9\\ i=26&14&10&14&10&14&9\\ i=27&14&11&13&11&12&9\\ i=28&15&11&15&10&15&10\\ i=29&15&11&14&11&13&10\\ i=30&16&12&16&12&16&10\\ i=31&16&12&15&11&14&10\\ i=32&17&12&17&12&17&10\\ i=33&17&13&16&13&15&11\\ i=34&18&13&18&12&18&10\\ i=35&18&13&17&13&16&11\\ i=36&19&14&19&14&19&11\\ i=37&19&14&18&13&17&12\\ i=38&20&14&20&14&20&11\\ i=39&20&15&19&15&18&12\\ i=40&21&15&21&14&21&12\end {array} \right]$$

• Nice! Would the code slow down for larger values or just this filled out enough place? – domotorp Nov 8 at 17:31
• Some larger $i$ and $j$ could be done, but it would soon slow down rather rapidly, as this involves a brute-force search over pairs of partitions. – Robert Israel Nov 8 at 17:34
• Can you maybe do $mup(n,c)$ for some small $c$? – domotorp Nov 8 at 17:37
• I think what @domotorp is asking for is, e.g., $mup(n, c)$ for $1\leq c\leq 5$ or somesuch, but for $n\leq 100$ or similar... – Steven Stadnicki Nov 8 at 17:41
• OK, done for $1 \le j \le 6$ as requested. – Robert Israel Nov 8 at 19:37

There are some considerations which show that the answer is in the neighborhood of $$n/v + v$$, where I write $$v=\nu(c)$$, the smallest positive nondivisor of $$c$$.

There is a standard result that any increasing sequence starting from 0 and including $$v$$ many positive integers must have two of the sequence members differ by a multiple of $$v$$. So if we have two partitions witness the maximal number of parts, then either the partition of $$c$$ has less than $$v$$ parts or else $$n$$ has not many parts of size $$v$$.

However, we can take for a partition of $$n$$ one part of size larger than $$c$$, and the rest of size $$v$$, and then choose the smallest divisor of $$c$$ larger than $$n/v$$, and this will give close to $$n/v$$ distinct parts. By choosing the partition of $$c$$ carefully, we can bump this slightly to repartition $$n$$ and add a few more $$v$$ parts. In any case, the maximum value has to be less than $$1+ n/v + v$$ for $$n$$ not much larger than $$2c$$.

Gerhard "Parts Is Parts Are Parts" Paseman, 2019.11.08.

• In the second para, why are two numbers that differ by $v$ useful? Wouldn't you rather need some numbers whose sum is divisible by $v$? This is known as the Davenport constant, and it is at most $v$. But I don't see how your argument gives a complete proof of your claimed upper bound. – domotorp Nov 9 at 5:36
• In optimizing the number of parts, one wants as many values of v as possible to form a partition of n. If n is much bigger than 2*c, it is likely that there are more than c/v many v's in a partition of n. This is a problem if c is divided into v or more parts, for then we no longer get uniqueness: we have enough v's to replace some of the partition of c. Gerhard "V Is Not For Victory" Paseman, 2019.11.08. – Gerhard Paseman Nov 9 at 6:34
• I also think so, but this is not a rigorous proof yet. – domotorp Nov 9 at 8:38