Minimizing the number of carries in addition

DOI10.1137/120890612zbMATH Open1321.11010arXiv1209.1131OpenAlexW1991045742MaRDI QIDQ5300511FDOQ5300511

Authors: Noga Alon 

Publication date: 27 June 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: When numbers are added in base $b$ in the usual way, carries occur. If two random, independent 1-digit numbers are added, then the probability of a carry is $fracb-12b$. Other choices of digits lead to less carries. In particular, if for odd $b$ we use the digits $-(b-1)/2,-(b-3)/2,\mathrm{...},\mathrm{...}(b-1)/2$ then the probability of carry is only $frac{b}^2-14b^2$. Diaconis, Shao and Soundararajan conjectured that this is the best choice of digits, and proved that this is asymptotically the case when $b=p$ is a large prime. In this note we prove this conjecture for all odd primes $p$.

Full work available at URL: https://arxiv.org/abs/1209.1131

Recommendations

• Carries and the arithmetic progression structure of sets
• On the number of carries occurring in an addition mod \(2^k -1\)
• scientific article; zbMATH DE number 1055635
• A generalization of the carries process
• Analysis of Carry Propagation in Addition: An Elementary Approach

zbMATH Keywords

carrymodular addition

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Arithmetic combinatorics; higher degree uniformity (11B30) Number-theoretic algorithms; complexity (11Y16)

Cited In (6)

• Carries and the arithmetic progression structure of sets
• Combinatorics of balanced carries
• On the number of carries occurring in an addition mod \(2^k -1\)
• Inserting plus signs and adding
• Carries, group theory, and additive combinatorics
• Carryless arithmetic\(\mod 10\)

This page was built for publication: Minimizing the number of carries in addition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300511)