A pattern sequence approach to Stern's sequence

DOI10.1016/J.DISC.2011.07.029zbMATH Open1315.11019DBLPjournals/dm/CoonsS11arXiv1105.0086OpenAlexW2132962549WikidataQ60692153 ScholiaQ60692153MaRDI QIDQ409393FDOQ409393

Jeffrey Shallit, Michael Coons

Publication date: 13 April 2012

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

Abstract: Let w be a binary string and let a_w (n) be the number of occurrences of the word w in the binary expansion of n. As usual we let s(n) denote the Stern sequence; that is, s(0)=0, s(1)=1, and for n >= 1, s(2n)=s(n) and s(2n+1)=s(n)+s(n+1). In this note, we show that s(n) = a_1 (n) + sum_{w in 1 (0+1)*} s([w bar]) a_{w1} (n) where w bar denotes the complement of w (obtained by sending 0 to 1 and 1 to 0, and [w] denotes the integer specified by the word w interpreted in base 2.

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

Recommendations

• A correlation identity for Stern's sequence
• Sturmian words and the Stern sequence
• The modular distribution of Stern's sequence
• On some conjectures concerning Stern's sequence and its twist
• Stern's diatomic sequence \(0, 1, 1, 2, 1, 3, 2, 3, 1, 4, \dots \)

zbMATH Keywords

pattern sequence expansionStern sequence

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15) Automata sequences (11B85)

Cites Work

• The ring of \(k\)-regular sequences
• Automatic Sequences
• Title not available (Why is that?)
• Pattern spectra, substring enumeration, and automatic sequences
• Paper Folding, Digit Patterns and Groups of Arithmetic Fractals
• Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,…

Cited In (4)

• Asymptotic analysis of \(q\)-recursive sequences
• Combinatorics on patterns of a bidimensional Sturmian sequence
• Sturmian words and the Stern sequence
• Counting the number of non-zero coefficients in rows of generalized Pascal triangles

This page was built for publication: A pattern sequence approach to Stern's sequence

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