How to divide natural number N into M nearly equal summands?

Question

How to divide natural number N into M nearly equal summands?

For example, to divide 20 by 13, in geometric representation, I should get

How to generate the sequence above?

What is the name of this operation? It is close to division, but exact and giving unequal summands as a result.

P.S. Also this is probably related with leap years / calendar calculations.

UPDATE

Regarding examples where we get

$20=2+2+2+2+2+2+2+2+1+1+1+1$

I think it is not ballanced in the middle:

I would like partial sums be close to ratio as much as possible.

Answer 1

Consider the sequence $$\left\lfloor\frac{N k}{M}\right\rfloor, \qquad k = 0,\ldots, M.$$ which for $N = 20, M = 13$, gives $$0, 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 20.$$ The differences between successive terms are $$\left\lfloor\frac{N (k + 1)}{M}\right\rfloor - \left\lfloor\frac{N k}{M}\right\rfloor, \qquad k = 0,\ldots, M - 1.$$ In our example, $$1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2,$$ and the reverse of this is $$\phantom{(\ast)\qquad} 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, \qquad(\ast)$$ which is nearly the sequence given.

I claim that $(\ast)$ is actually the sequence you want, rather than the given one. Notice, for example, that if we take the origin to be the bottom-leftmost corner, the line passes through $\left(3, \frac{39}{20}\right)$, which is below the marked point $(3, 2)$; so, in the diagram, the red step curve actually crosses the black diagonal, which I presume is undesired.

Reversing the order in the sequence of differences exchanges the $k$th term with the $(M - k - 1)st$ (for every $k$), so the general formula for the desired sequence is $$\color{#df0000}{\left\lfloor\frac{N (M - k)}{M}\right\rfloor - \left\lfloor\frac{N (M - k - 1)}{M}\right\rfloor, \qquad k = 0,\ldots, M - 1}.$$

Remark One can alternately produce more "balanced" partitions by rounding each multiple $\frac{Nk}{M}$ to the nearest integer (rather than flooring): $$\left\lfloor\frac{N k}{M} + \frac{1}{2}\right\rfloor, \qquad n=0,\ldots, M$$ (this convention rounds $\frac{1}{2}$ up). The resulting sequence of differences is $$\left\lfloor\frac{N (M - k)}{M} + \frac{1}{2}\right\rfloor - \left\lfloor\frac{N (M - k - 1)}{M} + \frac{1}{2}\right\rfloor, \qquad n=0,\ldots, M - 1,$$ which for our example is the aesthetically pleasing $$2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2.$$

Answer 2

We note that in general we can express some number $n$ as the sum of $m$ "almost equal" parts, such that:

$$n=\left\lceil\frac{n}{m} \right\rceil+\cdots+\left\lceil \frac{n-m+1}{m} \right\rceil = \sum_{k=0}^{m-1}\left\lceil\frac{n-k}{m}\right\rceil$$

So for each bin $k \in \{1,m\}$ we have the number of items in it:

$$N_{k}=\left\lceil\frac{n-k+1}{m}\right\rceil$$

So for your example where $n=20$, $m=13$ we have the number in each bin:

$$\{2,2,2,2,2,2,2,1,1,1,1,1,1\}$$

Which corresponds to your example. I hope this helps!

Answer 3

Use the division algorithm to write $N$ as $aM+r$ with $0\leq r<M$

Then $N$ can be seen as $r$ times the number $a+1$ and $M-r$ times the number $a$.

---

Example: you want to divide $20$ by $13$. We get $20=1\cdot13+7$, here $a=1$ and $r=7$

Then we use the above and get $20$ is the same as $7$ times $1+1=2$ plus $13-7=6$ times $1$.

So we get $20=2+2+2+2+2+2+2+1+1+1+1+1+1$