# 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.

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