Baum–Sweet sequence

In mathematics the Baum–Sweet sequence is an infinite automatic sequence of 0s and 1s defined by the rule:

b_n = 1 if the binary representation of n contains no block of consecutive 0s of odd length;

b_n = 0 otherwise;

for n ≥ 0.^[1]

For example, b₄ = 1 because the binary representation of 4 is 100, which only contains one block of consecutive 0s of length 2; whereas b₅ = 0 because the binary representation of 5 is 101, which contains a block of consecutive 0s of length 1.

Starting at n = 0, the first few terms of the Baum–Sweet sequence are:

1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1 ... (sequence A086747 in the OEIS)

The properties of the sequence were first studied by L.E. Baum and M.M. Sweet in 1976.^[2]

Properties

The Baum–Sweet sequence can be generated by a three state automaton.^[3]

The value of term b_n in the Baum–Sweet sequence can be found recursively as follows. If n = m·4^k, where m is not divisible by 4 (or is 0), then

b_{n}={\begin{cases}1&{\text{if }}n=0\\0&{\text{if }}m{\text{ is even}}\\b_{(m-1)/2}&{\text{if }}m{\text{ is odd}}.\end{cases}}

Thus b₇₆ = b₉ = b₄ = b₀ = 1, which can be verified by observing that the binary representation of 76, which is 1001100, contains no consecutive blocks of 0s with odd length.

The Baum–Sweet word 1101100101001001..., which is created by concatenating the terms of the Baum–Sweet sequence, is a fixed point of the morphism or string substitution rules

00 → 0000

01 → 1001

10 → 0100

11 → 1101

as follows:

11 → 1101 → 11011001 → 1101100101001001 → 11011001010010011001000001001001 ...

From the morphism rules it can be seen that the Baum–Sweet word contains blocks of consecutive 0s of any length (b_n = 0 for all 2^k integers in the range 5.2^k ≤ n < 6.2^k), but it contains no block of three consecutive 1s.

The Baum–Sweet sequence is the sequence of coefficients of the unique solution of the cubic equation f³ + Xf + 1 = 0 in the field F₂((X⁻¹)) of formal Laurent series over F₂.^[4]

Notes

↑ Weisstein, Eric W. "Baum–Sweet Sequence". MathWorld.
↑ Baum, L. E. and Sweet, M. M. Continued Fractions of Algebraic Power Series in Characteristic 2 Ann. Math. 103, 593-610, 1976.
↑ Finite automata and arithmetic, Jean-Paul Allouche
↑ Graham Everest Recurrence Sequences AMS 2003, p 236

References

Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.

This article is issued from Wikipedia - version of the 11/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.