# The sum of the carries when adding and multiplying two numbers in base p

Let $\sigma_p(m,n)$ (resp. $\pi_p(m,n)$) denote the sum of the carries when adding (resp. multiplying) the numbers $m=\sum_{k\ge0}m_kp^k$ and $n=\sum_{k\ge0}n_kp^k$ using base-$p$ arithmetic where $m_k,n_k\in\{0,\dots,p-1\}$ for $k\ge0$. Let $s_p(m)=\sum_{k\ge0}m_k$ be the sum of the base-$p$ digits.

Question 1. Does someone know a reference for the following (cohomological) formulas? $$\sigma_p(m,n)=\frac{s_p(m)+s_p(n)-s_p(m+n)}{p-1},\quad \pi_p(m,n)=\frac{s_p(m)s_p(n)-s_p(mn)}{p-1}.$$

Question 2. Does someone know what $\pi_p(m,n)$ counts (besides the number of carries)?

I will happily type my (short) proofs if there is interest, and there is no obvious reference. A famous result of Kummer says that $\sigma_p(m,n)$ is the exponent of the largest power of $p$ dividing $\binom{m+n}{n}$. (The formula for $\pi_p(m,n)$ arose from a problem in finite geometry.)

Edit: Typo corrected ($\alpha$ changed to $\sigma$). Thanks R. Also, replaced `number of carries' with 'sum of carries' as $c_k>1$ happens, see proof below.

-
Where did $\alpha$ come from? – R.. Sep 4 '14 at 4:20

In their article "Stolarsky's conjecture and the sum of digits of polynomial values"( https://www.math.uwaterloo.ca/~kghare/Preprints/PDF/P34_Stolarsky.pdf ), Hare, Laishram and Stoll show in Proposition 2.2 that the sum of digits is subadditive and submultiplicative. Although the proposition does not contain the formulae you gave, the proof proceeds by giving your formulae, and then concluding with the remark that the number of carries is non-negative.

Can you explain what these equation have to do with cohomology?

-
Thanks Jan-Christoph. Prop 2.2 of the preprint states the formula for $\sigma_p(m,n)$, but not the formula for $\pi_p(m,n)$. (If it did then the proof of $s_p(mn)\le s_p(m)s_p(n)$ would be even shorter.) – Glasby Sep 5 '14 at 1:01
It implicitly does. The displayed formula in their proof has two $\leq$-signs, each of which comes from sub-additivity. If you insert the more precise formula for $\sigma_p(m, n)$ at these places, you get the formula for $\pi_p(m,n)$. – Jan-Christoph Schlage-Puchta Sep 6 '14 at 9:34

I was asked (offline) for a proof of the formula for the sum of the carries $\pi_p(a,b)$ when multiplying $a$ and $b$ in base $p$.

Proof. Multiplying the base-$p$ expansions $a=\sum_{k\ge0}a_kp^k$ and $b=\sum_{k\ge0}b_kp^k$ generates carries $c_0,c_1,\dots$ where $c_k$ is the carry generated by adding multiples of $p^k$. The base-$p$ expansion of the product $ab=\sum_{k\ge0}(ab)_kp^k$ is related to the $a_i$, $b_j$ and $c_k$ via the equations: \begin{align*} (ab)_0&=a_0b_0-pc_0\\ (ab)_1&=a_0b_1+a_1b_0+c_0-pc_1\\ (ab)_2&=a_0b_2+a_1b_1+a_2b_0+c_1-pc_2\\ &\ \vdots \end{align*} where $(ab)_k=\left(\sum_{i+j=k}a_ib_j\right)+c_{k-1}-pc_k$ for $k\ge1$. Adding these equations gives $$s_p(ab)=\left(\sum_{i\ge0}a_i\right)\left(\sum_{j\ge0}b_j\right) -(p-1)\sum_{k\ge0}c_k=s_p(a)s_p(b)-(p-1)\pi_p(a,b).$$ Rearranging gives the desired formula for $\pi_p(a,b)$. The formula for $\sigma_p(a,b)$ is obtained similarly by adding $(a+b)_0=a_0+b_0-pc_0$ and $(a+b)_k=a_k+b_k+c_{k-1}-pc_k$ for $k\ge1.\ \ \square$

-