We consider in general two-block substitutions and their fixed points. We prove that some of them have a simple structure: their fixed points are morphic sequences. Others are intrinsically more complex, such as the Kolakoski sequence. We prove this for the Thue-Morse sequence in base 3/2.

We characterize the entries of Hofstadter’s G-sequence in terms of the lower and upper Wythoff sequences. This can be used to give a short and comprehensive proof of the equality of Hofstadter’s G-sequence and the sequence of averages of the swapped Wythoff sequences. In the second part we give some results that hold when one re-places the golden mean by other quadratic algebraic numbers. In the third part we prove a close relationship between Hofstadter’s G-sequence and a sequence studied by Avdivpahić and Zejnulahi.

We discuss the base 3/2 representation of the natural numbers. We prove that the sum-of-digits function of the representation is a fixed point of a 2-block substitution on an infinite alphabet, and that this implies that sum-of-digits function modulo 2 of the representation is a fixed point x_3/2 of a 2-block substitution on {0,1}. We prove that x_3/2 is invariant for taking the binary complement, and present a list of conjectured properties of x_3/2, which we think will be hard to prove. Finally, we make a comparison with a variant of the base 3/2 representation, and give a general result on p-q-block substitutions.

In a base phi representation, a natural number is written as a sum of powers of the golden mean φ. There are many ways to do this. Well known is the standard representation, introduced by George Bergman in 1957, where a unique representation is obtained by requiring that no consecutive powers, φⁿ and φⁿ⁺¹, occur in the representation. In this paper, we introduce a new representation by allowing that the powers φ⁰ and φ¹ may occur at the same time, but no other consecutive powers. We then argue that this representation is much closer to the classical representation of the natural numbers by powers of an integer than Bergman’s standard representation.

In this paper we introduce a technique to determine the sumset A + A, where A is the indicator function of the 0’s occurring in a fixed point x of a substitution on the alphabet {0, 1}.

We consider the sum of digits functions for both base phi, and for the Zeckendorf expansion of the natural numbers. For both sum of digits functions we present morphisms on infinite alphabets such that these functions viewed as infinite words are letter-to-letter projections of fixed points of these morphisms. We characterize the first differences of both functions a) with generalized Beatty sequences, or unions of generalized Beatty sequences, and b) with morphic sequences.

In this paper we classify the Zeckendorf expansions according to their digit blocks. It turns out that if we consider these digit blocks as labels on the Fibonacci tree, then the numbers ending with a given digit block in their Zeckendorf expansion appear as compound Wythoff sequences in a natural way on this tree. Here the digit blocks consisting of only 0’s are an exception. We also give a second description of these occurrence sequences as generalized Beatty sequences. Finally, we characterize the numbers with a fixed digit block occurring at an arbitrary fixed position in their Zeckendorf expansions, and determine their densities.

In the base phi representation, any natural number is written uniquely as a sum of powers of the golden mean with coefficients 0 and 1, where it is required that the product of two consecutive digits is always 0. In this self-contained paper, we give a new and short proof of the recursive structure of the base phi representations of the natural numbers.

In the base phi expansion any natural number is written uniquely as a sum of powers of the golden mean with digits 0 and 1, where one requires that the product of two consecutive digits is always 0. In this paper we show that the sum of digits function modulo 2 of these expansions is a morphic sequence. In particular we prove that — like for the Thue-Morse sequence — the frequency of 0’s and 1’s in this sequence is equal to 1/2.

Morphic words are letter-to-letter images of fixed points x of morphisms on finite alphabets. There are situations where these letter-to-letter maps do not occur naturally, but have to be replaced by a morphism. We call this a decoration of x. Theoretically, decorations of morphic words are again morphic words, but in several problems the idea of decorating the fixed point of a morphism is useful. We present two of such problems. The first considers the so called AA sequences, where α is a quadratic irrational, A is the Beatty sequence defined by A(n)=⌊αn⌋, and AA is the sequence (A(A(n))). The second example considers homomorphic embeddings of the Fibonacci language into the integers, which turns out to lead to generalized Beatty sequences with terms of the form V(n)=p⌊αn⌋+qn+r, where p,q and r are integers.

Number the cells of a (possibly infinite) chessboard in some way with the numbers 0, 1, 2, … . Consider the cells in order, placing a queen in a cell if and only if it would not attack any earlier queen. The problem is to determine the positions of the queens. We study the problem for a doubly-infinite chessboard of size ℤ × ℤ numbered along a square spiral, and an infinite single-quadrant chessboard (of size N × N) numbered along antidiagonals. We give a fairly complete solution in the first case, based on the Tribonacci word. There are connections with combinatorial games.

Let S be a map from a language Lto the integers satisfying S(vw) =S(v) +S(w)for all v, w ∈L. The classical Frobenius problem asks whether the complement of S(L)in the natural numbers will be infinite or finite, and in the latter case the value of the largest element in this complement. This is also known as the ‘coin-problem’, and Lis the full language consisting of all words over a finite alphabet. We solve the Frobenius problem for the golden mean language, any Sturmian language and the Thue–Morse language. We also consider two-dimensional embeddings.

Primitive constant length substitutions generate minimal symbolic dynamical systems. In this article we present an algorithm which can produce the list of injective substitutions of the same length that generate topologically conjugate systems. We show that each conjugacy class contains infinitely many substitutions which are not injective. As examples, the Toeplitz conjugacy class contains three injective substitutions (two on two symbols and one on three symbols), and the length two Thue–Morse conjugacy class contains twelve substitutions, among which are two on six symbols. Together, they constitute a list of all primitive substitutions of length two with infinite minimal systems which are factors of the Thue–Morse system.