Fagan’s Construction, Strange Roots, and Tchoukaillon Solitaire

Mark Dukes School of Mathematics and Statistics University College Dublin Dublin 4 Ireland

                       mark.dukes@ucd.ie

Abstract

We examine a procedure that, on starting with an integer n, results in a pair of equal integers that are no greater than n. We call the resulting value the strange root of n, and we show how this strange-root-finding procedure is intimately linked to the game of Tchoukaillon solitaire. We analyze the strange-root-finding procedure in reverse to determine when a prescribed value is the strange root of at most two integers. We present a conjecture about strange roots and translate this conjecture into one involving Tchoukaillon solitaire.

1 Introduction

In this paper we present some results relating an algorithmic procedure on integer pairs due to Colm Fagan [5], an actuary with a keen interest in mathematics, to the game of Tchoukaillon solitaire. First we explain Fagan’s construction as it was originally defined in the On-line Encyclopedia of Integer Sequences [7, \underline{A204539}] and state the question that has motivated the work on this construction.

Fagan’s construction: Let m be a positive integer. Define the first Fagan pair to be (2, 2m). If the current Fagan pair is (i, y) and y > i, then construct the next Fagan pair (i + 1, z) where z is the smallest integer such that (i + 1)z > iy and i + 1 + z is even. Do this until the current Fagan pair (i, y) satisfies y ≤ i.

To illustrate this, choose m = 4. We begin with the Fagan pair (2, 8), which produces the next Fagan pair (3, 7). Applying the rule once again, we construct the Fagan pair (4, 6) followed by the Fagan pair (5, 5). As 5 ≯ 5 we are done. Let us use CF(m) to refer to the resulting sequence of Fagan pairs in this case, i.e.,

CF(4) : (2, 8) → (3, 7) → (4, 6) → (5, 5).

The outcome of this procedure seems to yield a pair of equal positive integers that we denote (cf(m), cf(m)), and in the above example cf(4) = 5. We prove this equality by using Lemma 3 in conjunction with the connection to Fagan pairs that follows Lemma 4.

Fagan’s question: If there is only one integer m for which cf(m) = n, we say that n is cf-unique. Are there infinitely many positive integers n that are cf-unique?

The values of m for which this is known to be true are 1, 2, 3, 6, 30, 493080, and 242650650. The corresponding values of n are given in the table and is sequence \underline{A204540}. Information on the number of integers m for which cf(m) is some prescribed value is given in \underline{A204539}.

\begin{matrix}m & cf(m) \\ 1 & 2 \\ 2 & 3 \\ 3 & 4 \\ 6 & 6 \\ 30 & 14 \\ 493080 & 1760 \\ 242650650 & 39046 \end{matrix}

Fagan’s construction relies on the chosen integer being a multiple of 4 and contains a parity condition. Observations and calculations made regarding this construction may be found in sequences \underline{A204539}, \underline{A204540}, and \underline{A185001}. The original terminology includes the notions of basins and the sea, which represent the size of the pre-image cf^{−1}(n) and the Fagan pair (cf(m), cf(m)), respectively.

In order to preserve Fagan’s original construction but at the same time move to a more mathematically convenient framework, in this paper we define (in Definition 1) a procedure on a larger set of integers and introduce the notion of a strange root of an integer n. This new procedure incorporates Fagan’s construction. The correspondence between strange roots and the final pair of numbers in a Fagan pair is that the strange root of 2m is equal to cf(m).

Tchoukaillon solitaire is a game played on a one-dimensional board that consists of a pit followed by a sequence of holes (see Figure 1). Every hole can contain a number of stones. The pit is special in that stones can be placed into it but not removed from it, and it is initially empty. The aim of the game to move stones from all holes to the pit according to a redistribution rule: select a hole, pick up all the stones in that hole, and place one stone in each hole that one meets on the way to the pit. It turns out that for a fixed number n of stones, there is only one configuration on a board consisting of n stones that is winnable, and the order in which hole selection should be executed is non-trivial. The game is won if one can select the holes in such an order so that at end all stones are in the pit. Figure 1 illustrates the Tchoukaillon board for n = 10 and the winning play of the game.

pit hole 1 hole 2 hole 3 hole 4 hole 5

Configuration (0,1,1,3,5)

pit hole 1 hole 2 hole 3 hole 4 hole 5

Configuration (1,2,2,4,0)

(0, 1, 1, 3, 5) ↦ (1, 2, 2, 4, 0) ↦ (0, 2, 2, 4, 0) ↦ (1, 0, 2, 4, 0) ↦ (0, 0, 2, 4, 0)
↦ (1, 1, 3, 0, 0) ↦ (0, 1, 3, 0, 0) ↦ (1, 2, 0, 0, 0) ↦ (0, 2, 0, 0, 0)
↦ (1, 0, 0, 0, 0) ↦ (0, 0, 0, 0, 0)

Figure 1: The Tchoukaillon board configurations for n = 10 is displayed first followed by the board configuration after the first play. Note that we do not record the number of stones in the pit in the configuration. The list of board configurations resulting in a win is given.

It turns out that there are precisely two Tchoukaillon boards for which the rightmost non-empty hole is hole number 5, and these boards correspond to having n = 10 and n = 11 stones. In this paper we prove the surprising result, in Proposition 11, that the number of Tchoukaillon boards for which the rightmost non-empty hole is hole number k −1 is equal to the number of integers n whose strange root is k. The number of integers n whose strange root is 5 + 1 is precisely two (these are the integers 11 and 12).

We also address the question of whether it is possible to go backwards from a strange root and systematically derive those integers that have a specified strange root. It will transpire in Proposition 12 that when we try working backwards from a strange root pair, there can be at most two pairs that map to a specified pair, and it can only be two if a divisibility condition is satisfied. We end the paper by using the correspondences we have proven to give an equivalent formulation of Fagan’s conjecture in terms of Tchoukaillon solitaire.

2 Strange roots

In this section we consider a construction on the natural numbers that at first looks fundamentally different to Fagan’s construction. We show that it incorporates Fagan’s construction by way of a linear transformation. As with Fagan’s construction, our construction also appears to terminate in an equal pair of integers and we prove this equality in Lemma 3. We refer to the equal pair of values that each construction terminates as the strange root of the initial number. To clearly distinguish our construction from Fagan’s, we use angle brackets in place of the parentheses used for Fagan pairs in Section 1.

Let ℕ = {1, 2, …} be the set of natural numbers.

Definition 1. Let n ∈ ℕ. Let Alist_{n} be the sequence of pairs produced by the following algorithm: Begin with the pair ⟨1, n⟩. Given a pair ⟨i, y_{i}⟩ with y_{i} > i, construct the subsequent pair ⟨i + 1, y_{i+1}⟩ where y_{i+1} is the smallest integer such that (i + 1)y_{i+1} > i(y_{i} + 1). Equivalently, y_{i+1} is the unique integer such that

y_{i+1} > \frac{i(y_{i} + 1)}{i + 1} ≥ y_{i+1} − 1.

This produces a sequence Alist_{n} = ⟨1, n = y_{1}⟩ → ⟨2, y_{2}⟩ → ⟨3, y_{3}⟩ → ⋯ → ⟨sr(n), y_{sr(n)}⟩ where ⟨sr(n), y_{sr(n)}⟩ is the final pair in this sequence. We will find it convenient to call the value sr(n) the strange root of n.

Example 2.

(i) Suppose n = 2. We begin with ⟨1, 2⟩. As y_{1} = 2 > 1 we let y_{2} be the smallest integer greater than 1(2)/2 = 1, which is 2. This gives the pair ⟨2, 2⟩. Since y_{2} ≯ 2 we are done and ⟨2, 2⟩ = ⟨sr(2), y_{sr(2)}⟩. Thus Alist_{2} is ⟨1, 2⟩ → ⟨2, 2⟩.

(ii) Suppose n = 8. We start with ⟨1, 8⟩. As 8 > 1 we let y_{2} be the smallest integer greater than 1(8 + 1)/2 = 4.5, which is 5. We now have the pair ⟨2, 5⟩ and since 5 > 2 we let y_{3} be the smallest integer greater than 2(5 + 1)/3 = 4, which is 5. This gives the pair ⟨3, 5⟩. As 5 > 3 we let y_{4} be the smallest integer greater than 3(5 + 1)/4 = 4.5, which is 5. This gives the pair ⟨4, 5⟩. As 5 > 4 we let y_{5} be the smallest integer greater than 4(5 + 1)/5 = 4.8, which is 5. This gives the pair ⟨5, 5⟩. Since 5 ≯ 5 this is the final pair and so ⟨sr(8), y_{sr(8)}⟩ = ⟨5, 5⟩. Thus Alist_{8} is ⟨1, 8⟩ → ⟨2, 5⟩ → ⟨3, 5⟩ → ⟨4, 5⟩ → ⟨5, 5⟩.

(iii) The Alist sequences for the first few integers are illustrated in Figure 2.

Lemma 3. For every n ∈ ℕ, we have sr(n) = y_{sr(n)}.

Proof. Consider the sequence of pairs produced by Definition 1. If ⟨sr(n), y_{sr(n)}⟩ is the final entry of Alist_{n}, then it must be the case that y_{sr(n)} ≤ sr(n). We now show the following:

(i) If we have pairs ⟨i, y_{i}⟩ and ⟨i + 1, y_{i+1}⟩ as part of this process, then y_{i+1} ≤ y_{i}.

\begin{matrix}n & Alist_{n} \\ 1 & ⟨1, 1⟩ \\ 2 & ⟨1, 2⟩ → ⟨2, 2⟩ \\ 3 & ⟨1, 3⟩ → ⟨2, 3⟩ → ⟨3, 3⟩ \\ 4 & ⟨1, 4⟩ → ⟨2, 3⟩ → ⟨3, 3⟩ \\ 5 & ⟨1, 5⟩ → ⟨2, 4⟩ → ⟨3, 4⟩ → ⟨4, 4⟩ \\ 6 & ⟨1, 6⟩ → ⟨2, 4⟩ → ⟨3, 4⟩ → ⟨4, 4⟩ \\ 7 & ⟨1, 7⟩ → ⟨2, 5⟩ → ⟨3, 5⟩ → ⟨4, 5⟩ → ⟨5, 5⟩ \\ 8 & ⟨1, 8⟩ → ⟨2, 5⟩ → ⟨3, 5⟩ → ⟨4, 5⟩ → ⟨5, 5⟩ \\ 9 & ⟨1, 9⟩ → ⟨2, 6⟩ → ⟨3, 5⟩ → ⟨4, 5⟩ → ⟨5, 5⟩ \\ 10 & ⟨1, 10⟩ → ⟨2, 6⟩ → ⟨3, 5⟩ → ⟨4, 5⟩ → ⟨5, 5⟩ \\ 11 & ⟨1, 11⟩ → ⟨2, 7⟩ → ⟨3, 6⟩ → ⟨4, 6⟩ → ⟨5, 6⟩ → ⟨6, 6⟩ \\ 12 & ⟨1, 12⟩ → ⟨2, 7⟩ → ⟨3, 6⟩ → ⟨4, 6⟩ → ⟨5, 6⟩ → ⟨6, 6⟩ \\ 13 & ⟨1, 13⟩ → ⟨2, 8⟩ → ⟨3, 7⟩ → ⟨4, 7⟩ → ⟨5, 7⟩ → ⟨6, 7⟩ → ⟨7, 7⟩ \\ 14 & ⟨1, 14⟩ → ⟨2, 8⟩ → ⟨3, 7⟩ → ⟨4, 7⟩ → ⟨5, 7⟩ → ⟨6, 7⟩ → ⟨7, 7⟩ \\ 15 & ⟨1, 15⟩ → ⟨2, 9⟩ → ⟨3, 7⟩ → ⟨4, 7⟩ → ⟨5, 7⟩ → ⟨6, 7⟩ → ⟨7, 7⟩ \\ 16 & ⟨1, 16⟩ → ⟨2, 9⟩ → ⟨3, 7⟩ → ⟨4, 7⟩ → ⟨5, 7⟩ → ⟨6, 7⟩ → ⟨7, 7⟩ \\ 17 & ⟨1, 17⟩ → ⟨2, 10⟩ → ⟨3, 8⟩ → ⟨4, 7⟩ → ⟨5, 7⟩ → ⟨6, 7⟩ → ⟨7, 7⟩ \\ 18 & ⟨1, 18⟩ → ⟨2, 10⟩ → ⟨3, 8⟩ → ⟨4, 7⟩ → ⟨5, 7⟩ → ⟨6, 7⟩ → ⟨7, 7⟩ \\ 19 & ⟨1, 19⟩ → ⟨2, 11⟩ → ⟨3, 9⟩ → ⟨4, 8⟩ → ⟨5, 8⟩ → ⟨6, 8⟩ → ⟨7, 8⟩ → ⟨8, 8⟩ \\ 20 & ⟨1, 20⟩ → ⟨2, 11⟩ → ⟨3, 9⟩ → ⟨4, 8⟩ → ⟨5, 8⟩ → ⟨6, 8⟩ → ⟨7, 8⟩ → ⟨8, 8⟩ \end{matrix}

Figure 2: The first few Alist sequences as defined in Definition 1

(ii) If we have pairs ⟨i, y_{i}⟩ and ⟨i + 1, y_{i+1}⟩ as part of this process, then y_{i+1} ≥ i + 1.

For (i), since ⟨i, y_{i}⟩ → ⟨i + 1, y_{i+1}⟩, by assumption it must be the case that y_{i} > i, so y_{i} ≥ i + 1. By Definition 1, y_{i+1} is the smallest integer that is strictly greater than the quantity z = i(y_{i} + 1)/(i + 1) = y_{i} + 1 − (y_{i} + 1)/(i + 1). As y_{i} ≥ i + 1 we must have that (y_{i}+1)/(i+1) ≥ (i+2)/(i+1) = 1+1/(i+1). Therefore we have z = y_{i}+1−(y_{i}+1)/(i+1) ≤ y_{i} + 1 − (1 + 1/(i + 1)) = y_{i} − 1/(i + 1). As y_{i+1} is the smallest integer strictly greater than z, and since z ≤ y_{i} − \frac{1}{i+1} < y_{i}, we must therefore have y_{i+1} ≤ y_{i}.

For (ii), notice that since z = y_{i} + 1 − (y_{i} + 1)/(i + 1) and y_{i} ≥ i + 1, we have z ≥ (i + 1) − 1/(i + 1). As y_{i+1} is the smallest integer strictly greater than z, we must have y_{i+1} ≤ i + 1.

The implications of (i) and (ii) are that the sequence of pairs must terminate since the second value is weakly decreasing and the first value is strictly increasing. Part (ii), with i = sr(n) − 1 gives us the inequality y_{sr(n)} ≥ sr(n). Since y_{sr(n)} ≤ sr(n) we must have that there is a final pair, and this final pair is ⟨sr(n), y_{sr(n)} = sr(n)⟩, as claimed.

The strange roots for the first few integers are given in Figure 3. A first observation is

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ sr(n) & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 5 & 5 & 6 & 6 & 7 & 7 & 7 & 7 & 7 & 7 & 8 & 8 \end{matrix}

Figure 3: The strange roots of the first few integers.

that the sequence seems to be weakly increasing.

Lemma 4. Let n_{1}, n_{2} ∈ ℕ with n_{1} ≤ n_{2}. Then sr(n_{1}) ≤ sr(n_{2}).

Proof. Suppose we have

Alist_{n_{1}} = ⟨1, n_{1} = x_{1}⟩ → ⟨2, x_{2}⟩ → ⋯ → ⟨sr(n_{1}), sr(n_{1})⟩,
Alist_{n_{2}} = ⟨1, n_{2} = y_{1}⟩ → ⟨2, y_{2}⟩ → ⋯ → ⟨sr(n_{2}), sr(n_{2})⟩.

Let us assume we have the pairs ⟨i, x_{i}⟩ and ⟨i, y_{i}⟩ and assume that x_{i} ≤ y_{i}. Note that, by assumption this is true for i = 1. By Definition 1 we have that x_{i+1} is the smallest integer strictly greater than i(x_{i} + 1)/(i + 1). Since x_{i} ≤ y_{i} we also have i(x_{i} + 1)/(i + 1) ≤ i(y_{i} + 1)/(i + 1), and by definition y_{i+1} is the smallest integer strictly greater than i(y_{i} + 1)/(i + 1). Therefore x_{i+1} ≤ y_{i+1}.

This tells us that at the second entry in Alist_{n_{2}} is always at least as big as the corresponding second entry in Alist_{n_{1}}, and the result follows.

Let us now connect these pairs of integers we have just introduced to Fagan pairs. Consider Alist_{2n} : ⟨1, 2n⟩ → ⋯ → ⟨sr_{2n}, sr_{2n}⟩ and the linear transform ⟨x, y⟩ ↦ (x, 2y − x). Note that the sum of the entries in the resulting pair is always even. The inverse of this transform is (x, y) ↦ ⟨x, (x + y)/2⟩. Under this transform the first entry of our sequences ⟨1, 2n⟩ ↦ (1, 4n − 1). The second pair in Alist_{2n} is ⟨2, y_{2}⟩ where y_{2} is the smallest integer such that y_{2} > (y_{1} + 1)/2 = (2n + 1)/2, which is n + 1. The pair ⟨2, n + 1⟩ ↦ (2, 2n) which is a Fagan pair.

Let us suppose that the ith pair in Alist_{2n} is ⟨i, y_{i}⟩, which maps to (i, 2y_{i} − i). If y_{i} > i then the subsequent pair in Alist_{2n} is ⟨i + 1, y_{i+1}⟩, which maps to (i + 1, 2y_{i+1} − (i + 1)) where y_{i+1} is the smallest integer such that y_{i+1} > i(y_{i} + 1)/(i + 1).

Let us re-frame this without the use of the angle bracket pairs. Define a_{i} := 2y_{i} − i. Notice that y_{i} > i ⟺ 2y_{i} > 2i ⟺ a_{i} > i. Given the pair (i, a_{i}) with a_{i} > i and i + a_{i} even, we next produce the pair (i + 1, a_{i+1}) where a_{i+1} is the smallest integer such that

\frac{a_{i+1} + (i + 1)}{2} > i\frac{((\frac{a_{i}+i}{2}) + 1)}{i + 1}.

This inequality simplifies to

(i + 1)a_{i+1} ≥ ia_{i},

with the additional property that i + 1 + a_{i+1} is even.

We would like to show that equality can never occur in this inequality if i + a_{i} and i + 1 + a_{i+1} are both even. Suppose that i is even. Then i + 1 is odd and since i + a_{i} is even we must have that a_{i} is even. Since i + 1 + a_{i+1} is even we must have that a_{i+1} is odd. The product (i + 1)a_{i+1} is therefore off and the product ia_{i} is even, and so it is not possible for (i + 1)a_{i+1} to be equal to ia_{i}. A similar argument holds for when i is odd. With equality ruled out, we have that a_{i+1} is the smallest integer such that (i + 1)a_{i+1} > ia_{i} and such that i + 1 + a_{i+1} is even. This statement is the defining step of Fagan’s construction and so all of these pairs beginning with (2, 2m) are Fagan pairs.

To conclude, the sequence of Fagan pairs that one meets in Fagan’s construction for the integer 4m corresponds exactly to the sequence of pairs in Alist_{2m} (discounting the initial pair) via the linear transformation ⟨x, y⟩ ↦ (x, 2y − x). The final pair in Alist_{2m} is ⟨sr(2m), sr(2m)⟩ ↦ (sr(2m), 2sr(2m) − sr(2m)) = (sr(2m), sr(2m)) = (cf(m), cf(m)).

Proposition 5. Let n ∈ ℕ and define y_{1} = n. Then the sequence of numbers (y_{1}, …, y_{r}) are such that Alist_{n} is ⟨1, y_{1}⟩ → ⟨2, y_{2}⟩ → ⋯ → ⟨r, r = y_{r}⟩ iff the sequence of numbers w_{i} defined by w_{i} = y_{i} − y_{i+1} + 1 satisfies

w_{i} = ⌈\frac{n − 1 − (w_{1} + ⋯ + w_{i−1})}{i + 1}⌉ ,

for all i = 1, 2, …, r − 1. (Note that the sum of the w_{j} is zero when i = 1.)

Proof. Let n ∈ ℕ and set y_{1} := n. By Definition 1, a sequence of numbers (y_{1}, …, y_{r}) is such that ⟨1, y_{1}⟩ → ⟨2, y_{2}⟩ → ⋯ → ⟨r, y_{r}⟩ with r = sr(y_{1}) = y_{r} iff y_{i+1} > i(y_{i} + 1)/(i + 1) ≥ y_{i+1} − 1 for all i ∈ {1, …, r − 1} and y_{r} = r = sr(y_{1}).

Let us translate this last statement into one that concerns only the differences between the y_{i} terms. For a general sequence of numbers (y_{1}, …, y_{r}), we consider the sequence (z_{1}, …, z_{r−1}) of differences where z_{i} := y_{i} − y_{i+1} for all 1 ≤ i < r.

The value z_{i} comes from the transition ⟨i, y_{i}⟩ → ⟨i + 1, y_{i+1}⟩. Since there is a transition we must have y_{i} > i and, by Definition 1, y_{i+1} is the unique integer such that

y_{i+1} > \frac{i(y_{i} + 1)}{i + 1} ≥ y_{i+1} − 1.

Subtracting every term in this inequality from y_{i} gives

y_{i} − y_{i+1} < y_{i} − \frac{i(y_{i} + 1)}{i + 1} = \frac{y_{i} + 1}{i + 1} − 1 ≤ y_{i} − y_{i+1} + 1,

which is equivalent to

z_{i} < \frac{y_{i} + 1}{i + 1} − 1 ≤ z_{i} + 1.

This, in turn, is equivalent to ⌈\frac{y_{i} + 1}{i + 1} − 1⌉ = z_{i} + 1, i.e., ⌈\frac{y_{i} + 1}{i + 1}⌉ = z_{i} + 2. We can now

provide an expression for the z_{i} values without the y_{i} values by noticing that the sum of the first i − 1 z values is z_{1} + ⋯ + z_{i−1} = y_{1} − y_{i} = n − y_{i}. This gives

z_{i} = ⌈\frac{1 + n − (z_{1} + z_{2} + ⋯ + z_{i−1})}{i + 1}⌉ − 2

for all i = 1, …, r − 1. Note that when i = 1 the sum of the z terms in the expression is empty, and is consequently 0.

Substituting z_{i} = w_{i} − 1 into the above expression, and simplifying, gives

w_{1} = ⌈\frac{n − 1}{2}⌉

and for all i = 2, …, r − 1,

w_{i} = ⌈\frac{n − 1 − (w_{1} + ⋯ + w_{i−1})}{i + 1}⌉ .

3 Tchoukaillon solitaire

Let us now introduce the board game Tchoukaillon solitaire and detail some of its properties. The board for this game is a sequence of holes numbered 0, 1, 2, . . .. We assume that hole 1 is to the right of hole 0, and hole 2 is to the right of hole 1, and so on (see Figure 1). The game is played as follows: n stones are placed in these holes, but hole 0 (also known as the pit) is special and does not initially contain any stones.

The aim of the game is to move all the stones in holes 1 and above to the pit through some sequence of valid moves. A valid move consists of selecting a hole, i say, that currently contains s_{i} stones, and then re-distributing these s_{i} stones by placing one stone into each of the s_{i} holes i − 1, i − 2, …, i − s_{i}. If i − s_{i} < 0 then we have no holes left in which to place the remaining s_{i} − i stones, and we immediately lose the game. One should therefore never select a hole that currently has more stones than there are holes to its left. The game is won if one can select the holes in such an order that we end up with all stones in the pit.

Let us write c = (c_{1}, c_{2}, …) for a Tchoukaillon configuration whereby c_{i} is the number of stones in hole i and n := c_{1} +c_{2} +· · ·. It turns out that for every n there is a unique winning Tchoukaillon configuration, Tchouk_{n}, consisting of n stones. We list these configurations in Figure 4.

We find it important to mention that it is not the case that any order of selecting holes in Tchouk_{n} results in a win.

Example 6. Consider Tchouk_{3} = (1, 2). If we select hole 1 first, then on performing our move the single stone is placed into the pit. Next we select hole 2 that contains two stones, and on performing our move we drop one stone into hole 1 and the other into the pit. Next we select hole 1 again, and drop the stone from there into the pit. After this all three stones are in the pit and we have won the game.

However, had we selected hole 2 first, then one stone would have been placed into hole 1, and one into the pit. There are then two stones in hole 1, and there is no way of winning so we have lost the game.

n  Tchouk_{n}  Move vector
0  ()  none
1  (1)  (1)
2  (0, 2)  (1, 1)
3  (1, 2)  (2, 1)
4  (0, 1, 3)  (2, 1, 1)
5  (1, 1, 3)  (3, 1, 1)
6  (0, 0, 2, 4)  (3, 1, 1, 1)
7  (1, 0, 2, 4)  (4, 1, 1, 1)
8  (0, 2, 2, 4)  (4, 2, 1, 1)
9  (1, 2, 2, 4)  (5, 2, 1, 1)
10  (0, 1, 1, 3, 5)  (5, 2, 1, 1, 1)
11  (1, 1, 1, 3, 5)  (6, 2, 1, 1, 1)
12  (0, 0, 0, 2, 4, 6)  (6, 2, 2, 1, 1)
13  (1, 0, 0, 2, 4, 6)  (7, 2, 1, 1, 1, 1)

Figure 4: The first few unique winning configurations Tchouk_{n} of Tchoukaillon solitaire

One way to construct Tchouk_{n} is by recursion. Given Tchouk_{n−1}, suppose that position i is the leftmost position containing 0 stones. Then Tchouk_{n} is the configuration that results from Tchouk_{n−1} by adding i stones to hole i, and subsequently removing one stone from each of the holes 1, 2, …, i − 1.

Recently, Jones, Taalman, and Tongen [6] gave an explicit method to construct the winning configurations Tchouk_{n}. The configuration Tchouk_{n} = (c_{1}, c_{2}, …) whereby

c_{1} = n mod 2
c_{2} = n − c_{1} mod 3
c_{3} = n − (c_{1} + c_{2}) mod 4
⋮
c_{k} = n − (c_{1} + c_{2} + ⋯ + c_{k−1}) mod (k + 1).

Once the sum c_{1} + c_{2} + ⋯ + c_{k−1} = n one stops computing further entries.

For any winning configuration, there is some sequence of moves that result in a win. As we saw in Example 6, it is not the case that any sequence of moves on Tchouk_{n} result in a win. The sequence of moves that is required to ‘win’ can be discovered by playing the game in reverse, and is essentially the same as the recursive rule for constructing Tchoukaillon configurations highlighted above (except, of course, executed in reverse since it starts from the empty board).

There is another interesting aspect to the winning configurations that instead looks at the number of times each hole was selected for a valid move during a ‘win’. Given c = (c_{1}, …, c_{k}) = Tchouk_{n}, let m = m(c) = (m_{1}, …, m_{k}) be the sequence whereby m_{i} is the number of times that hole i was selected in playing the game. This sequence m is known in the literature as the move vector. For example, in Example 6 we considered c = (1, 2) = Tchouk_{3}. For that game hole 1 was selected twice (so m_{1} = 2) and hole 1 was selected once (so m_{2} = 1). The move vector for this c is m(c) = (2, 1).

Taalman et al. [9] gave an explicit expression for the entries of the move vector of Tchouk_{n} in terms of n:

Theorem 7. (Taalman et al. [9, Thm.4]) The move vector for solving Tchouk_{n} is m = (m_{1}, …, m_{ℓ}) where

m_{1} = ⌈\frac{n}{2}⌉
m_{2} = ⌈\frac{n − m_{1}}{3} ⌉
m_{3} = ⌈\frac{n − (m_{1} + m_{2})}{4}⌉
⋮
m_{ℓ} = ⌈\frac{n − (m_{1} + m_{2} + ⋯ + m_{ℓ−1})}{ℓ + 1}⌉ .

The link between Tchoukaillon solitaire and strange roots is now seen by comparing the theorem above to the expression in Proposition 5. The precise correspondence is given in the following theorem.

Theorem 8. Let n ≥ 2. The sequence Tchouk_{n−1} = (b_{1}, …, b_{ℓ}) corresponds uniquely to Alist_{n} : ⟨1, y_{1} = n⟩ → ⟨2, y_{2}⟩ → ⋯ → ⟨sr(n), sr(n)⟩ as follows:

(a) ℓ = sr(n) − 1.

(b) For i = 1, 2, …, sr(n) − 1,

b_{i} = 2i + 1 + iy_{i} − (i + 1)y_{i+1}.

(c) For i = 1, 2, …, sr(n),

y_{i} = i + \frac{1}{i}(b_{i} + b_{i−1} + ⋯ + b_{sr(n)−1}).

Proof. With the objects as stated in the theorem, the correspondences are established through the intermediate object of the move sequence m = (m_{1}, m_{2}, …, m_{ℓ}) where m_{i} := 1 + y_{i} − y_{i+1}. The largest value of ℓ for which this is well defined is ℓ = sr(n) − 1, hence (a). That m is a valid move vector is verified by showing 0 ≤ m_{i} < i for all i, and this is a consequence of Lemma 3.

The sum of the entries in a move sequence is the same as the number of stones in the Tchoukaillon game, and so ∑_{i} m_{i} = (1+y_{1}−y_{2})+(1+y_{2}−y_{3})+⋯ = (sr(n)−1)+y_{1}−y_{sr(n)} = sr(n) − 1 + n − sr(n) = n − 1. In other words the sequence Alist_{n} can be seen to correspond to a move sequence for a Tchoukaillon game with n − 1 stones. In order to be able to write the entries of the sequences (b_{1}, …, b_{sr(n)−1}) and (y_{1}, …, y_{sr(n)}) in terms of one another, we make use of some identities.

(b) To describe the b_{j} in terms of m_{j}, we use the following identify from Taalman et al. [9, Theorem 2]:

b_{i} = im_{i} − ∑_{j=i+1}^{sr(n)−1} m_{j}.

Substitute m_{j} = 1 + y_{j} − y_{j+1} into this. We have

b_{i} = \begin{cases}i(1 + y_{i} − y_{i+1}) − ∑_{j=i+1}^{sr(n)−1}(1 + y_{j} − y_{j+1}), & if i ≤ sr(n) − 2; \\ (sr(n) − 1)(1 + y_{sr(n)−1} − y_{sr(n)}), & if i = sr(n) − 1. \end{cases}

The expression in the top case simplifies to 2i + 1 − sr(n) + iy_{i} − (i + 1)y_{i+1} + y_{sr(n)} = 2i+1+iy_{i} −(i+1)y_{i+1}. The expression in the bottom case simplifies, by using the fact that y_{sr(n)−1} = y_{sr(n)} for n ≥ 2, to sr(n)−1. In fact if we use i = sr(n)−1 in the top case then it reduces to this same expression sr(n) − 1, and so b_{i} = 2i + 1 + iy_{i} − (i + 1)y_{i+1} for all i = 1, 2, …, sr(n) − 1.

(c) To describe the y_{j} in terms of the b_{j}. If Tchouk_{n−1} = (b_{1}, b_{2}, …, b_{sr(n)−1}) = b then the move vector corresponding to b is m = (m_{1}, …, m_{sr(n)−1}) where

m_{i} = \frac{1}{i}b_{i} + \frac{1}{i(i + 1)} ∑_{k=i+1}^{sr(n)−1} b_{k},  (1)

for all 1 ≤ i ≤ sr(n) − 1 by using Taalman et al. [9, Eq. (2)]. As the m_{i} and y_{i} values are related via m_{i} = 1 + y_{i} − y_{i+1} for all 1 ≤ i ≤ sr(n) − 1 and y_{1} = n, we find that

y_{i} = n + (i − 1) − ∑_{t=1}^{i−1} m_{t}

and this holds for all 1 ≤ i ≤ sr(n). The ends of this sequence are well defined since y_{1} = n + 0 − 0 = n and y_{sr(n)} = n + (sr(n) − 1) − (m_{1} + ⋯ + m_{sr(n)−1}) = n + (sr(n) − 1) − (n − 1) = sr(n).

Again by using Equation (1) we can express the partial sum

∑_{t=1}^{i−1} m_{t} = ∑_{t=1}^{i−1} (\frac{1}{t}b_{t} + (\frac{1}{t} − \frac{1}{t + 1}) ∑_{k=t+1}^{sr(n)−1} b_{k})

= ∑_{t=1}^{i−1} \frac{1}{t}b_{t} + ∑_{t=1}^{i−1} (\frac{1}{t} − \frac{1}{t + 1}) ∑_{k=t+1}^{sr(n)−1} b_{k}

= ∑_{t=1}^{i−1} \frac{1}{t}b_{t} + ∑_{k=2}^{sr(n)−1} b_{k} ∑_{t=1}^{min(i,k)−1} (\frac{1}{t} − \frac{1}{t + 1})

= ∑_{t=1}^{i−1} \frac{1}{t}b_{t} + ∑_{k=2}^{sr(n)−1} b_{k} (1 − \frac{1}{min(i, k)})

= ∑_{t=1}^{i−1} \frac{1}{t}b_{t} + (∑_{t=1}^{i−1} b_{t} (1 − \frac{1}{t})) + (1 − \frac{1}{i}) (b_{i} + ⋯ + b_{sr(n)−1})

= (b_{1} + ⋯ + b_{i−1}) + (1 − \frac{1}{i}) (b_{i} + ⋯ + b_{sr(n)−1})

= (n − 1) − \frac{1}{i} ∑_{k=i}^{sr(n)−1} b_{i}.

Using this in the equation for y_{i}, and simplifying, we have that

y_{i} = i + \frac{1}{i} ∑_{k=i}^{sr(n)−1} b_{i},

for all 1 ≤ i ≤ sr(n). Therefore the configuration b = Tchouk_{n−1} corresponds to Alist_{n} : ⟨1, y_{1}⟩ → ⟨2, y_{2}⟩ → ⋯ → ⟨sr(n), sr(n)⟩, where the y_{i} are as stated.

Notice that the end of a Tchoukaillon configuration is a fixed point in the following sense:

Lemma 9. Suppose b = (b_{1}, …, b_{ℓ}) = Tchouk_{n}. Then b_{ℓ} = ℓ.

Proof. This is straightforward to see by using the recursive construction presented after Example 6 Since Tchouk_{1} = (1), we have b_{ℓ} = 1 = ℓ and it is true. Suppose it is true for n = k so that Tchouk_{k} = (b_{1}, …, b_{ℓ}) with ℓ = b_{ℓ}. To construct Tchouk_{k+1} from Tchouk_{k} we must condition on the appearance of the first (i.e., lowest indexed) 0 in Tchouk_{k}.

(a) If b_{i} = 0 is the first zero of Tchouk_{k} and i < ℓ then only the entries in holes {1, …, i} are changed and the final entry of Tchouk_{k+1} is the same as the final entry of Tchouk_{k}, hence b_{ℓ} = ℓ.

(b) If b_{ℓ+1} is the first zero of Tchouk_{k}, then Tchouk_{k+1} must have b_{ℓ+1} = ℓ + 1 and all entries to the left of this are decreased by one.

In both cases, the claim holds true and the result follows by induction.

A natural corollary of Theorem 8 and Lemma 9 is the following, which allows us to interpret questions about the strange root of n in terms of winning Tchoukaillon configurations.

Corollary 10. For all n ≥ 2, sr(n) = length(Tchouk_{n−1}) = final(Tchouk_{n−1}), where length(c) is the highest index i such that c_{i} ≠ 0, and final(c) is the value of that c_{i}.

The correspondence established in this section allows us to gain some insight into the sr statistic through enumerative results on Tchoukaillon solitaire. The quantity that is most well-known in relation to Tchoukaillon solitaire is a statistic t(k) that is defined as the smallest integer n for which k occurs for the first time in Tchouk_{n}. For example, if we look at Figure 4, we see that 4 first occurs in Tchouk_{6}, and so t(4) = 6.

Since the end of every winning Tchoukaillon sequence is a value equal to its index (by Lemma 9), t(k) may be equivalently defined as the number of n(≥ 0) for which there are no entries in holes k, k + 1, k + 2, . . .. For example, for k = 4, if we look at Figure 4 then there are no stones in holes 4 or higher of the configurations Tchouk_{0}, Tchouk_{1}, …, Tchouk_{5} and so t(4) = 6.

The sequence (t(1), t(2), …) is \underline{A002491} and begins

1, 2, 4, 6, 10, 12, 18, 22, 30, 34, 42, 48, 58, 60, ….

It is known to have several curious properties. An extremely good exposition of these properties and further references can be found in Jones et al. [6].

• t(k) can be calculated by starting with k and successively rounding up to next multiple of k − 1, k − 2, …, 1. For example, t(4) is calculated by starting with 4, round up to the next multiple of k − 1 = 3 which is 6. Round up again to the next multiple of k − 2 = 2 which is still 6, and rounding up to the next multiple of k − 3 = 1 does not change the value at all. Thus t(4) = 6. (Brown [2]).

• It can be generated by a sieving process on the integers. This was described in Erdős and Jabotinsky [4] and David [3], and is very clearly explained in Sloane [8].

• t(k) = \frac{k^{2}}{π} + O(n) (this result is due to Broline and Loeb [1] and improves on Erdős

and Jabotinsky [4] result t(k) = \frac{k^{2}}{π} + O(n^{4/3})).

Brown’s construction (in the first point above) bears a similarity to the construction that we are considering. It produces pairs of integers according to a rule similar to ours. However, it does not stop in the same manner that Fagan’s construction or Definition 1 do, and so the notion of a ‘root’ seems to have been skipped over. In light of the correspondences we have established, we have the following:

Proposition 11.

(a) The number of integers n for which sr(n) = k is t(k) − t(k − 1). Equivalently, t(k) = |{n ≥ 1 : sr(n) ≤ k}|.

(b) The number of integers whose strange root is less than k is approximately k^{2}/π for k large.

Part (b) helps justify the strange root terminology we have used as the number of nonnegative integers whose square root is less than a natural number k is k^{2}. Although these connections give us some interesting information about the sr function, the known properties of t(k) are not sufficient to aid us any further in considering Fagan’s question. In the next section we present a brief analysis of the Alist sequences with Fagan’s question in mind.

4 Determining integers having a prescribed strange root

When we consider the sequence of pairs that arise from these constructions, is it possible to express those pairs that must precede some pair in a given sequence? Moreover, given an integer r, is it possible to determine the set {n ∈ ℕ : sr(n) = r}?

Suppose

Alist_{n} : ⟨1, n⟩ → ⋯ → ⟨i, u⟩ → ⟨i + 1, v⟩ → ⋯ → ⟨r, r⟩

where r ≥ 2. Definition 1 tells us that u must be an integer that satisfies (i+1)v > i(u+1) ≥ (i+1)(v −1). In analyzing the values that u can take, at a second glance it is more restricted than first appears. It transpires that there can be either one or two values of u that map to a given ⟨i + 1, v⟩.

Proposition 12. Let n ∈ ℕ and consider

Alist_{n} : ⟨1, n⟩ → ⋯ → ⟨i, u⟩ → ⟨i + 1, v⟩ → ⋯ → ⟨r, r⟩

where r ≥ 2. Then

u ∈ \begin{cases}\{v − 2 + ⌊\frac{v−1}{i}⌋ , v − 1 + ⌊\frac{v−1}{i}⌋\} , & if i | v − 1; \\ \{v − 1 + ⌊\frac{v−1}{i}⌋\} , & if i |̸ v − 1. \end{cases}

Proof. Suppose that ⟨i, u⟩ → ⟨i+1, v⟩ as stated in the theorem. Then by Definition 1 u must satisfy (i + 1)v > i(u + 1) ≥ (i + 1)(v − 1). This inequality is equivalent to v + (v/i) − 1 = v − 1 + (v/i) > u ≥ (v − 1) + (v − 1)/i − 1 = v − 2 + (v − 1)/i, i.e.,

v − 1 + ⌊\frac{v − 1}{i}⌋ ≥ u ≥ v − 2 + ⌈\frac{v − 1}{i}⌉ .

Notice that if \frac{v−1}{i} is an integer x, then this inequality is v − 1 + x ≥ u ≥ v − 2 + x, i.e., u ∈ \{v −2+x, v −1+x\}. However, if \frac{v−1}{i} is not an integer but is x+ϵ for some integer x ∈ ℕ and ϵ ∈ (0, 1), then this inequality is v−1+x ≥ u ≥ v−2+x+1 = v−1+x, i.e., u = v−1+x. For example, consider ⟨i + 1, v⟩ = ⟨4, 5⟩, we have that v − 1 = 4 and i = 3. As 4/3 is not an integer, the only u for which ⟨i, u⟩ → ⟨i + 1, v⟩ is u = v − 1 + ⌊(v − 1)/x⌋ = 4 + 1 = 5. The only pair ⟨3, u⟩ that produces ⟨4, 5⟩ is ⟨3, 5⟩.

Proposition 12 allows us to give a description of those integers n whose strange root is some prescribed value by working backwards from the value of the root. Let us observe that in Proposition 12, when i = 1, the value i always divides v − 1, and there are two possible values for u such that ⟨1, u⟩ → ⟨2, v⟩ for all v ≥ 2. Thus given a pair ⟨2, v⟩, both ⟨1, 2v − 3⟩ → ⟨2, v⟩ and ⟨1, 2v − 2⟩ → ⟨2, v⟩.

The following proposition provides a characterization of the r that are the roots of at most two integers.

Proposition 13. Suppose that n ≥ 5. Let x_{r} = r and for every i = r − 1, …, 1 define

x_{i} := x_{i+1} − 1 + ⌊\frac{x_{i+1} − 1}{i}⌋ = ⌊\frac{(i + 1)(x_{i+1} − 1)}{i}⌋ .

Then there are only two integers (x_{1} and x_{1} − 1) that have r as its strange root if and only if x_{i+1} − 1 ≢ 0 (mod i) for all i ∈ {2, …, r − 2}.

Example 14. Consider r = 14. Then we have x_{14} = 14, and we apply the rule to derive the second row of the following table:

i  14 13 12 11 10 9 8 7 6 5 4 3 2 1
x_{i}  14 14 14 14 14 14 14 14 15 16 18 22 31 60
\frac{x_{i+1} − 1}{i}  \frac{13}{12} \frac{13}{11} \frac{13}{10} \frac{13}{9} \frac{13}{8} \frac{13}{7} \frac{13}{6} \frac{14}{5} \frac{15}{4} \frac{17}{3} \frac{21}{2}

Using the top two rows we can compute the values in the bottom row. None of the quotients in the bottom row are integers hence, by the above proposition, there are only two integers (x_{1} = 60 and x_{1} − 1 = 59) that have 14 its strange root.

Proposition 13 classifies those r that are the strange root of only two integers. There are precisely r − 3 (non-)divisibility conditions to be satisfied in order for r to be a unique strange root. Thus as r grows it would appear less and less likely to find an r such that the sequence (x_{r}, …, x_{1}) satisfies the stated condition. There is nothing suggesting that there is a maximal such value of r after which no more unique strange roots may exist. Based on the form of the condition in Prop 13 we present the following conjecture.

Conjecture 15. There exists an infinite number of integers r ∈ ℕ for which the size of the set {n ∈ ℕ : sr(n) = r} is 2.

Fagan’s question translates into the question that we have considered, since an integer r is the strange root of only two integers iff {m ∈ ℕ : cf(m) = r} is a singleton set. In Figure 5 we record the first few values of both cf and sr to summarize how they are related.

\begin{matrix}m & cf(m) & sr(n) & n \\ 1 & 2 & 2 & 2 \\ 2 & 3 & 3 & 3, 4 \\ 3 & 4 & 4 & 5, 6 \\ 6 & 6 & 6 & 11, 12 \\ 30 & 14 & 14 & 59, 60 \\ 493080 & 1760 & 1760 & 986159, 986160 \\ 242650650 & 39046 & 39046 & 485301299, 485301300 \end{matrix}

Figure 5: Note that cf(m) = x is equivalent to sr(2m) = x.

Since the numbers in Figure 5 seem to be growing so fast, it is not easy to get a clearer picture on the next value (if it exists). It would be interesting to see if some of the theory regarding the game of Tchoukaillon solitaire could be utilized to give insights into strange roots that are the strange roots of at most two integers.

We end this paper with a reformulation of Fagan’s conjecture in terms of Tchoukaillon solitaire through the correspondence we established in Theorem 8. Let us say that the Tchoukaillon solitaire board b = (b_{1}, …, b_{k}) = Tchouk_{n} satisfies the Fagan property if

(i) b_{1} = 1 and b_{k} = k, and

(ii) 1 ≤ b_{i} < i for all i ∈ {2, …, k − 1}.

To see what the Fagan property represents from a solitaire perspective, let us assume that Tchouk_{n} satisfies the Fagan property. Consider the next two plays of the Tchouk_{n} game. We have, by Theorem 8(a), that sr(n) = 1+k. Hole 1 contains 1 stone and should now be played since if it ends up containing more than one stone the game has been lost. After playing hole 1 we have b_{1} = 0, b_{k} = k, and 1 ≤ b_{i} < i for all other i which is the board Tchouk_{n−1}. By Theorem 8(a) we have sr(n−1) = 1+k. We now play the leftmost hole such that b_{i} = i, and this is hole k. After this play we have the configuration (1, b_{2}+1, …, b_{k−1}+1, 0) = Tchouk_{n−2}, which is a board having length 1 less than Tchouk_{n−1}. By Theorem 8(a), we have sr(n−2) = k and this is different to sr(n − 1) and sr(n).

Next consider Tchouk_{n+1}, the board that results from ‘un-playing’ the board Tchouk_{n}. As all of the holes 1, …, k of Tchouk_{n} are non-empty, it must be the case that the last hole played that resulted in Tchouk_{n} was hole k+1. This means sr(n+1) = 1+(k+1). Therefore, if b = (b_{1}, …, b_{k}) = Tchouk_{n} satisfies the Fagan property, there are at most two integers, n and n − 1, whose strange root is k + 1.

Conjecture 16 (Fagan’s Tchoukaillon Solitaire Conjecture). The exists an infinite number of Tchoukaillon solitaire boards that satisfy the Fagan property.

Remark 17. Determining those Tchoukaillon boards that satisfy the Fagan property corresponds to solving a system of linear congruences (as explained in this paper just after Example 6), a fact that would suggest that a solution to this conjecture is difficult but not impossible.

5 Acknowledgments

I am grateful to Colm Fagan for sharing his interesting problem with me and to the anonymous referee for very insightful comments that have helped improve both the presentation and content of the paper. My thanks to Neil Sloane for providing a reference for the the construction due to Kevin Brown.

References

[1] D. M. Broline and D. E. Loeb, The combinatorics of Mancala-type games: Ayo, Tchoukaillon and 1/π, UMAP J. 16 (1995), 21–36.

[2] K. S. Brown, Rounding up to π, 2020. Available at http://www.mathpages.com/home/

   kmath001/kmath001.htm.

[3] Y. David, On a sequence generated by a sieving process, Riveon Lematematika 11 (1957), 26–31.

[4] P. Erdős and E. Jabotinsky, On a sequence of integers generated by a sieving process, Indag. Math. 20 (1958), 115–128.

[5] C. Fagan, A construction on pairs of integers related to sequence \underline{A204539}, personal communication, June 2020.

[6] B. Jones, L. Taalman, and A. Tongen, Solitaire Mancala games and the Chinese remainder theorem, Amer. Math. Monthly 120 (2013), 706–724.

[7] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2021. Available

   at https://oeis.org.

[8] N. J. A. Sloane, My favorite integer sequences, in C. Ding, T. Helleseth, and H. Niederreiter, eds., Sequences and their Applications (Proceedings of SETA ’98), Springer-Verlag,

   1999, pp. 103–130. Available at http://arxiv.org/abs/math/0207175.

[9] L. Taalman, A. Tongen, B. Warren, F. Wyrick-Flax, and I. Yoon, Mancala matrices, College Math. J. 44 (2013), 273–283.

2010 Mathematics Subject Classification: Primary 68R05; Secondary 91A46, 11B99. Keywords: Fagan pair, strange root, Tchoukaillon solitaire.

(Concerned with sequences \underline{A002491}, \underline{A185001}, \underline{A204539}, and \underline{A204540}.)

Received November 4 2020; revised versions received April 22 2021; May 14 2021; May 26 2021. Published in Journal of Integer Sequences, June 4 2021.

Return to Journal of Integer Sequences home page.