Is the Number of Carries in Integer-Addition Associative?

Question

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions are carried out)? Carries are computed in base 2, so that 1+3 is $01_2+11_2=100_2$, which involves 2 carries: the least significant digits resulted in a carry, which then causes a second carry of the 2's digit.

In case the assumption is wrong, I would also like some ideas for determining the optimal permutation and order of additions.

Answer 1

In base $b$, let $G_n$ be the set of $n$-digit integers, thought of as the integers mod $b^n$. Then we have an exact sequence $$0\rightarrow G_1\rightarrow G_n\rightarrow G_{n-1}\rightarrow 0$$

For $n-1$ digit numbers, the leftmost carry digit is the two-cocycle associated to this group extension and therefore satisfies the cocycle condition $$c(x,y)+c(x+y,z)=c(y,z)+c(x,y+z)$$ In other words, the sum of the leftmost carry digits does not depend on the order of the summands.

After reducing mod $b^k$, the same argument holds for any other carry digit.

Answer 2

For any base $b$, if we add $a$ and $c$ with $k$ carries, then $S_b(a+c)=S_b(a)+S_b(c)-(b-1)k$, where $S_b$ denotes the sum of digits. Since the resulting sum is independent of the order of addition, the total number of carries is independent as well.

Answer 3

Alpoge's comment gives a beautiful answer for prime bases. Of course this answers the original question for binary addition.

I can't see how to extend it to composite bases. For instance in base $6$, the addition $2+7 = 9 = 13_6$ has one carry, but the highest power of $6$ dividing $\binom{9}{2} = 36$ is $2$.

Here is an alternative argument. Work in base $d$. If $x = x_r d^r + \cdots + x_jd^j + \cdots x_1 d + x_0$ then say $x_j$ is in position $j$. Suppose we are adding $a^{(1)}, \ldots, a^{(n)}$ and that there is a carry of $r$ into position $j$. Consider the sum $r + a^{(1)}_j + \cdots + a^{(n)}_j$, computed in $\mathbb{N}_0$. We get a carry every time a partial sum $r + a^{(1)} + \cdots + a^{(m)}_j$ is $< ds$ (for some $s$) and the next addition makes it $\ge ds$ (but necessarily $< (d+1)s$). Since addition in $\mathbb{N}_0$ is commutative and associative, the number of such 'crossings' does not depend on the order of the numbers. Neither does the carry going into position $j+1$. So by induction, the total number of carries is independent of the order of the numbers.