5
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Nice! Would the code slow down for larger values or just this filled out enough place? $\endgroup$ – domotorp Nov 8 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Nov 8 at 17:34
  • $\begingroup$ Can you maybe do $mup(n,c)$ for some small $c$? $\endgroup$ – domotorp Nov 8 at 17:37
  • 1
    $\begingroup$ 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... $\endgroup$ – Steven Stadnicki Nov 8 at 17:41
  • 1
    $\begingroup$ OK, done for $1 \le j \le 6$ as requested. $\endgroup$ – Robert Israel Nov 8 at 19:37
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – domotorp Nov 9 at 5:36
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 9 at 6:34
  • $\begingroup$ I also think so, but this is not a rigorous proof yet. $\endgroup$ – domotorp Nov 9 at 8:38

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.