Generalizing the Wythoff Array and Other Fibonacci Facts to Tribonacci Numbers

Eric Chen, Adam Ge, Andrew Kalashnikov, Ella Kim, Evin Liang, Mira Lubashev, Matthew Qian, Rohith Raghavan, Benjamin Taycher, and

Samuel Wang PRIMES STEP

Department of Mathematics

MIT 77 Massachusetts Ave. Cambridge, MA 02139

USA

 primes.step@gmail.com

Tanya Khovanova Department of Mathematics

MIT 77 Massachusetts Ave. Cambridge, MA 02139

USA

   tanya@math.mit.edu

Abstract

In this paper, we generalize many facts from a recent paper of Conway and Ryba, where we replace the Fibonacci sequence in that paper with the Tribonacci sequence. We study the Tribonacci array, which we also call the Trithoff array to emphasize the connection to the Wythoff array. We also describe 13 new sequences.

1 Introduction

A recent paper by Conway and Ryba [2] studied the Wythoff array, which initially appeared in relation to the two-player combinatorial Wythoff game [8] that has deep connections to the Fibonacci numbers. In their paper, Conway and Ryba found that a pattern resembling the Empire State Building appears when the Wythoff array is extended, so our initial goal was to discover if an analog of the Empire State Building could be found for the Tribonacci sequences.

Throughout the paper, we discuss 23 existing sequences from the OEIS and study and describe 13 new sequences that arise from our arguments.

The Wythoff array is an infinite table that contains each integer exactly once, with numbers increasing along each row and column. The integers in the array can be naturally divided into pairs corresponding to the winning positions in the Wythoff combinatorial game. However, this paper uses an alternative definition of the Wythoff array using Fibonacci numbers.

We also study the Zeckendorf representation, which can be considered as a Fibonaccibase representation of an integer. Namely, every integer can be uniquely represented as a sum of distinct, non-consecutive Fibonacci numbers, which can be encoded as a string of ones and zeros without two consecutive ones. The nth column of the Wythoff array consists of numbers with n − 1 zeros at the end of their Zeckendorf representation. For example, the first column consists of the numbers whose Zeckendorf representations have a least significant digit of 1.

In their paper, Conway and Ryba [2] extended the array to the left and found some natural border lines that symmetrically surround the central column of the array. The lines form a shape resembling the Empire State Building. This led them to form several statements regarding the Wythoff array and Fibonacci numbers. We generalized several of these statements to the Tribonacci numbers before moving on to topics unrelated to the Conway-Ryba paper. The analog of the Wythoff array is known as the Tribonacci array [4, 5], but in this paper, we use the term “Trithoff array” to emphasize the connection to the Wythoff array.

We did not ultimately find an analog of the Empire State Building in the Trithoff array because when extending the Trithoff array to the left, we lose the symmetry properties of the array. However, the extended array still yielded many interesting discoveries. Next, we present an overview of the sections of the paper.

Section 2 covers the list of facts from the Conway-Ryba paper [2] that we generalize. We state well-known facts about Tribonacci numbers T_{n}, the Fibonacci word, and the Tribonacci word. We introduce the Tribonacci successor of an integer n, which we denote as out(n) in accordance with Conway and Ryba [2].

The Tribonacci sequence is known to grow approximately as a geometric series α^{n}, where α = 1.83929 … is the Tribonacci constant. In Section 3 we bound the value of out(n) to be αn − 0.85 < out(n) < αn + 0.85. We also study the difference T_{n+1} − αT_{n}, showing that the sequence of these differences cannot have the same sign for any three consecutive terms and describing positive and negative records for such differences.

In Section 4, we discuss the Trithoff array. In Section 4.1, we discuss difference sequences for every row and, for a given row, how to find the row that represents its difference sequence. We prove that given a row r, we can find another row such that r is its difference sequence if and only if row r does not repeat periodically even, even, odd, and odd numbers. In Section 4.2, we describe the difference sequence of the first column and show that it consists of twos and threes. We also show that a number in column c and row r of the Trithoff array can be approximated as \frac{rα^{c}}{α−1}.

In Section 5, we extend the Trithoff array to the left. We study the columns −2, −1, and 0, which we call, by analogy to Conway-Ryba [2], the pre-seed, seed, and wall. We describe these columns in terms of the first column. For example, we prove that the wall term w, in column 0, is followed by out(w) − 1 in the first column. The pre-seed, seed, and wall form new sequences, which we describe in detail.

In Section 6, we prove that the tail of every positive Tribonacci-like sequence appears in the Trithoff array. We also study how multiples of Tribonacci-like sequences appear in the array and prove that such multiples appear in order. Furthermore, we show that the nth multiple of a Tribonacci-like sequence has a row number equal to 1 modulo n. We explain that when extending a positive Tribonacci-like sequence to the left, there exists some index i before which the sequence cannot have three consecutive numbers with the same sign. Moreover, if we take the absolute values of the numbers before the index i and reverse the sequence, it cannot be a Tribonacci-like sequence. This is different from the Fibonacci case.

In Section 7, we describe the Fibbinary, Tribbinary, Fibternary, and Tribternary numbers and their properties.

2 Preliminaries

2.1 The extra Fibonacci series and the Empire State Building

We summarize results relevant to us from the paper of Conway and Ryba [2]. The paper has many numbered statements labeled as facts. Here we present some of the facts from that paper that we plan to generalize, using their numbering, but in a different order.

In the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, … (\underline{A000045}), each term is the sum of the previous two. We say that this sequence follows the Fibonacci rule. Integer sequences that follow the Fibonacci rule and end in positive integers are called extraFib series or extraFibs. The name was introduced in [2]. They use the word series to emphasize that the sequences can be extended in both directions.

The Zeckendorf representation of an integer k is its expression as a sum of positive Fibonacci numbers, where each Fibonacci number can only be used once, and there can be no two consecutive Fibonacci numbers in the sum.

Fact 2. The Zeckendorf expansion of n is unique.

Suppose integer n has Zeckendorf representation

n = F_{i_{1}} + ⋯ + F_{i_{k}}.

We can denote the Fibonacci successor of n as out(n), where it is defined as

out(n) = F_{i_{1}+1} + ⋯ + F_{i_{k}+1}.

Fact 1. The function out(n) is well-defined.

The golden ratio (1 + \sqrt{5})/2, denoted by ϕ, is used in the next fact.

Fact 3. The unique integer in the open unit interval (ϕn − ϕ^{−2}, ϕn + 1 − ϕ^{−2}) is out(n).

The Wythoff array is an infinite table W_{m,n}, with m, n > 0, where W_{m,n} denotes the entry in row m and column n of the array, and where

• W_{m,1} = ⌊⌊mϕ⌋ϕ⌋,

• W_{m,2} = ⌊⌊mϕ⌋ϕ^{2}⌋,

• W_{m,n} = W_{m,n−2} + W_{m,n−1} for n > 2.

We see that each row of the array is an extraFib, and thus, we can continue each sequence to the left. Table 1 shows the corner of the Wythoff array with two more columns on the left.

0 1 1 2 3 5 8 13 21 34 …
1 3 4 7 11 18 29 47 76 123 …
2 4 6 10 16 26 42 68 110 178 …
3 6 9 15 24 39 63 102 165 267 …
4 8 12 20 32 52 84 136 220 356 …
5 9 14 23 37 60 97 157 254 411 …
6 11 17 28 45 73 118 191 309 500 …
7 12 19 31 50 81 131 212 343 555 …
8 14 22 36 58 94 152 246 398 644 …
9 16 25 41 66 107 173 280 453 733 …
10 17 27 44 71 115 186 301 487 788 …

Table 1: The Garden State.

Conway and Ryba [2] call the table the Garden State. The numbers in the first column (index −1) are called the seed terms; in the second column (index 0), the wall terms; and other numbers are called the Garden (indexed starting from 1). The Garden grows out in the sense that for every term n in the Garden, the next term to the right is out(n).

The rows are indexed starting from 1. The first row is Fibonacci numbers, while the second row is Lucas numbers. The next three rows are 2, 3, and 4 times the Fibonacci numbers. The sixth row is called the Pibonacci numbers (\underline{A104449}). When extended to the left, the first few terms of the sequence look like the digits of the number Pi: 3, 1, 4, 5, 9.

We can see that the first column of the Wythoff array consists of integers whose Zeckendorf representation ends in 1. It is easy to prove the following structure of Table 1.

Fact 5.

(a) A garden term n is followed by out(n).

(b) A seed term s is followed by out(s) + 1.

(c) A wall term w is followed by out(w) − 1.

We also have the following amazing fact about how natural numbers appear in the Garden State.

Fact 6. Every positive integer appears exactly once in the Garden and once as a seed, and zero also appears just once as a seed.

The next fact explains how extraFibs appear in the array.

Fact 7. Every series that satisfies Fibonacci’s rule and ends with positive integers is represented in the Garden State.

By the words “is represented,” they mean that given an extraFib (which may be extended in both directions), we can find a number k, such that all the terms of the extraFib starting from index k form a row in the Garden State.

Fact 8. If X_{n} is any extraFib series, so too is any positive multiple mX_{n}.

Fact 9. The multiples of any extraFib series appear in order in the Garden State.

The parts above related to the Garden, also known as the Wythoff array, are widely known.

The paper [2] also describes how to find each particular extraFib in the Garden State. Given the extraFib S_{n}, we expand it to the left and right and find the out values of every term. The wall term S_{w} corresponds to the largest w, such that S_{w+1} = out(w) − 1.

It is well-known that if we continue extraFibs to the left, negative integers will alternate with positive integers. Thus, Conway and Ryba defined a reversal of an extraFib, which is obtained by reversing the order and changing negative signs to positive ones. One can check the following fact.

Fact 10. The reversal of an extraFib series is also an extraFib series.

In our paper, we prove analogs of facts described above for the Tribonacci case. We denote our analogs of these facts with the letter T after the number. But first, we need some more information about Fibonacci numbers.

2.2 The Fibonacci word

A Fibonacci word is an infinite word in a two-letter alphabet formed by the following infinite process. Let S_{0} = a and S_{1} = ab. Now S_{n} = S_{n−1}S_{n−2}, the concatenation of the previous word and the one before that. The infinite Fibonacci word is the limit S_{∞}, that is, the unique infinite sequence that contains each S_{n}, for finite n, as a prefix. The first few terms of the Fibonacci word, which we index starting from 1, are described in sequence \underline{A003849}:

abaababaabaab ….

The positions of a’s form the lower Wythoff sequence \underline{A000201}. These are the numbers from the odd-numbered columns in the Wythoff array. Moreover, these are the wall numbers. The positions of b’s form the complementary sequence: the upper Wythoff sequence \underline{A001950}.

Now we describe the background for the Tribonacci numbers.

2.3 Tribonacci numbers

The Tribonacci numbers T_{n} start with T_{0} = 0, T_{1} = 0, T_{2} = 1, and each Tribonacci number thereafter is calculated by summing up the previous 3 numbers:

T_{n} = T_{n−1} + T_{n−2} + T_{n−3}

for n > 2. The Tribonacci sequence, \underline{A000073}, starts as

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, ….

The Tribonacci representation of an integer k is its expression as a sum of positive Tribonacci numbers, where each Tribonacci number can only be used once, and there can be no 3 consecutive Tribonacci numbers in the sum. Note that number 1 can only be used once, even though it appears twice in the sequence.

The Tribonacci representation can be viewed as numbers written in the Tribonacci base. We denote the Tribonacci representation of integer N as (N)_{T} and the evaluation of a string w written in the Tribonacci base as [w]_{T}. For example, 9 can be expressed as 7 + 2, making 1010 a Tribonacci representation of 9, where the rightmost digit 0 means that there is no 1 in the sum, the 1 to the left of that means that there is a 2, the 0 to the left of that means that there is no 4, and finally the leftmost 1 means that there is one 7. Thus, we write (9)_{T} = 1010 and [1010]_{T} = 9.

Such a Tribonacci representation can be found by using a greedy algorithm. Start by finding the largest Tribonacci number that is less than the given number and subtract it. Then repeat the process. This method ensures that no three consecutive Tribonacci numbers are used. This is similar to Fact 2 in the Conway and Ryba paper [2] in that the Zeckendorf representation is unique. The following theorem is proved in [5].

Fact 2T. Every natural number has a unique Tribonacci representation.

Consider the characteristic equation for the Tribonacci sequence:

x^{3} − x^{2} − x − 1 = 0.

We can define the Tribonacci successor similarly to how the Fibonacci successor is defined. Suppose integer n has a Tribonacci representation

n = T_{i_{1}} + ⋯ + T_{i_{k}}.

We define the Tribonacci successor of n as out(n), where

out(n) = T_{i_{1}+1} + ⋯ + T_{i_{k}+1}.

The following analog of Fact 1 follows from the uniqueness of the Tribonacci representation.

Fact 1T. The Tribonacci successor is well-defined.

The Tribonacci numbers grow approximately as a geometric series with a ratio of approximately 1.83929. This ratio is the largest root of the characteristic equation for the Tribonacci sequence and is called Tribonacci constant, and we denote it as α. Thus,

out(n) ≈ αn.

2.4 The Tribonacci word

The Tribonacci word is the limit of the sequence of words W (n), where W (n) is a string of digits a, b, and c formed in the following manner: W (0) = a, W (1) = ab, and W (2) = abac. Then W (n) = W (n − 1)W (n − 2)W (n − 3) is the concatenation of the previous Tribonacci word, the one before it, and the one before that. For example,

W (3) = abacabaabacab

is a prefix of the Tribonacci word.

The following theorem [4] by Duchêne and Rigo connects the positions of different letters in the Tribonacci word with their Tribonacci representations.

Theorem 1 ([4]). The nth symbol of the Tribonacci word is a, b, or c if the Tribonacci representation of n − 1 ends in 0, 01, or 11, respectively.

This is equivalent to the following statement: The nth symbol of the Tribonacci word depends on the number of trailing zeros of the Tribonacci representation of n. The nth symbol is a, b, or c if the number of trailing zeros is equal to 0, 1, or 2 modulo 3, respectively. Equivalently, the nth symbol of the Tribonacci word is a, b, or c if n is in the column number of the Trithoff array (defined later) that has remainder 1, 2, or 0 modulo 3, respectively.

The following three complementary sequences correspondingly describe the positions of letters a, b, and c in the Tribonacci word.

Sequence \underline{A003144} describes the positions of the letter a in the Tribonacci word.

1, 3, 5, 7, 8, 10, 12, 14, 16, 18, 20, 21, 23, 25, 27, 29, 31, ….

It is known [3] that \underline{A003144}(n) is always either ⌊αn⌋ or ⌊αn + 1⌋ for all n, where α is the Tribonacci constant. In other words, αn − 1 < \underline{A003144}(n) < αn + 1.

Sequence \underline{A003145} describes the positions of the letter b in the Tribonacci word.

2, 6, 9, 13, 15, 19, 22, 26, 30, 33, 37, 39, 43, 46, 50, 53, 57, ….

Sequence \underline{A003146} describes the positions of the letter c in the Tribonacci word.

4, 11, 17, 24, 28, 35, 41, 48, 55, 61, 68, 72, 79, 85, 92, 98, 105, ….

3 Bounds on the successor

The Tribonacci sequence grows approximately as a geometric progression with the ratio α. It is well-known (see, for example, [1]), that for n > 2, we have T_{n} < α^{n−2} < T_{n+1}.

We are interested in a Tribonacci analog of Fact 3, which provides bounds on the Fibonacci successor. We start by estimating the growth of the Tribonacci sequence in terms of the roots of the characteristic equation defined in the previous section. In addition to the largest root, α, we also denote the other two roots as β and γ, which are conjugates of each other, and β has the positive imaginary part.

Lemma 2. We have

|T_{n+1} − αT_{n}| < \frac{2α^{− \frac{n}{2}}}{|β − γ|}.

Proof. The explicit formula for T_{n} in terms of roots of the characteristic equation is wellknown [7]:

T_{n} = \frac{α^{n}}{(α − β)(α − γ)} + \frac{β^{n}}{(β − α)(β − γ)} + \frac{γ^{n}}{(γ − α)(γ − β)}.

We compute

T_{n+1} − αT_{n} = \frac{α^{n+1}}{(α − β)(α − γ)} + \frac{β^{n+1}}{(β − α)(β − γ)} + \frac{γ^{n+1}}{(γ − α)(γ − β)}−

\frac{αα^{n}}{(α − β)(α − γ)} + \frac{αβ^{n}}{(β − α)(β − γ)} + \frac{αγ^{n}}{(γ − α)(γ − β)} = \frac{β^{n}}{β − γ} + \frac{γ^{n}}{γ − β} .

Taking the absolute value of both sides, we get |T_{n+1} − αT_{n}| ≤ |\frac{β^{n}}{β−γ} | + |\frac{γ^{n}}{γ−β} |. Since |β| = |γ|, we get |T_{n+1} − αT_{n}| ≤ 2\frac{|β|^{n}}{|β−γ|}. Since |β| = |γ| and αβγ = 1, we know that |β|^{n} = α^{− \frac{n}{2}} . The lemma follows.

Fact 3T. If out(n) is the Tribonacci successor of n, then

−0.85 < out(n) − αn < 0.85.

Proof. Suppose the Tribonacci representation of n is T_{a} + T_{b} + ⋯, where a ≥ 3. Then the successor is T_{a+1} + T_{b+1} + · · ·. By Lemma 2, we have

| out(n) − αn| < \frac{2α^{− \frac{a}{2}}}{|β − γ|} + \frac{2α^{− \frac{b}{2}}}{|β − γ|} + · · · .

Given that the Tribonacci representation excludes three consecutive Tribonacci numbers, we can bound the expression as

\frac{2}{|β − γ|} (α^{− \frac{3}{2}} + α^{− \frac{4}{2}} + α^{− \frac{6}{2}} + α^{− \frac{7}{2}} + ⋯) =

\frac{2}{|β − γ|} (α^{− \frac{3}{2}} + α^{− \frac{4}{2}} ) ∑_{m=0}^{∞} α^{− \frac{3m}{2}} = \frac{2(α^{− \frac{3}{2}} + α^{− \frac{4}{2}} )}{|β − γ|(1 − α^{− \frac{3}{2}} )} ≈ 1.91746 < 2.

We can improve this bound further by adding computational results. We calculated the largest possible difference for numbers that have a Tribonacci representation up to 35 Tribonacci digits. The largest possible difference was less than 0.849. By a similar calculation to the one above, the larger digits can contribute to the difference no more than

\frac{2(α^{− \frac{36}{2}} + α^{− \frac{37}{2}} )}{|β − γ|(1 − α^{− \frac{3}{2}} )} < 0.0001.

Thus, the maximum difference is not more than 0.85.

Consider the sequence of integers n such that T_{n+1} − αT_{n} is positive. This is a newly added sequence \underline{A352719}:

0, 1, 3, 4, 6, 7, 9, 10, 12, 15, 18, 21, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 41, 44, ….

Let us denote this sequence as P (k), where P (0) = 0 and P (1) = 1. We denote by Q(n) the complementary sequence, with Q(1) = 2. The sequence Q(n) is the sequence of integers n such that T_{n+1} − αT_{n} is negative. This is a newly added sequence \underline{A352748}:

2, 5, 8, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 28, 31, 34, 37, 39, 40, 42, 43, 45, ….

Proposition 3. The value T_{n+1} − αT_{n} cannot have the same sign for any three consecutive integers n.

Proof. From the proof of Lemma 2, we know that T_{i+1} − αT_{i} = \frac{β^{i}}{β−γ} + \frac{γ^{i}}{γ−β} = 2ℜ(\frac{β^{i}}{β−γ}), where ℜ is the real part of a complex number. Now 2ℜ(\frac{β^{a}}{β−γ}) = \frac{2|β^{a}|}{β−γ} sin(aψ), where ψ is the polar angle coordinate of β. We can calculate ψ ≈ ±2.17623 radians, so \frac{π}{2} < |ψ| < π.

If ℜ(\frac{β^{i}}{β−γ}) is positive, then −\frac{π}{2} ≤ arg \frac{β^{i}}{β−γ} ≤ \frac{π}{2}. Since β − γ is purely imaginary, this is equivalent to 0 ≤ arg β^{i} ≤ π. Hence, 2πn ≤ i arg β = iψ ≤ 2πn + π for some integer n. Equivalently, the fractional part of i\frac{ψ}{2π} is at most \frac{1}{2}. Similarly, ℜ(\frac{β^{i}}{β−γ}) is negative if the fractional part of i\frac{ψ}{2π} is at least \frac{1}{2}.

Now suppose that ℜ(\frac{β^{i}}{β−γ}) is positive for i = k and i = k + 1. Then for certain integers n and n′, we have n ≤ k \frac{ψ}{2π} ≤ n+ \frac{1}{2} and n′ ≤ k \frac{ψ}{2π} + \frac{ψ}{2π} ≤ n′ + \frac{1}{2}. Since n′ ≤ k \frac{ψ}{2π} + \frac{ψ}{2π} ≤ n+ \frac{1}{2} + \frac{ψ}{2π} and \frac{ψ}{2π} ≤ \frac{1}{2}, we have n′ ≤ n. Also, n ≤ k \frac{ψ}{2π} ≤ n′ + \frac{1}{2} − \frac{ψ}{2π}, so n = n′. Hence if ℜ(\frac{β^{i}}{β−γ}) is positive for i = k, k + 1, and k + 2, then for some integer n,

n ≤ k \frac{ψ}{2π} < k \frac{ψ}{2π} + \frac{ψ}{2π} < k \frac{ψ}{2π} + 2\frac{ψ}{2π} ≤ n + \frac{1}{2},

which is impossible because 2\frac{ψ}{2π} > \frac{1}{2}. Hence ℜ(\frac{β^{i}}{β−γ}) cannot be positive for three consecutive integers. Similarly, ℜ(\frac{β^{i}}{β−γ}) cannot be negative for three consecutive integers.

It follows that P (n) − P (n − 1) < 3, and the sequence P (n) does not contain three consecutive numbers. An analogous statement is true for Q(n).

We are interested in the numbers n such that the difference out(n) − αn is bigger than the differences for all smaller n. We say that such numbers n create new records in positive differences. We define records in negative differences similarly, where the difference is smaller than those of all smaller n.

Proposition 4. Numbers that create new records in positive differences have the following properties.

1. If k is a positive record, then all the indices in its Tribonacci representation belong to the sequence P (n).

2. For any k, the number T_{P (2)} + T_{P (3)} + ⋯ + T_{P (k−1)} + T_{P (k)}, creates a new record for positive differences.

3. For every t > 1, there exists N_{0} such that the Nth positive (negative) record for any N > N_{0} contains P (t).

Similar statements are true for negative differences.

Proof. Consider the Tribonacci representation of n. Suppose n achieves a new positive record, and suppose its Tribonacci representation contains T_{j} such that out(T_{j}) − αT_{j} < 0; that is, j ≠ P (t) for t > 1. Then consider the number n − T_{j}. The corresponding difference out(n − T_{j}) − α(n − T_{j}) equals out(n) − out(T_{j}) − αn + αT_{j} > out(n) − αn. Thus, the difference for a smaller number n − T_{j} exceeds the difference for a larger number n, which means n cannot be a record. Hence, the Tribonacci representations of records must only have terms of the form T_{P (t)} for some t > 1.

Moreover, suppose we have a number n with Tribonacci representation T_{P (2)} + T_{P (3)} + ⋯+T_{P (k−1)} +T_{P (k)} for some k. Consider a number m < n. Its Tribonacci representation can be built by removing some of the terms T_{P (j)} for j ≤ k and adding terms of the form T_{Q(i)}. That is, we remove terms contributing a positive difference and add terms contributing a negative difference. Then out(n) − αn > out(m) − αm. So n is a record.

Finally, we show that for t > 1, every term T_{P (t)} is contained in the Tribonacci representation of every sufficiently large record. First, as we just showed, for every M, the number N_{0} = T_{P (2)} + T_{P (3)} + ⋯ + T_{P (M−1)} + T_{P (M)} is a record. Suppose N > N_{0} does not contain T_{P (t)} in its Tribonacci representation. Then (out(N_{0}) − αN_{0}) − (out(N) − αN) ≥ T_{P (t)+1} − αT_{P (t)} − (T_{P (a_{0})+1} − αT_{P (a_{0})} + T_{P (a_{1})+1} − αT_{P (a_{1})} + ⋯), where the a_{i} are all greater than M. But from Lemma 2, we know that T_{P (a_{i})+1} − αT_{P (a_{i})} ≤ 2\frac{|β|^{P (a_{i})}}{|β−γ|}. Thus, T_{P (a_{0})+1} − αT_{P (a_{0})} + T_{P (a_{1})+1} − αT_{P (a_{1})} + ⋯ is bounded by \frac{2}{|β−γ|}(|β|^{M+1} + |β|^{M+2} + ⋯) =

\frac{2|β|^{M+1}}{|β−γ|(1−|β|)}, which goes to 0 as M goes to infinity. We know that T_{P (t)+1}−αT_{P (t)} is positive, so picking a sufficiently large M, we can ensure that (T_{P (a_{0})+1}−αT_{P (a_{0})}+T_{P (a_{1})+1}−αT_{P (a_{1})}+⋯) is smaller than T_{P (t)+1} − αT_{P (t)}. Thus, (out(N_{0}) − αN_{0}) − (out(N) − αN) is positive, and N is not a record.

The argument for negative records is similar.

Table 2a lists n that set a new record for a positive difference out(n) − αn. The first column shows n, the second column shows the approximate value of |αn − out(n)|, and the last column shows the indices of the Tribonacci numbers in the Tribonacci representation of n. The proposition above tells us that the numbers in the right column belong to sequence P (k). Moreover, in the limit, the numbers approach the sequence P (k) in reverse order. The data for negative records is in Table 2b.

Remark 5. Fact 3T bounds the absolute value of new records by 0.85. We see in Tables 2a and 2b that positive records are close to this bound, while the bound on negative records has room for improvement. We leave it to future researchers to find tighter bounds.

4 Trithoff array

We want to build the analog of the Wythoff array for Tribonacci numbers. We call it the Trithoff array. The first column consists of numbers in increasing order whose Tribonacci representation ends in 1. For a number n in the array, the number to the right is out(n). Thus, the second column is numbers whose Tribonacci representation ends in 10, and so on. Table 3 shows the Trithoff array, where the last column is the sequence numbers in the OEIS [6] for corresponding rows. The array itself is represented in the OEIS as sequence \underline{A136175},

1 0.1607132  [3]
2 0.3214264  [4]
3 0.4821397  [4, 3]
10 0.6071324  [6, 4, 3]
23 0.6964046  [7, 6, 4, 3]
67 0.7677874  [9, 7, 6, 4, 3]
148 0.7855602  [10, 9, 7, 6, 4, 3]
341 0.8032164  [12, 9, 7, 6, 4, 3]
422 0.8209892 [12, 10, 9, 7, 6, 4, 3]

(a) Records for positive difference.

\begin{matrix}4 & −0.3571470 & [5] \\ 28 & −0.5000291 & [8, 5] \\ 177 & −0.5537556 & [11, 8, 5] \\ 681 & −0.5542803 & [13, 11, 8, 5] \\ 1104 & −0.5725777 & [14, 11, 8, 5] \\ 1608 & −0.5731023 & [14, 13, 11, 8, 5] \\ 4240 & −0.5758421 & [16, 14, 11, 8, 5] \\ 4744 & −0.5763667 & [16, 14, 13, 11, 8, 5] \\ 6872 & −0.5785818 & [17, 14, 11, 8, 5] \end{matrix}

(b) Records for negative difference.

Table 2: Records for positive and negative difference.

and it is called the Tribonacci array. By analogy with Conway and Ryba [2], we will later extend the Trithoff array while we call this part the Garden State.

row\column 1 2 3 4 5 6 …
1  1 2 4 7 13 24 … \underline{A000073}
2  3 6 11 20 37 68 … \underline{A001590}
3  5 9 17 31 57 105 … \underline{A000213}
4  8 15 28 51 94 173 … \underline{A214899}
5  10 19 35 64 118 217 … \underline{A020992}
6  12 22 41 75 138 254 … \underline{A100683}
…  . . . . . . . . . . . . . . . . . . . . .

Table 3: The Trithoff array.

Here are some properties of the Trithoff array.

In the Trithoff array, the numbers in columns with index equaling 1, 2, or 3 mod 3 are the positions of letters a, b, and c in the Tribonacci word, respectively.

We denote the element in row i and column j as T_{i,j}. In particular, the first row is a shifted Tribonacci sequence: T_{1,k} = T_{k+3}.

We call the sequences that follow the Tribonacci rule Tribonacci-like sequences. In addition, similar to extraFibs, we call integer sequences that follow the Tribonacci rule and end in positive integers extraTrib series or extraTribs.

It is well-known that every extraTrib can be expressed through Tribonacci numbers. For example, consider an extraTrib sequence S_{n}, where S_{0} = x, S_{1} = y, and S_{2} = z. Then we have

S_{n} = xT_{n−1} + y(T_{n+1} − T_{n}) + zT_{n}.

This allows one to derive many formulae connecting the values of different rows. For example • T_{2,n} = T_{1,n} + T_{1,n+1} = T_{1,n+3} − T_{1,n+2} = T_{1,n+2} − T_{1,n−1},

• T_{3,n} = T_{2,n−1} + T_{2,n} = T_{2,n+1} − T_{2,n−2} = T_{1,n} + T_{1,n+2} = T_{n−1} + 2T_{n} + T_{n+1}.

Column 1 is sequence \underline{A003265}:

1, 3, 5, 8, 10, 12, 14, 16, 18, 21, 23, 25, 27, 29, 32, 34, 36, 38, 40, ….

We can estimate the growth rate of this sequence. Each next term is either 2 or 3 more than the previous term.

Proposition 6. The ratio of a number to its index in sequence \underline{A003265} above approaches

\frac{α^{2} + 1}{2} = \frac{α}{α − 1}

as the index approaches infinity.

The ratio in the proposition above is the inverse of the proportion of numbers below n whose Tribonacci expansions end in 1, as n approaches infinity.

Proof. We want to see how many numbers that are less than n end with a 1 in their Tribonacci representation. These numbers are either in the form of w011 or w01. Suppose a is the number with Tribonacci representation w. Then (out(out(out(a))) + 3)_{T} = w011 and (out(out(a)) + 1)_{T} = w01. Let us call the numbers of the form w011 type 1 and the numbers of the form w01 type 2.

Suppose \underline{A003265}(r) = n, or equivalently, the value in column 1 and row r of the Trithoff array is n. This means that there are r numbers less than or equal to n with Tribonacci representations ending in 1, each of which is of either type 1 or type 2. From Fact 3T, we have

lim_{n→∞} \frac{out(n)}{n} = α.

For a type 1 number a, we have that α^{3}a+3 ≤ n, implying that the number of type 1 numbers approaches \frac{n}{α^{3}} when n approaches infinity. Similarly, the number of type 2 numbers when n approaches infinity is \frac{n}{α^{2}} . We now calculate that r = \frac{n}{α^{3}} + \frac{n}{α^{2}} when n approaches infinity. Equivalently, \frac{n}{r} = \frac{α^{3}}{α+1} = \frac{α}{α−1}, which proves the proposition.

Column 2 is a newly added sequence \underline{A353083}:

2, 6, 9, 15, 19, 22, 26, 30, 33, 39, 43, 46, 50, 53, 59, 63, 66, 70, ….

Given a sequence S_{i}, the difference sequence D_{i} is defined as D_{i} = S_{i+1} − S_{i}. We can see that the difference sequence of an extraTrib is an extraTrib.

Suppose a row starts with [a1]_{T}. What is the row number?

Let us first introduce a new base U, based on the second row of the array. Let us denote U_{i} = T_{2,i−2} = T_{i+1} − T_{i}. Suppose we consider a Tribonacci-like representation system based on the second row of the array. Then using this system, [… a_{4}a_{3}a_{2}a_{1}a_{0}]_{U} is equal to ⋯+a_{4}U_{4} +a_{3}U_{3} +a_{2}U_{2} +a_{1}U_{1} +a_{0}U_{0} = ⋯+6a_{4} +3a_{3} +2a_{2} +a_{1} +0a_{0}. Such representation is not unique, as a_{0} can change without changing the sum. Also, [1000]_{U} = [110]_{U} = 3. However, the point of this system is provided by the following lemma.

Lemma 7. If the row in Trithoff array starts with [a1]_{T}, then the row number is [a1]_{T} −[a]_{T} = 1 + [a1]_{U}.

Proof. Each row starts with a number whose Tribonacci representation ends in 1. There are [a1]_{T} total numbers not exceeding [a1]_{T}. Out of those, the numbers of the form [a0]_{T} correspond to numbers ending in zero, and there are exactly [a]_{T} of them. Therefore, the total number of numbers not exceeding [a1]_{T} and with Tribonacci representation ending in 1 is [a1]_{T} − [a]_{T} = 1 + [a0]_{T} − [a]_{T}. Using that U_{i} = T_{i+1} − T_{i}, we get that [a1]_{T} − [a]_{T} = 1 + [a0]_{U} = 1 + [a1]_{U} is the row number.

4.1 Rows of the Trithoff array and their difference sequences

The difference sequence of a Fibonacci-like sequence is again the same sequence with the index shifted by 1. In the Tribonacci case, the situation is more interesting.

The difference sequence of the first row of the Trithoff array is the second row. The difference sequence of the second row is the third row. The difference sequence of the third row is the seventh row. When we continue, we get the following sequence a(n), which is a newly added sequence \underline{A354215}. In this sequence, a(n + 1) is the row in the Trithoff array corresponding to the difference sequence of row a(n).

1, 2, 3, 7, 19, 29, 81, 125, 353, 161, 1545, 705, 2001, ….

The following proposition defines the difference sequence in terms of the Tribonacci representation of the given sequence.

Proposition 8. Given a Tribonacci representation a, the difference sequence of the row containing [a]_{T} contains [11 · a]_{T}, where the multiplication of two binary strings 11 and a is done in any integer base larger than 2.

Proof. We consider the difference sequences in terms of Tribonacci representation. First consider two large Tribonacci numbers: (T_{n})_{T} = 10^{n−3} and (T_{n+1})_{T} = 10^{n−2}. Then their difference is T_{n+1} − T_{n} = T_{n−2} + T_{n−1}. Thus, the Tribonacci representation of (T_{n+1} − T_{n})_{T} is (T_{n−2} + T_{n−1})_{T} = 110^{n−3}. By linearity, if we take the difference sequence of a row containing [a]_{T}, the result contains [11 · a]_{T}, where the multiplication is done in any integer base larger than 2.

For example, from row 1 containing 1, we get Tribonacci representation 11 · 1 = 11 evaluated to [11]_{T} = 3, which is in row 2. Then, multiplying 11 by 11, we get 121 evaluated to [121]_{T} = 9, which is in row 3. Row 3 starts with 5, with Tribonacci representation 101.

Repeating again, we multiply 101 by 11 to get 1111, which evaluates to 14, corresponding to row 7.

Given a sequence S_{i}, the partial-sums sequence P_{i} is sequence defined as P_{i} = ∑_{k=0}^{i} S_{k}. If a sequence has S_{i} as a difference sequence, then this sequence equals P_{i} plus a constant.

Before proving our next result, we want to describe possible parities of Tribonacci-like integer sequences. One can check that there are four possible cases:

• Type (EEEE): All terms are even (for example, row 7);

• Type (OOOO): All terms are odd (for example, row 3);

• Type (EOEO): The terms alternate (for example, row 2);

• Type (EEOO): The terms form a pattern of two even, then two odd (for example, row 1).

Theorem 9. Given an extraTrib S, there exists a unique Tribonacci-like sequence such that S is its difference sequence. This unique sequence is an extraTrib itself if and only if the given sequence does not belong to Type EEOO.

Proof. Take four adjacent terms a, b, c, a+b+c of an extraTrib sequence S. Then the partial sums are a, a + b, a + b + c, and 2a + 2b + 2c. To make the resulting sequence Tribonacci-like, we need to add a constant. The sum of the first three terms is 3a + 2b + c, so we need to add \frac{c−a}{2} to each term to make the fourth term the sum of the first three terms. Consider a Tribonacci-like sequence Q that starts with four consecutive entries

\frac{a + c}{2}, \frac{a + 2b + c}{2}, \frac{a + 2b + 3c}{2}, \frac{3a + 4b + 5c}{2}.

As Q follows the Tribonacci rule, its difference sequence follows the Tribonacci rule, and since the difference sequence agrees with S for three consecutive terms, it agrees with S everywhere.

But the new sequence Q, though it is Tribonacci-like, is not always an extraTrib, as it is not guaranteed to be an integer sequence. When we add \frac{c−a}{2} to the terms, the new terms are integers if and only if a and c have the same parity. Thus, extraTrib sequences of types EEEE, OOOO, and EOEO have partial sums for which a constant can be added to make it an ExtraTrib, while the sequences of Type EEOO do not.

We call an extraTrib S invertible if there exists an extraTrib with the difference sequence S. Equivalently, an extraTrib is invertible if it is of types EEEE, OOOO, or EOEO.

Testing the rows in the Trithoff array, we get the sequence of invertible rows, which is a newly added sequence \underline{A353178}:

2, 3, 4, 7, 11, 12, 16, 17, 19, 20, 21, 25, 26, 28, 29, 30, 33, 34, ….

Non-invertible rows are a newly added sequence \underline{A353193}:

1, 5, 6, 8, 9, 10, 13, 14, 15, 18, 22, 23, 24, 27, 31, 32, 36, 37, 39, ….

Interestingly, nothing of this sort appears in the Fibonacci case. As the difference sequence of a Fibonacci-like sequence is the sequence itself (shifted), we get that all extraFibs are invertible, as they invert to themselves. Theorem 10. If we start with an extraTrib and keep inverting it, we will get to a noninvertible sequence in a finite number of steps. Proof. We start by looking at how the difference operator changes types. Type EEOO changes to EOEO; the latter changes to OOOO, then to EEEE. The sequence of type EEEE stays EEEE.

Define the valuation of an extraTrib to be the largest integer n such that all numbers in the sequence are multiples of 2^{n}. An extraTrib of valuation n, after dividing by 2^{n}, is of the type OOOO, EOEO, or EEOO. Similar to before, the difference sequence of sequence 2^{n} times type EEOO is sequence 2^{n} times type EOEO. The latter changes to 2^{n} times type OOOO, and the difference of that has valuation m > n. After taking at most three difference operators, the result has a greater valuation than the starting sequence. Thus, for every three inverse differences, the valuation decreases, and the result follows.

4.2 The difference sequence for the first column

Consider the first column (sequence \underline{A003265}):

1, 3, 5, 8, 10, 12, 14, 16, 18, 21, 23, 25, 27, 29, 32, 34, 36, 38, 40, …,

and its difference sequence:

2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, …,

We can notice that the difference sequence of the first column consists of twos and threes, which we prove in the next proposition. Proposition 11. We have that T_{i+1,1} − T_{i,1} is either 2 or 3. Moreover, T_{i+1,1} − T_{i,1} = 3 if and only if i is in sequence \underline{A305373}. Proof. Consider a number a in the first column. Looking at its Tribonacci representation that must end in a 1, consider cases b001, b011, b0101, and b01101.

If [a]_{T} = b0101, then the next term in column 1 will be |b1001| = [b0101]_{T} + 3 = a + 3, so the difference is 3.

For other possibilities, b001, b011, and b01101, the next terms are b011, |b101|, and |b10001| correspondingly. In all these cases, the next term is increased by 2.

The indices of the rows such that the next value in the first column is 3 greater correspond to rows starting with numbers of the form [b0101]_{T}. The row number is [b0101]_{T} − [b010]_{T} by Lemma 7. This equals out(b) + out^{2}(b) + 3. Sequence \underline{A305373} is defined as the sum of \underline{A003144} and \underline{A003145}. \underline{A003144} is the sequence [x0]_{T} + 1 and \underline{A003145} is the sequence [x01]_{T} + 1. Thus, their sum is out(x) + out^{2}(x) + 3. Thus, our sequence is \underline{A305373}.

5 Extending the Trithoff array. Precolumns

We extend the Trithoff array to the left by using the rule that in every row, each number is the sum of the three previous numbers. We assume that the columns of the Trithoff array start with index 1. Similar to Conway and Ryba [2], we call the 0th column the wall, column −1, the seed, and column −2, the pre-seed. Table 4 shows the upper-left part of the Trithoff array with precolumns.

i = −2 (pre-seed) i = −1 (seed) i = 0 (wall) i = 1 i = 2 i = 3 i = 4
0  0  1  1  2  4  7
0  1  2  3  6  11  20
1  1  3  5  9  17  31
1  2  5  8  15  28  51
1  3  6  10  19  35  64
2  3  7  12  22  41  75

Table 4: Trithoff array with precolumns.

Before describing precolumns, we need to extend the notion of the Tribonacci representations to allow for three consecutive ones.

We call the standard Tribonacci representation of number n canonical. We call a representation of a number n in the Tribonacci base a non-canonical Tribonacci representation if it evaluates to n and consists of integers zero and one, but might contain three consecutive ones. For example, suppose n = 13. Then its canonical representation is 10000. While a non-canonical word 1110 also evaluates to 13. Similar to Conway and Ryba [2], we denote by |v| the canonization of a non-canonical representation v.

Suppose we have a non-canonical Tribonacci representation of the number n. We can view this representation as a sum of distinct Tribonacci numbers. We call replacing T_{n−2}+T_{n−1}+T_{n} in this sum with T_{n+1} carrying.

Here we describe the canonization of a non-canonical representation. Suppose we have a non-canonical representation v of number n. We find the leftmost occurrence of three ones and apply carrying. In other words, we replace the leftmost 0111 with 1000. This way, the new representation contains only digits zero and one and evaluates to the same number n, while the sum of digits decreases. That means the procedure terminates in a canonical representation of n.

Lemma 12. Suppose a binary word w is a non-canonical representation of integer n, then w0 is a non-canonical representation of out(n).

Proof. Consider a canonization procedure described above for binary words w and w0. Each step of this procedure is the same, except we have 0 at the end of the second word. Thus |w0| = |w|0 = (n)_{T} 0 = (out(n))_{T}.

Now we are ready to describe the Tribonacci representation of precolumns, given the Tribonacci representation of the first column.

Lemma 13. Suppose number n in column 1 has the Tribonacci representation abc1, where b and c are digits zero or one, and a is a binary word. Then the wall w in the same row equals [abc]_{T} + 1, the seed in the same row equals [ab]_{T} + c, and the pre-seed in the same row equals [a]_{T} + b.

Proof. We have (out(n))_{T} = abc10 and (out(out(n)))_{T} = abc100. By definition, the corresponding wall element w is out(out(n)) − out(n) − n. We can split n as [abc0]_{T} + 1, out(n) as [abc00]_{T} + 2 and out(out(n)) as [abc000]_{T} + 4. Then w = ([abc000]_{T} + 4) − ([abc00]_{T} + 2) − ([abc0]_{T} + 1) = ([abc000]_{T} − [abc00]_{T} − [abc0]_{T}) + 1 = [abc]_{T} + 1.

The seed s equals out(n) − n − w = [abc10]_{T} − [abc1]_{T} − [abc]_{T} − 1 = ([ab000]_{T} + 4c + 2) − ([ab00]_{T} + 2c + 1) − ([ab0]_{T} + c) − 1 = ([ab000]_{T} − [ab00]_{T} − [ab0]_{T}) + c = [ab]_{T} + c.

The pre-seed p equals n − w − s = [abc1]_{T} − ([abc]_{T} + 1) − ([ab]_{T} + c) = ([a000]_{T} + 4b + 2c + 1) − ([a00]_{T} + 2b + c + 1) − ([a0]_{T} + b + c) = ([a000]_{T} − [a00]_{T} − [a0]_{T}) + b = [a]_{T} + b.

Analogs for our case for the structure of the Tribonacci Garden State of Facts 5T describe how the next term to the right depends on the previous term.

Fact 5Ta. A garden term n is followed by out(n).

This is true by definition.

Fact 5Tc. A wall term w is followed by out(w) − 1.

Proof. Suppose the wall term w is followed by the garden term n. Suppose the Tribonacci representation of n is abc1. Then from Lemma 13 we have w = [abc]_{T} + 1. Thus, n = out(w − 1) + 1.

We consider cases as we can assume that b and c are not both 1.

• If bc is 00, then out(w)−1 = out([abc]_{T} +1)−1 = out([a00]_{T} +1)−1 = out([a01]_{T})−1 = [a010]_{T} − 1 = [a001]_{T} = [abc1]_{T}.

• If bc is 01, then out(w)−1 = out([abc]_{T} +1)−1 = out([a01]_{T} +1)−1 = out([a10]_{T})−1. The representation [a10]_{T} might be non-canonical, so by Lemma 12 out(w) − 1 = [a100]_{T} − 1 = [a011]_{T} = [abc1]_{T}.

• If bc is 10, then out(w)−1 = out([abc]_{T} +1)−1 = out([a10]_{T} +1)−1 = out([a11]_{T})−1. Again [a11]_{T} might be a non-canonical representation, and by Lemma 12 we have out([a11]_{T}) − 1 = [a110]_{T} − 1 = [a101]_{T} = [abc1]_{T}.

So w is always followed by out(w) − 1.

The analog of Fact 5b describes how to calculate the seed from the pre-seed and the wall from the seed in the same row. The formulae depend on the last digits of the Tribonacci representation of the first garden term in the same row. Consider row x, where we denote the pre-seed by p(x), the seed by s(x), the wall term as w(x), and the first garden term as g(x).

Fact 5Tb. If (g(x))_{T} ends with 11, then w(x) = out(s(x)) and s(x) = out(p(x)) + 1. If (g(x))_{T} ends in 001, then w(x) = out(s(x)) + 1 and s(x) = out(p(x)). If (g(x))_{T} ends in 101, then w(x) = out(s(x)) + 1 and s(x) = out(p(x)) − 1.

Proof. We use Lemma 13 that states that if (g(x))_{T} = abc1, then w(x) = [abc]_{T} + 1, s(x) = [ab]_{T} + c, and p(x) = [a]_{T} + b.

If (g(x))_{T} ends with 11, then b = 0 and c = 1. We have w(x) = [a01]_{T} + 1 = [a10]_{T} and s(x) = [a0]_{T} +1 = [a1]_{T}. The representation [a1]_{T} might be non-canonical, but it still respects the out function. Thus, in this case, w(x) = out(s(x)). We also have p(x) = [a]_{T} + 0 = [a]_{T}, so s(x) = out(p(x)) + 1.

If (g(x))_{T} ends in 01, then c = 0. Thus, w(x) = [ab0]_{T} + 1 and s(x) = [ab]_{T} + 0 = [ab]_{T}, and therefore w(x) = out(s(x)) + 1.

If (g(x))_{T} ends in 001, then b = c = 0. Thus, s(x) = [a0]_{T} + 0 = [a0]_{T} and p(x) = [a]_{T} + 0 = [a]_{T}, and therefore s(x) = out(p(x)).

If (g(x))_{T} ends in 101, then b = 1 and c = 0, so s(x) = [a1]_{T} + 0 = [a0]_{T} + 1 and p(x) = [a]_{T} + 1. To prove that [a0]_{T} + 1 = out([a]_{T} + 1) − 1 we must consider two cases. If a ends in 0, then adding 1 might result in a non-canonical representation, but we still can take the successor. In this case, out(p(x)) = out([a]_{T} + 1) = [a0]_{T} + 2 = s(x) + 1, so the lemma holds. If a ends in 1, it must end in 01; otherwise, the representation of (g(x))_{T} would not be canonical. Let a = d01 for some binary string d. Then [a]_{T} + 1 = [d01]_{T} + 1 = [d10]_{T}. Again, d10 might not be canonical. In any case, out(p(x)) = out([a]_{T} + 1) = out([d10]_{T}) = [d100]_{T} = out([d01]_{T}) + 2 = out([a]_{T}) + 2 = s(x) + 1, and the lemma still holds.

5.1 Precolumns

The following theorem describes precolumns in terms of the Tribonacci word.

Theorem 14. The wall, the seed, and the pre-seed can be described as follows.

• The wall is an increasing sequence of numbers that are positions of letters a and b in the Tribonacci word.

• The seed is a non-decreasing sequence, starting with 0 followed by all integers, where the positions of letter a in the Tribonacci word are doubled, and all the other integers are not doubled.

• The pre-seed forms a non-decreasing sequence, starting with two zeros followed by all integers, where the positions of letters a and b in the Tribonacci word are tripled, while the positions of letters c are doubled.

Proof. Consider a term x in the first column of the Trithoff array in the form [abc1]_{T}. By Lemma 13, the wall w in the same row equals [abc]_{T} + 1, the seed in the same row equals [ab]_{T} + c, and the pre-seed in the same row equals [a]_{T} + b.

We start with the wall. The word abc goes, in order, through all Tribonacci representations ending in 0 or 01. Thus, the wall term goes in order through numbers that are one greater than numbers with Tribonacci representations ending in 0 or 01. So by Theorem 1, the wall term will go through all positions of the letters a and b in the Tribonacci word.

We continue with the seed. Consider how it changes when moving to the previous row. Suppose b = 0 and c = 1. Then the first column term x for that row is [a011]_{T}, and the

corresponding seed is [a0]_{T} + 1, matching a position of letter a in the Tribonacci word. The previous row has the garden term [a001]_{T}, and the corresponding seed equals [a0]_{T}. Thus, the seed increases by 1 from the previous row.

Suppose b = 1 and c = 0. Then x = [a101]_{T}, and the corresponding seed is [a1]_{T}, matching a position of letter a in the Tribonacci word. The previous row has garden term [a011]_{T}, and the corresponding seed is [a0]_{T} + 1 = [a1]_{T}. Thus, this row’s seed equals the previous seed.

Suppose b = c = 0. Then x = [a001]_{T}, and the corresponding seed is [a0]_{T}, which matches a position of letter b or c in the Tribonacci word. Suppose a′ is the Tribonacci representation of [a]_{T} − 1. The previous row has garden term [a′101]_{T} or [a′011]_{T} with the same corresponding seed [a′1]_{T} or [a′0]_{T} + 1, which is less than the current seed [a0]_{T} by 1.

To summarize, a row’s seed equals the previous seed when b = 1 and c = 0; otherwise, the row’s seed is one greater than the previous seed. Thus, only the positions of the letter a in the Tribonacci word are doubled.

We finish with the pre-seed. The pre-seeds are non-decreasing because as [abc1]_{T} increases, [a]_{T} + b either remains the same or increases by 1.

The number [a]_{T} appears at least twice as a pre-seed: in rows with the garden value equal [a001]_{T} or [a011]_{T}.

The other possible values for the first column are [a101]_{T} where a does not end in two 1s, and the corresponding pre-seed is [a]_{T} + 1. If [a]_{T} = x0, for some prefix x, then such pre-seed has the possibly non-canonical representation [x1]_{T}, so its canonical representation has the number of trailing zeroes equal to 0 mod 3 and if [a]_{T} = x01 then such pre-seed has the possibly non-canonical representation [x10]_{T}, which has a canonical representation with a number of trailing zeroes equal to 1 mod 3. These extra values are indices of a and b in the Tribonacci word.

Column 0, the wall, is a newly added sequence \underline{A353084}:

1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, ….

Column −1, the seed, is a newly added sequence \underline{A353086}:

0, 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 10, …,

The numbers that are not doubled in the seed form a newly added sequence \underline{A351631}:

0, 2, 4, 6, 9, 11, 13, 15, 17, 19, 22, 24, 26, 28, 30, 33, 35, ….

Column −2, the pre-seed, is a newly added sequence \underline{A353090}:

0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, ….

5.2 Fact 6

We can combine the results in this section into the following analog of Fact 6.

Fact 6T. Each positive integer appears once in the Trithoff array. In addition, positions of a in the Tribonacci word appear 1 time in the wall, 2 times in the seed, and 3 times in the pre-seed. Positions of b in the Tribonacci word appear 1 time in the wall, 1 time in the seed, and 3 times in the pre-seed. Positions of c in the Tribonacci word appear 0 times in the wall, 1 time in the seed, and 2 times in the pre-seed.

6 ExtraTribs and their multiples

According to Fact 7 from Conway-Ryba paper [2], every series that satisfies Fibonacci’s rule and is eventually positive is represented in the Garden State. Namely, every extraFib has a tail that is a row in the Wythoff array. We want to generalize this to extraTribs.

As an example, consider the sequence that is twice the Tribonacci numbers: 0, 0, 2, 2, 4, 14, 26, 48, and so on. The first few terms can be found in the first row of the Trithoff array. The tail, starting from 14, 26, and 48, is the seventh row of the Trithoff array.

To help us deal with extraTribs, we need to deal with improper Tribonacci representations discussed below.

6.1 Improper Tribonacci representation and its canonization

We call a Tribonacci representation improper if it uses digits other than zero and one. To emphasize the difference, we call a canonical or a non-canonical representation (aka representations that use only ones and zeros) proper. Suppose a word v is an improper Tribonacci representation of integer n. As before, we denote by |v| the canonization of the word v, aka the canonical Tribonacci representation of n. In other words, |v| = (n)_{T}. An example of an improper representation of 13 is 1030, and its canonization is 10000.

Suppose we have an improper Tribonacci representation of number n, which is a linear combination of Tribonacci numbers. Recall that we call replacing T_{n−2} + T_{n−1} + T_{n} with T_{n+1} carrying. We call replacing T_{n+1} with T_{n−2} + T_{n−1} + T_{n} reverse carrying. In terms of a Tribonacci representation of n, carrying replaces dabc with (d + 1)(a − 1)(b − 1)(c − 1) for a, b, c > 0, while reverse carrying replaces dabc with (d − 1)(a + 1)(b + 1)(c + 1) for d > 0.

Our goal in this section is to introduce the canonization procedure that, given enough zeros at the end of a Tribonacci representation, converts an improper representation of some number to a canonical representation of the same number in a finite number of steps.

We call the position (index) of the leftmost digit that is greater than 1 in an improper representation w the improper boundary index and the value at this position the improper boundary value. Next, we define the weight of w to be the sum of all digits in w that are to the right from the last 0 preceding the improper boundary.

We look at the word w from left to right, where we can assume that w is padded with zeros on the left if needed.

Lemma 15. Leftmost carrying does not move the improper boundary index to the left and does not increase the weight.

Proof. Leftmost carrying replaces 0abc with 1(a − 1)(b − 1)(c − 1), where a, b, c > 0. Thus, the boundary does not move to the left. If leftmost carrying acts on digits to the left of the 0 preceding the boundary, then it does not change the weight; if not, it decreases it.

Consider the following procedure acting on an improper representation of a number, which we call the Canonization procedure:

• Step 1. Use leftmost carrying when possible. This procedure ensures that the longest prefix of the word w that contains only 0’s and 1’s is in canonical form. For the following steps, we can always assume that no three consecutive digits are greater than 0.

• Step 2. When step 1 is not available, work on the leftmost improper boundary a. There are two cases of what we do depending on what is before a: 0 or 01.

– Step 2a. Replace 0abcd with 1(a − 2)bc(d + 1). This is a combination of reverse carrying (replacing 0abcd with 0(a−1)(b+1)(c+1)(d+1)) and carrying (replacing 0(a − 1)(b + 1)(c + 1)(d + 1) with 1(a − 2)bc(d + 1)).

– Step 2b. Replace 01a0cd with 10(a − 2)0(c + 1)(d + 1). This is a combination of reverse carrying (replacing 01a0cd with 01(a − 1)1(c + 1)(d + 1)) and carrying (replacing 01(a − 1)1(c + 1)(d + 1) with 10(a − 2)0(c + 1)(d + 1)).

These operations are not defined when a is one of the last three digits of a number. If the procedure on the word w′ ends with a canonical word w, we call the w the canonization of w′: w = |w′|. If d is an integer, we write the string consisting of m copies of d as d^{m}.

Note that when our presentation is non-canonical but proper, we only need Step 1.

Theorem 16. Given an improper representation w of an integer n with weight m ending in at least 3m zeros, the canonization procedure applied to w terminates in the finite number of steps.

Proof. Each of the steps in canonization does not change the value of the number while making it lexicographically larger. In addition, Step 1 decreases the sum of digits of the Tribonacci representation, while both Steps 2a and 2b do not change the sum of the digits.

Now, we look at the weight. Step 1 does not increase the weight. Step 2b decreases the weight. Next, we look at Step 2a. If a > 3, then Step 2a does not change the weight, but the next operation has to be either Step 1 or Step 2b, both of which decrease the weight. If a = 3, then Step 2a replaces 03bcd with 11bc(d + 1). If b = 0, the boundary moves, and the weight decreases; if b > 0, we perform Step 1, which decreases the weight. If a = 2, then Step 2a replaces 02bcd with 10bc(d + 1), and the weight decreases.

Step 1 does not change the number of trailing zeros while increasing the lexicographical order. Moreover, the digits of the improper representation of a number x cannot exceed x. It follows that we can only make a finite number of such steps in a row. The total number of times Step 2 runs is also finite as Steps 2b decrease the weight, and each Step 2a is followed by steps decreasing the weight.

Now we estimate the number of trailing zeros that we need. Notice that though Step 2a might not decrease the weight, as soon as the boundary moves, the weight is decreased. For every operation in Step 2, we need three digits after the boundary to be available. It follows that it is enough to have 3m trailing zeros.

The canonization procedure for the word w uses a fixed number of zeros. If we add more zeros to the end of w, the procedure will still be the same.

Corollary 17. If the canonization procedure above for an improper representation w of number n terminates in the canonical Tribonacci representation |w|, then the same procedure for w0^{k} terminates in |w|0^{k}.

6.2 ExtraTribs

Consider an extraTrib S_{n} that starts with non-negative numbers a, b, and c, that is S_{0} = a, S_{1} = b, and S_{2} = c. Then S_{n} is a linear combination of three sequences:

• A sequence that starts as 1, 0, 0. This sequence continues as 1, 1, 2, and can be described as a shifted Tribonacci sequence T_{n−1}.

• A sequence that starts as 0, 1, 0. This sequence continues as 1, 2, 3, 6, and so on. It is the second row of the Trithoff array and can be represented as the sequence T_{n} + T_{n+1}.

• A sequence that starts as 0, 0, 1, which is the Tribonacci sequence T_{n}.

Thus,

S_{n} = aT_{n−1} + b(T_{n} + T_{n+1}) + cT_{n} = aT_{n−1} + (b + c)T_{n} + bT_{n+1}.

Fact 7T. Any extraTrib sequence has a tail appearing in the array.

Proof. Suppose we are given an extraTrib sequence S_{n}. Its terms can be expressed as a positive integer linear combination of shifted Tribonacci sequences: S_{n} = aT_{n−1} + (b + c)T_{n} + bT_{n+1}. Thus, for n > 3, the term S_{n} has an improper Tribonacci representation b(b + c)a0^{n−4}. By Theorem 16, there exists N_{0}, such that the canonization procedure for the word b(b + c)a0^{N_{0}−4} terminates in a word w. By Corollary 17 for any number N ≥ N_{0}, we have (S_{n})_{T} = w0^{N−N_{0}}. Thus, all these numbers are in the same row of the Trithoff array.

6.3 Multiples of Tribonacci sequences in the array

According to Fact 8, any positive multiple of an extraFibs is an extraFib. It immediately generalizes to Fact 8T.

Fact 8T. Any positive multiple of an extraTribs is an extraTribs.

Thus, any multiple of an extraTribs appears in the Trithoff array.

We wrote a program to calculate multiples of the Tribonacci numbers and find them in the Trithoff array. This data is summarized in Table 5. The first row is the multiple coefficient. The next row of the table is the row of the array where the tail of the nth multiple appears. The third row of the table is the value of the first column of that row in the array. The last row of the table is the third row divided by the first row.

multiple 1 2 3 4 5 6 7 8  9  10 11 12 …
row #  1 7 10 81 101 121 141 161 1126 1251 1376 1501 …
first column 1 14 21 176 220 264 308 352 2466 2740 3014 3288 …
Trib #  1 7 7 44 44 44 44 44 274 274 274 274 …

Table 5: Tribonacci multiples.

The sequence of row numbers is a newly added sequence \underline{A351685}:

1, 7, 10, 81, 101, 121, 141, 161, 1126, 1251, 1376, 1501, 1626, 1751, ….

The numbers that start off the rows that are multiples of the Tribonacci sequence us a newly added sequence \underline{A351689}:

1, 14, 21, 176, 220, 264, 308, 352, 2466, 2740, 3014, 3288, 3562, ….

Notice that this sequence contains runs of arithmetic progressions. For example, numbers 176, 220, 264, 308, and 352 form an arithmetic progression with a difference of 44. Correspondingly, number 44 appears 5 times in row 4 of Table 5. The next 13 numbers form an arithmetic progression with a difference of 274. The next 27 numbers form an arithmetic progression with a difference of 1705.

6.4 Order of multiples

Fact 9 states that multiples of any extraFib series appear in order in the Wythoff array.

Fact 9T. Multiples of extraTribs appear in order in the Trithoff array.

Proof. Let the sequence in the array be S_{n}. Suppose we found kS_{n} in the array. If it requires m trailing zeroes to canonize, then the first term in the Trithoff array corresponding to kS_{n} starts with the canonization of kS_{m+1}, as S_{m+1} is the smallest term in the array S_{n} which has m zeros. Now we want to canonize (k + 1)S_{n} = kS_{n} + S_{n}. First, canonizing kS_{n} requires m trailing zeroes, then adding S_{n} requires a total of m′ ≥ m zeroes because the process never moves the rightmost digit leftwards. So the sequence (k + 1)S_{n} starts at (k + 1)S_{m′} ≥ (k + 1)S_{m} > kS_{m} and thus, it appears later.

The exact same argument proves that the sequence A + B appears after sequences A and B.

The sequence a(n), where a(n) is the row number in the Wythoff array that is n times the Fibonacci sequence is \underline{A269725}. The similar sequence for Lucas numbers is \underline{A269726}.

6.5 Row numbers for multiples

Theorem 18. When all the numbers in an extraTrib are divisible by n, the row number of the extraTrib in the Trithoff array is 1 modulo n.

Proof. Consider an extraTrib S with all terms divisible by n. After dividing by n, we get another extraTrib that is a row in the Trithoff array. Suppose its element in the first column is p. Then the sequence S must contain an element np. Consider the Tribonacci representation v = (p)_{T} and an improper word w, where we replace every digit one in the word v with n. Suppose the improper word w requires adding exactly z trailing zeroes to canonize. Thus, the row for sequence S starts with [|w0^{z}|]_{T}. The canonization procedure depends on the rule for the Tribonacci-like sequences but not on the sequences themselves. Thus, the canonization steps are identical for bases T and U. By Lemma 7, the row number is 1 + [|w0^{z}|]_{U} = 1 + n[v0^{z}]_{U}. This is 1 plus a multiple of n.

For example, consider the Tribonacci sequence and its multiples. Suppose that some range of values of n needs the same number of zeros z to get canonized. In other words, for this range, the canonization of n0^{z} ends in 1. That means the first column of the row that is the nth multiple of the Tribonacci sequence equals nT_{n+2+z}. Thus, for this range, the elements in the first column form an arithmetic progression with difference T_{n+2+z}, and row numbers form an arithmetic progression with difference T_{n+2+z} − T_{n+1+z}.

6.6 How to find the extraTribs in the garden

Given an extraTrib, how can we locate it in the array? We can do this by computing the outs of each term. From Fact 5T, when n is the wall, out(n) − 1 is the term after n, and it is the last term that does so. Moreover, suppose we have three consecutive terms of an extraTrib that are m, out(m), and out^{2}(m). Then n + out(n) + out^{2}(n) = out^{3}(n), it follows that the next terms is out^{3}(n) and so on.

Thus to find the wall term in an extraTrib, it is enough to locate a term n, such that the next term is m = out(n) − 1, and the next two terms are out(m) and out^{2}(m).

6.7 Extending to the left

Let us extend the Fibonacci sequence to the left:

…, −8, 5, −3, 2, −1, 1, 0, 1, 1, 2.

We see that the signs on the left alternate.

Note that any extraFib series extended to the left has a similar pattern. The signs on the left alternate, and the absolute values moving to the left form an extraFib (see [2]).

Going backward through the Tribonacci sequence gives 1, 0, 0, 1, −1, 0, 2, −3, 1, 4, −8, 5, 7, −20, 18, 9, −47, 56, 0, −103, 159, −56, −206, 421, −271, etc. We see that the signs do not form a nice pattern, and the absolute values do not form an extraTrib.

Lemma 19. When extending an extraTrib to the left, we have to reach a negative number. After that, no three consecutive numbers to the left of it can have the same sign.

Proof. First, we prove that when extending an extraTrib sequence to the left, we always reach a negative number. Assume this is false, and there exists such an extraTrib whose elements are all non-negative. It follows that the sequence is non-decreasing as for any k, we have T_{k} = T_{k−1} +T_{k−2} +T_{k−3} ≥ T_{k−1}. It follows that the sequence does not contain zeros and is actually monotonically increasing. There is a finite number of non-negative integers less than any given non-negative integer, but there are no bounds on the index moving to the left, so as we move to the left in an extraTrib sequence, we must, at some point, encounter a negative element.

Suppose T_{k} < 0. Let T_{n}, T_{n−1}, and T_{n−2} for n < k be all positive. This means that T_{n+1} = T_{n} + T_{n−1} + T_{n−2} > 0. By continuing, we see that for all j > n, we have T_{j} > 0, contradicting that T_{k} < 0.

Let T_{n}, T_{n−1}, and T_{n−2} for n < k be all negative. This means that T_{n+1} = T_{n} + T_{n−1} + T_{n−2} < 0. By continuing, we see that for all j > n, we have T_{j} < 0, contradicting the fact that this is an extraTrib.

6.8 Reversal

In a similar manner as Conway and Ryba [2], we can define the reversal of an extraTrib series, the series where we change the index n to −n and replace the numbers with their absolute values. The following proposition is a negation of Fact 10.

Theorem 20. The reversal of an extraTrib is not an extraTrib.

Proof. We use the fact from Lemma 19 that no three consecutive terms of an extraTrib can be all positive or all negative once the term index is below some constant i_{0}.

Moreover, for the reversal of the extraTrib series to be an extraTrib, we can assume that the terms to the left of some index constant i_{0} increase in absolute value. Let the absolute values of some four consecutive terms A, B, C, D to the left of i_{0} be a, b, c, and d. By our assumptions,

a > b > c > d.

Now consider the signs of A, B, C, and D. Without loss of generality, we can assume that the sign for A is positive. As no three consecutive terms have the same sign, there are 5 cases for the distribution of signs: + + −+, + + −−, + − ++, + − +−, and + − −+. We have that A+B +C = D. Thus, we get the following equations: a+b−c = d, a+b−c = −d, a − b + c = d, a − b + c = −d, and a − b − c = d. Or equivalently, a + b = c + d, a + b + d = c, a + c = b + d, a + c + d = b, and a = b + c + d.

Given that a > b > c > d, we can exclude the first four cases. We are left with the case of four consecutive numbers: a, −b, −c, and d. Consider the number to the left of a. On the one hand, it has to equal −c − (−b) − a = b − c − a. On the other hand, its absolute value has to be a + b + c. We get a contradiction.

7 Fib/Trib binary/ternary numbers

While generalizing the Wythoff array to Tribonacci numbers, we discovered many interesting sequences, which are discussed above. In this section, we cover several additional sequences related to the Fibonacci and Tribonacci sequences.

7.1 Definitions

The sequence of Fibbinary numbers (\underline{A003714}) is defined as numbers whose binary representation contains no two adjacent ones. In other words, the Fibbinary numbers can be formed by writing the Zeckendorf representations of natural numbers and then evaluating the result in binary:

0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, 36, 37, 40, ….

Analogously, we define the Tribbinary numbers as those numbers whose binary representation has no three consecutive ones. The sequence of Tribbinary numbers can be constructed by writing out the Tribonacci representations of non-negative integers and then evaluating the result in binary. This is sequence \underline{A003726}:

0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 16, 17, …

Now, we would like to introduce two more sequences related to base 3 rather than base 2. We define Fibternary numbers as numbers whose ternary representations consist only of

zeros and ones and do not have two consecutive ones. The sequence of Fibternary numbers can be constructed by writing out the Zeckendorf representations of non-negative integers and then evaluating the result in ternary. This is sequence \underline{A060140}:

0, 1, 3, 9, 10, 27, 28, 30, 81, 82, 84, 90, 91, 243, 244, ….

These are Fibbinary numbers written in base 2, then evaluated in base 3.

We define Tribternary numbers as numbers whose ternary representations consist only of zeros and ones and do not have three consecutive ones. The sequence of Tribternary numbers can be constructed by writing out the Tribonacci representations of non-negative integers and then evaluating the result in ternary. This is a newly added sequence \underline{A356823}: These are Tribbinary numbers written in base 2, then evaluated in base 3.

Much is known about Fibbinary numbers and can be easily generalized to the other three sequences.

7.2 Powers of 2 and 3

The number of Fibbinary numbers less than any power of two is a Fibonacci number. It is easy to prove that the number of Tribbinary numbers less than any power of two is a Tribonacci number. Similarly, the number of Fibternary(Tribternary) numbers less than any power of three is a Fibonacci(Tribonacci) number.

7.3 Recursive generation

We can generate all these four sequences (\underline{A003714}, \underline{A003726}, \underline{A060140}, \underline{A356823}) recursively. Start by adding 0 to the sequence. Then, if x is a number in the sequence, add the following numbers to the sequence (ignoring repeated zeros):

• 2x and 4x + 1, for Fibbinary;

• 2x, 4x + 1, and 8x + 3, for Tribbinary;

• 3x and 9x + 1, for Fibternary;

• 3x, 9x + 1, and 27x + 4, for Tribternary;

7.4 Fibonacci(Tribonacci) word

The Fibbinary numbers have the property that the nth Fibbinary number is even if the nth term of the Fibonacci word is a. Respectively, the nth Fibbinary number is odd (of the form 4x + 1) if the nth term of the Fibonacci word is b.

Similarly, the nth Fibternary number is of the form 3x (correspondingly 9x + 1) if nth term of the Fibonacci word is a (correspondingly b) (see comment in the OEIS for \underline{A060140}).

Similarly, the nth Tribbinary number is even if the nth term of the Tribonacci word is a. Respectively, the nth Tribbinary number is of the form 4x + 1 if the nth term of the Tribonacci word is b, and the nth Tribbinary number is of the form 8x + 3 if the nth term of the Tribonacci word is c. This follows from Theorem 1 (see [4]).

Similarly, the nth Tribternary number is divisible by 3 if the nth term of the Tribonacci word is a. Respectively, the nth Tribbinary number is of the form 9x + 1 if nth term of the Tribonacci word is b, and the nth Tribbinary number is of the form 27x + 4 if nth term of the Tribonacci word is c.

7.5 Sums

It is known and can be easily checked, that every non-negative integer can be written as the sum of two Fibbinary numbers. As Fibbinary numbers are a subset of Tribbinary numbers, we get that every non-negative integer can be written as the sum of two Tribbinary numbers. Here is the analog for Fibternary and Tribternary numbers.

Proposition 21. Every non-negative integer can be written as a sum of four Fibternary numbers or as a sum of three Tribternary numbers.

Proof. We start with Fibternary numbers. Suppose the base-3 representation of integer n has k digits. Consider two k-digit Fibternary numbers of the form 101010 … in base 3 and another two k-digit numbers of the form 010101 . . .. We can add these four numbers to get the k-digit number N written as 222222 … in base 3. We can get to our number n by subtracting one or two in some digit placements. We can distribute these subtractions between our four numbers by replacing some ones with zeros in them. The four numbers will remain Fibternary and will sum up to n.

We continue with Tribternary numbers. Suppose the base-3 representation of integer n has k digits. Consider three special numbers in base 3, all of them consisting of zeros and ones. The first number has zeros in digit places divisible by 3, the second number in digit places that have remainder 1 when divided by three, and the third number in digit places that have remainder 2 when divided by 3. These three numbers sum up to a number with k digits in base three, all equal to 2. Suppose our number n in base 3 has the digit 1 in some place. Then we can remove a 1 from one of the two special numbers that have a 1 in the same place. Suppose our number (n)_{3} has the digit 0 in some place. Then we can remove a 1 from both of the two special numbers with a 1 in the same place. When all digits are adjusted, we will have three numbers that sum to n, and all of them have every third digit as zero. Thus, all of them are Tribonacci representations of some numbers.

7.6 Multiples

Every number has a Fibbinary multiple. The proof is available in the sequence \underline{A300867} entry in the OEIS [6]. Our generalization is in the next proposition.

Proposition 22. Every number has a Fibternary multiple.

Proof. Let a(k) = \frac{9^{k}−1}{8}, and then for any n, the pigeonhole principle implies there are i ≠ j such that a(i) ≡ a(j) (mod n), making a(i) − a(j) a multiple of n.

In addition,

9^{k} − 1 = \overbrace{888 … 8}^{k 8’s}_{9},

so

a(k) = \overbrace{111 … 1}^{k 1’s}_{9}.

Then

a(i) − a(j) = \overbrace{111 … 1}^{i−j 1’s} \overbrace{000 … 0}^{j 0’s}_{9} = \overbrace{010101 … 01}^{i−j 01’s} \overbrace{000 … 0}^{2j 0’s}_{3}.

This means that a(i) − a(j) is actually Fibternary.

As every Fibbinary number is also Tribbinary and every Fibternary number is also Tribternary, we have the following corollary.

Corollary 23. Every number has a Tribbinary and a Tribternary multiple.

8 Acknowledgments

We are grateful to the PRIMES STEP program for giving us the opportunity to conduct this research.

References

[1] J. J. Bravo and F. Luca, On a conjecture about repdigits in k-generalized Fibonacci sequences, Publ. Math. Debrecen 82 (2013), 623–639.

[2] J. Conway and A. Ryba, The extra Fibonacci series and the Empire State Building, Math. Intelligencer 38 (2016), 41–48.

[3] F. M. Dekking, J. Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electron. J. Combin. 27 (2020), Paper no. P1.52.

[4] E. Duchêne and M. Rigo, A morphic approach to combinatorial games: the Tribonacci case, RAIRO Theor. Inform. Appl. 42 (2008), 375–393.

[5] T. J. Keller, Generalizations of Zeckendorf’s theorem, Fibonacci Quart. 10 (1972), 95– 112.

[6] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2022.

[7] W. R. Spickerman, Binet’s formula for the Tribonacci sequence, Fibonacci Quart. 20 (1982), 118–120.

[8] W. A. Wythoff, A modification of the game of Nim, Nieuw Archief voor Wiskunde 7 (1907), 199–202.

2020 Mathematics Subject Classification: Primary 11B99. Keywords: Fibonacci number, Fibonacci word, Tribonacci number, Wythoff array.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000201}, \underline{A000213}, \underline{A001590}, \underline{A001950}, \underline{A003144}, \underline{A003145}, \underline{A003146}, \underline{A003265}, \underline{A003714}, \underline{A003726}, \underline{A003849}, \underline{A020992}, \underline{A060140}, \underline{A100683}, \underline{A104449}, \underline{A136175}, \underline{A214899}, \underline{A269725}, \underline{A269726}, \underline{A300867}, \underline{A305373}, \underline{A351631}, \underline{A351685}, \underline{A351689}, \underline{A352719}, \underline{A352748}, \underline{A353083}, \underline{A353084}, \underline{A353086}, \underline{A353090}, \underline{A353178}, \underline{A353193}, \underline{A354215}, and \underline{A356823}.)

Received June 26 2024; revised versions received May 21 2025; August 9 2025. Published in Journal of Integer Sequences, September 18 2025.

Return to Journal of Integer Sequences home page.