The carry propagation of the successor function

DOI10.1016/J.AAM.2020.102062zbMATH Open1484.11012arXiv1907.01464OpenAlexW3031071223MaRDI QIDQ2197902FDOQ2197902

Authors: Christiane Frougny, Michel Rigo, Jacques Sakarovitch, Valérie Berthé 

Publication date: 1 September 2020

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Given any numeration system, we call carry propagation at a number $N$ the number of digits that are changed when going from the representation of $N$ to the one of $N+1$, and amortized carry propagation the limit of the mean of the carry propagations at the first $N$ integers, when $N$ tends to infinity, if this limit exists. In the case of the usual base $p$ numeration system, it can be shown that the limit indeed exists and is equal to $p/(p-1)$. We recover a similar value for those numeration systems we consider and for which the limit exists. We address the problem of the existence of the amortized carry propagation in non-standard numeration systems of various kinds: abstract numeration systems, rational base numeration systems, greedy numeration systems and beta-numeration. We tackle the problem by three different types of techniques: combinatorial, algebraic, and ergodic. For each kind of numeration systems that we consider, the relevant method allows for establishing sufficient conditions for the existence of the carry propagation and examples show that these conditions are close to being necessary conditions.

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

Recommendations

• Carry propagation in signed digit representations
• scientific article; zbMATH DE number 1055635
• Analysis of Carry Propagation in Addition: An Elementary Approach
• Carries and the arithmetic progression structure of sets
• Analysis of carries in signed digit expansions

zbMATH Keywords

generating functiondynamical systemnumeration systemsuccessor functioncarry propagationgreedy numeration systemlanguage signaturepositive rational seriesrational base numeration system

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Symbolic dynamics (37B10) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15) Relations between ergodic theory and harmonic analysis (37A46)

Cites Work

• Representations for real numbers and their ergodic properties
• On theβ-expansions of real numbers
• Elements of automata theory. Translated from the French by Reuben Thomas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Formal Languages, Automata and Numeration Systems 1
• Noncommutative rational series with applications
• Substitutions in dynamics, arithmetics and combinatorics
• Systems of Numeration
• Odometers and systems of numeration
• Title not available (Why is that?)
• Powers of rationals modulo 1 and rational base number systems
• Combinatorial Complexity of Regular Languages
• Numeration systems, linear recurrences, and regular sets
• On the sequentiality of the successor function
• Dynamiques associees a une echelle de numeration
• Number representation and finite automata
• Trees and languages with periodic signature
• Abstract numeration systems
• Numeration systems on a regular language
• How to write integers in a non-integral basis
• Title not available (Why is that?)
• The signature of rational languages
• Odometers on regular languages
• Combinatorial and probabilistic properties of systems of numeration
• Analysis of Carry Propagation in Addition: An Elementary Approach

Cited In (2)

• Regular sequences and synchronized sequences in abstract numeration systems
• Analysis of carries in signed digit expansions

This page was built for publication: The carry propagation of the successor function

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