In this paper we study the number of carries occurring while performing an addition modulo 2k ? 1. For a fixed modular integer t, it is natural to expect the number of carries occurring when adding a random modular integer a to be roughly the Hamming weight of t. Here we are interested in the number of modular integers in Z/(2k ? 1)Z producing strictly more than this number of carries when added to a fixed modular integer t ∈ Z/(2k ? 1)Z. In particular it is conjectured that less than half of them do so. An equivalent conjecture was proposed by Tu and Deng in a different context. Although quite innocent, this conjecture has resisted different attempts of proof and only a few cases have been proved so far. The most manageable cases involve modular integers t whose bits equal to 0 are sparse. In this paper we continue to investigate the properties of Pt,k, the fraction of modular integers a to enumerate, for t in this class of integers. Doing so we prove that Pt,k has a polynomial expression and describe a closed form for this expression. This is of particular interest for computing the function giving Pt,k and studying it analytically. Finally, we bring to light additional properties of Pt,k in an asymptotic setting and give closed-form expressions for its asymptotic values.
展开▼
