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. How many? Even if the number of powers of φ is finite, then any number has infinitely many base phi representations. By not allowing an expansion to end with the digits 0, 1, 1, the number of expansions becomes finite, a solution proposed by Ron Knott. Our first result is a recursion to compute this number of expansions. This recursion is closely related to the recursion given by Neville Robbins to compute the number of Fibonacci representations of a number, also known as Fibonacci partitions. We propose another way to obtain finitely many expansions, which we call the natural base phi expansions. We prove that these are closely connected to the Fibonacci partitions.

In the base phi expansion, a 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. We tackle the problem of describing these expansions in detail. We classify the positive parts of the base phi expansions according to their suffixes, and the negative parts according to their prefixes, specifying the sequences of occurrences of these digit blocks. We prove that the positive parts of the base phi expansions are a subsequence of the sequence of Zeckendorf expansions, giving an explicit formula in terms of a generalized Beatty sequence. The negative parts of the base phi expansions no longer appear lexicographically. We prove that all allowed digit blocks appear, and determine the order in which they do appear.

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.

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.

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 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}.

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.

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.

An automatic sequence is a letter-to-letter coding of a fixed point of a uniform morphism. More generally, morphic sequences are letter-to-letter codings of fixed points of arbitrary morphisms. There are many examples where an, a priori, morphic sequence with a non-uniform morphism happens to be an automatic sequence. An example is the Lysënok morphism a → aca, b → d, c → b, d → c, the fixed point of which is also a 2-automatic sequence. Such an identification is useful for describing the dynamical systems generated by the fixed point. We give several ways to uncover such hidden automatic sequences, and present many examples. We focus in particular on morphisms associated with Grigorchuk groups.

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.

We give an in-depth analysis of an algorithm, introduced by Kimberling in the On-Line Encyclopedia of Integer Sequences, that generates permutations of the natural numbers. It turns out that each example of such a permutation in the Encyclopedia is completely determined by some 3-automatic sequence.

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.

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.

A generalized Beatty sequence is a sequence V defined by (Formula Presented) where α is a real number, and p, q, r are integers. Such sequences occur, for instance, in homomorphic embeddings of Sturmian languages in the integers. We consider the question of characterizing pairs of integer triples (p, q, r), (s, t, u) such that the two sequences (Formula Presented) are complementary (their image sets are disjoint and cover the positive integers). Most of our results are for the case that α is the golden mean, but we show how some of them generalize to arbitrary quadratic irrationals. We also study triples of sequences (Formula Presented) that are complementary in the same sense.