The sum-of-digits function on arithmetic progressions

DOI10.2140/MOSCOW.2020.9.43MaRDI QIDQ2299252zbMATH OpenOpenAlexFDO

Authors Lukas Spiegelhofer, Thomas Stoll

Publication date 21 February 2020

Published in Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

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

zbMATH Keywords

arithmetic progressionCusick's conjecturesum-of-digits function

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Arithmetic progressions (11B25)

Abstract: Let $s_2$ be the sum-of-digits function in base $2$, which returns the number of non-zero binary digits of a nonnegative integer $n$. We study $s_2$ alon g arithmetic subsequences and show that --- up to a shift --- the set of $m$-tuples of integers that appear as an arithmetic subsequence of $s_2$ has full complexity.

Review text

Let \(s_2(n)\) be the sum of digits of \(n\) in base \(2\). This paper investigates the behaviour of \((m+1)\)-tuples of the form \[(s_2(n),s_2(n+t),\ldots,s_2(n+mt))\] for fixed integer \(m \geq 1\). The main result states that all possible \((m+1)\)-tuples of integers can occur for suitable \(n\) and \(t\), up to a shift: specifically, given integers \(k_1,k_2,\ldots,k_m\), there exist integers \(n,t \geq 0\) such that \[k_j = s_2(n+j t) - s_2(n)\] for \(1 \leq j \leq m\). Based on the heuristic that the differences \(s_2(n+jt)\) should be almost independent for most \(t\), the authors propose the following generalisation of Cusick's conjecture (which is the special case \(m=1\)): let \(c_t^{(m)}\) be the density of nonnegative integers \(n\) for which \(s_2(n) \leq s_2(n+jt)\) holds for all \(1 \leq j \leq m\). It is conjectured that \[c_t^{(m)} > \frac{1}{2^m}\] for all \(t \geq 0\). Moreover, if \(C_t^{(m)}\) denotes the density of integers \(n\) with \[s_2(n) \leq s_2(n+t) \leq s_2(n+2t) \leq \cdots \leq s_2(n+mt),\] then it is conjectured that \[C_t^{(m)} > \frac{1}{2^m m!}\] for all \(t \geq 0\).

Recommendations

• On a conjecture of Cusick concerning the sum of digits of n and n+t
• Approaching Cusick's conjecture on the sum-of-digits function
• On a conjecture of Dekking: the sum of digits of even numbers
• A lower bound for Cusick’s conjecture on the digits of n + t
• The binary digits of n+t

Cites work

• Approaching Cusick's conjecture on the sum-of-digits function
• Central limit theorem for probability measures defined by sum-of-digits function in base 2
• Gowers norms for the Thue-Morse and Rudin-Shapiro sequences
• Indépendance statistique d'ensembles liés à la fonction "somme des chiffres"
• Normality of the Thue-Morse sequence along Piatetski-Shapiro sequences. II
• On a conjecture of Cusick concerning the sum of digits of n and n+t
• On arithmetic progressions of integers with a distinct sum of digits

Cited in

(13)

• On the sum of digits functions for number systems with negative bases
• The truncated sum of digits function of polynomial sequences
• Finite generating functions for the sum-of-digits sequence
• A remark on a summation formula related with the sum of digits
• The truncated sum-of-digits function of powers
• On a conjecture of Cusick concerning the sum of digits of n and n+t
• scientific article; zbMATH DE number 1829512 (Why is no real title available?)
• scientific article; zbMATH DE number 5688289 (Why is no real title available?)
• On the hereditary sum of digits function to base q
• Approaching Cusick's conjecture on the sum-of-digits function
• The Sum-of-Digits Function of Squares
• The binary digits of n+t
• Relations among arithmetical functions, automatic sequences, and sum of digits functions induced by certain Gray codes

This page was built for publication: The sum-of-digits function on arithmetic progressions

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