\documentclass[12pt]{article} \usepackage{latexsym} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \setlength{\parindent}{0in} \setlength{\parskip}{5pt} \newtheorem{definition}{Definition} \newtheorem{lemma}[definition]{Lemma} \newtheorem{theorem}[definition]{Theorem} \newtheorem{conjecture}[definition]{Conjecture} \newtheorem{proposition}[definition]{Proposition} \newtheorem{cor}[definition]{Corollary} \newtheorem{problem}[definition]{Problem} \newtheorem{observation}[definition]{Observation} \newtheorem{claim}[definition]{Claim} \newtheorem{example}{Example} \begin{document} \begin{center} {\bf REGULARITY IN THE ${\cal G}-$SEQUENCES OF OCTAL GAMES WITH A PASS} \vskip 20pt {\bf D. G. Horrocks\footnote{partially supported by NSERC}}\\ {\smallit Department of Mathematics and Computer Science, University of Prince Edward Island, Charlottetown, PE C1A 4P3, Canada}\\ {\tt dhorrocks@upei.ca}\\ \vskip 10pt {\bf R. J. Nowakowski\footnote{partially supported by NSERC}}\\ {\smallit Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 3J5, Canada}\\ {\tt rjn@mathstat.dal.ca}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 9/19/02, Revised: 3/27/03, Accepted: 4/7/03, Published: 4/9/03} \vskip 30pt \centerline{\bf Abstract} \noindent Finite octal games are not arithmetic periodic. By adding a single pass move to precisely one heap, however, we show that arithmetic periodicity can occur. We also show a new regularity: games whose ${\cal G}-$sequences are partially arithmetic periodic and partially periodic. We give a test to determine when an octal game with a pass has such regularity and as special cases when the ${\cal G}-$sequence has become periodic or arithmetic periodic. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#G01\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} A {\it Taking-and-Breaking} game (see Chapter 4 of [3]) is an impartial, combinatorial game, played with heaps of beans on a table. Players move alternately and a move for either player consists of choosing a heap, removing a certain number of beans from the heap and then possibly splitting the remainder into several heaps. The winner is the player making the last move. The number of beans to be removed and the number of heaps that one heap can be split into are given by the rules of the game. For a finite {\it octal} game the rules are given by the octal code ${\bf d_{0}.d_{1}d_{2} \ldots d_{u}}$ where $0\leq {\bf d_{i}}\leq7$. If ${\bf d_{i}}=0$ then a player cannot take $i$ beans away from a heap. If ${\bf d_{i}}=\delta_{2}2^{2}+\delta_{1}2^{1}+\delta_{0}2^{0}$ where $\delta_{j}$ is 0 or 1, a player can remove $i$ beans from the heap provided he leaves the remainder in exactly $j$ non-empty heaps for some $j$ with $\delta_{j}=1$. In such games, then, a heap cannot be split into more than 2 heaps. A {\it subtraction} game, in which a heap may be reduced only by one of the numbers in a prescribed set (called the subtraction set), has each $d_{i} \in \{0, 3 \}$, i.e. a player can remove beans but cannot split the heap. The {\it followers}, or {\it options}, of a game are all those positions which can be reached in one move. The {\it minimum excluded value} of a set $S$ is the least nonnegative integer which is not included in $S$ and is denoted ${\rm mex}(S)$. Note that $\mbox{mex}\{\, \} = 0$. The {\it nim-value} of an impartial game $G$, denoted by ${\cal G}(G)$, is given by \[{\cal G}(G)={\rm mex}\{{\cal G}(H) | H \mbox{ is a follower of } G\}.\] The values in the set $\{{\cal G}(H) | H \mbox{ is a follower of } G\}$ are called {\it excluded values} for ${\cal G}(G)$. It is not difficult to see that an impartial game $G$ is a previous player win, i.e. the next player has no good move, if and only if ${\cal G}(G)=0$. The {\it nim-sum} of two nonnegative integers is the exclusive or (XOR), written $\oplus$, of their binary representations. It can also be described as adding the numbers in binary without carrying. A game $G$ is the {\it disjunctive} sum of games $H$ and $K$, written $G=H+K$, if on each turn, the players must choose one of $H$ and $K$ and make a legal move in that game. From the theory of impartial games (see [3] or [5]) if $G=H+K$, then ${\cal G}(G)={\cal G}(H)\oplus {\cal G}(K)$. Taking-and-Breaking games are examples of disjunctive games -- choose one heap and play in it. To know how to play these games well, it suffices to know what the nim-values are for individual heaps. For a given game, let ${\cal G}(i)$ be the nim-value of the game played with a heap of size $i$; the goal is to find a simple rule for ${\cal G}(i)$. We define the ${\cal G}$-sequence for a Taking-and-Breaking game to be the sequence ${\cal G}(0)$, ${\cal G}(1)$, ${\cal G}(2)$, $\ldots$. For a given subclass of these games, it is of interest to determine {\it What types of regularity are exhibited by the ${\cal G}-$sequences?} A ${\cal G}-$sequence is said to be {\it periodic} if there exist $N$ and $p$ such that ${\cal G}(n+p)={\cal G}(n)$ for all $n\geq N$; it is {\it arithmetic periodic} if there exist $N$, $p$ and $s>0$ such that ${\cal G}(n+p)={\cal G}(n)+s$ for all $n\ge N$, $s$ is called the {\it saltus}. All finite subtraction games have a bounded number of options and so are periodic. Austin, [2] (see also [3]), shows that the ${\cal G}-$sequence of any finite octal game cannot be arithmetic periodic. The heart of the proof is to show that there are too few options for the ${\cal G}-$sequence to rise quickly enough for it to be arithmetic periodic. It is not known, however, if the ${\cal G}-$sequence of a finite octal game must be periodic or even if the ${\cal G}-$values are bounded. Examples of games whose ${\cal G}-$sequence is arithmetic periodic can be found amongst {\em hexadecimal} games. (That is, games in which the heaps can be split into three. The exact rules are generalizations of the octal rules but with $d_j<16$.) For example, from [7], the ${\cal G}$-sequence for {\bf 0.137F} ({\bf F}=15) is 0, 1, 1, 2, 2, 3, 3,$\ldots$, where ${\cal G}(2m-1)={\cal G}(2m)=m$ for $m\geq 1$. In this case, the saltus is 1 and the period length is 2 or, in other words, ${\cal G}(n+2)={\cal G}(n)+1$ for $n\geq 1$. For hexadecimal games, another type of regularity is known to occur ([10]). The game {\bf 0.123456789} has the ${\cal G}-$sequence 0, 1, 0, 2, 2, 1, 1, 3, 2, 4, 4, 5, 5, 6, 4 and thereafter \[ {\cal G}(2m-1)={\cal G}(2m)=m-1, \, \rm{except }\, {\cal G}(2^{k}+6)=2^{k-1}.\] The games {\bf 0.71790A96D9BD024} and {\bf 0.1234567B33B} exhibit a similar regularity. Here {\bf A}$=1$, {\bf B}$=2$ etc. For more results on subtraction games, see [1,3]; on octal and similar games see [3,4,8,9]; on hexadecimal games see [7,10] Octal games with a pass move appeared when the first author investigated `Gale's Subset-Take-Away' game (see [6]). The sub-problem he considered was: Given a partial order known as a {\it fence} (or {\it zig-zag} see Figure \ref{fence}), a move is to either take a top element, or a bottom element along with any elements above it. \begin{figure}[h] \begin{center} \setlength{\unitlength}{0.15in} \begin{picture}(20,6)(0,0) \thicklines \put (0,0){\circle*{10}} \put (4,0){\circle*{10}} \put (8,0){\circle*{10}} \put (12,0){\circle*{10}} \put (16,0){\circle*{10}} \put (20,0){\circle*{10}} \put (2,4){\circle*{10}} \put (6,4){\circle*{10}} \put (10,4){\circle*{10}} \put (14,4){\circle*{10}} \put (18,4){\circle*{10}} \put (0,0){\line(1,2){2}} \put (4,0){\line(1,2){2}} \put (8,0){\line(1,2){2}} \put (12,0){\line(1,2){2}} \put (16,0){\line(1,2){2}} \put (2,4){\line(1,-2){2}} \put (6,4){\line(1,-2){2}} \put (10,4){\line(1,-2){2}} \put (14,4){\line(1,-2){2}} \put (18,4){\line(1,-2){2}} \end{picture} \end{center} \caption{A fence} \label{fence} \end{figure} An alternative way to view this game is to consider the minimal elements as a heap. Suppose that the fence ends in two minimal elements. A move in the maximal elements removes 0 and splits the heap into 2 non-empty heaps. A move in the minimals removes 1 and there could be 0, 1 or 2 heaps left. Each move results in heaps with minimals at the ends and therefore the game is equivalent to the octal game {\bf 4.7} which has ${\cal G}-$sequence $1,2,1,2,1,2 \ldots$. Further, if the fence ends with one maximal element and one minimal element then a move in this game can never create another maximal element at the end of a fence and it is easy to show that for $n\geq 0$, $${\cal G}(3n + i) = \left\{ \begin{array}{ll} 4n & i= 0, 2 \\ 4n+2 & i=1. \end{array} \right. $$ where $3n+i$ indicates the number of minimals in a fence. This ${\cal G}-$sequence is arithmetic periodic, specifically, ${\cal G}(n+3)={\cal G}(n)+4$. With the translation to the heap game, we have the same moves as before, however, taking the end maximal translates into a {\it pass} move and taking the minimal below the end maximal eliminates the pass move. Finally, if the fence ends with two maximal elements then it is now easy to show that the ${\cal G}-$sequence is $1,1,1,1,\ldots$. There are several immediate generalizations of this game but we concentrate on just one. A {\it p-octal} game is an octal game that has a pass move and the game is played according to the following rules. If the pass move has not been played then the next player can: 1: Throw away the pass move leaving every heap the same as before his move; or 2: Play a taking-and-breaking move as given by the octal game rules but he then either associates the pass move with a single non-empty heap or throws it away; or 3: If the pass move has been thrown away then the play continues as dictated by the octal game rules. Note that a pass move can never be created and that an empty heap cannot have a pass move associated with it. For a heap of size $n$, we use $\overline{n}$ to denote the p-octal game. The ${\cal G}-$sequence of a p-octal game can be periodic or arithmetic periodic. Moreover, we discovered a third type of regularity which is a hybrid between the two. A p-octal game is {\it split arithmetic periodic, periodic regular} or {\it sapp regular} for short, if there exist integers $e$, $s$, and $p$, and a set $S\subseteq \{0,1,2,\ldots, p-1\}$ such that \begin{itemize} \item ${\cal G}(\overline{i+p})={\cal G}(\overline{i})$ for $i>e$ and $(i \bmod p)\in S$, \item ${\cal G}(\overline{i+p})={\cal G}(\overline{i})+s$ for $i>e$ and $(i \bmod p)\not\in S$. \end{itemize} This paper presents theorems for testing p-octal games for sapp regularity, periodicity and arithmetic periodicity. The latter two are special cases of the first. We prove the sapp regularity theorem and state the other theorems, leaving the proofs to the reader. Note that each finite subtraction game, even with a pass-rule, has only a bounded number of options so that the ${\cal G}-$sequence cannot be arithmetico periodic. No one has found any sapp regular hexadecimal games. Furthermore, it is not known whether p-octal games exhibit any other regular behavior. \vskip 30pt \section*{\normalsize 2. Periodicity Theorems} The next theorems require that the underlying octal game be periodic. The reader may wish to prove that the finite octal game ${\bf d_0.d_1d_2\ldots d_k}$ is periodic with period length $p$ and last exceptional value at heap size $e$ if the period persists from heap sizes $e+1$ through $2e+2p+k$. (See [3].) {\bf Theorem 1. }{\it sapp regular p-octal games.} Let $\overline{G}$ be a finite p-octal game with the underlying octal game $G$ given by ${\bf d_0.d_1d_2\ldots d_k}$. If there exist integers $e$, $h$, $s$, $t$, and $p\geq k$, and a set $S \subseteq \{ 0, 1, 2, \ldots, p-1 \}$ such that $1$: ${\cal G}(n+p) = {\cal G}(n)$ for all $n>e$, $2$: $h$ is the least integer such that $2^{h}>\max\{{\cal G}(n),{\cal G}(\overline{j})\}$ for all $n$, and $j \leq e$ or $(j \bmod p)\in S$, $j\leq 2e+6p$; $3$: $s=t2^{h}$; $4$: ${\cal G}(\overline{n+p})={\cal G}(\overline{4})$ for $ee$, we have that ${\cal G}(\overline{n+p})={\cal G}(\overline{n})$ for $(n \bmod p)\in S$ and ${\cal G}(\overline{n+ p}) ={\cal G}(\overline{n}) +s$ for $(n \bmod p)\not\in S$. {\it Proof.} We assume that the result holds for heap sizes up to $n+p-1$ for some $n\geq 2e+5p+1$. Note that restriction on the saltus is artificial since this can be met by taking a sufficiently large multiple of the shortest period length. See the next section for an example. The cases $(n \bmod p) \in S$ and $(n \bmod p) \not\in S$ are considered separately. For $(n \bmod p) \in S$, we will show that every value $x < {\cal G} (\overline{n})$ is an excluded value for ${\cal G} (\overline{n+p})$, and that no option of $\overline{n+p}$ has ${\cal G}$-value equal to ${\cal G} (\overline{n})$. For $(n \bmod p) \not\in S$, we will show that every value $x < {\cal G} (\overline{n}) + s$ is an excluded value for ${\cal G} (\overline{n+p})$, and that no option of $\overline{n+p}$ has ${\cal G}$-value equal to ${\cal G} (\overline{n}) + s$. Throughout the proof, we will make use of the following observation: if $(m \bmod p) \not\in S$ and $ m>e + jp$ then ${\cal G}(\overline{m}) \geq js$. First, suppose that $(n \bmod p)\in S$ and let $0 \leq x < {\cal G} (\overline{n})$. Now $x$ is an excluded value for ${\cal G}(\overline{n})$ so there are nonnegative integers $a$ and $b$ such that $a+b=n-u$ for some $0\leq u \leq k$, and either ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x$ or ${\cal G}(a) \oplus {\cal G}(b) = x$ and so the move is permitted. If $b>e$ then ${\cal G}(b+p)={\cal G}(b)$ so either ${\cal G}(\overline{a}) \oplus {\cal G}(b+p) = {\cal G}(\overline{a}) \oplus {\cal G}(b)=x$ or ${\cal G}(a) \oplus {\cal G}(b+p) = {\cal G}(a) \oplus {\cal G}(b) = x$. Conversely, suppose that $b \leq e$. Now $a = n - u - b$ and since $n \geq 2e + 5p + 1$ and $u \leq k \leq p$, we have $a \geq e + 4p + 1$. Now if ${\cal G}(a)\oplus {\cal G}(b) = x$ then, as $a > e$, we have ${\cal G} (a+p) = {\cal G} (a)$ so ${\cal G}(a+p) \oplus {\cal G}(b) = x$. On the other hand, suppose that ${\cal G}(\overline{a})\oplus {\cal G}(b) = x$. Since we are assuming that $(n \bmod p) \in S$, we have $x = {\cal G} (\overline{n}) < s$, by condition 2. If $(a \bmod p) \not\in S$ then ${\cal G} (\overline{a}) \geq 4s$. But we also have $G(b) < s$ by condition 2, so now ${\cal G} (\overline{a}) \oplus {\cal G} (b) > s > x$, a contradiction. Therefore, $(a \bmod p) \in S$ and so ${\cal G}(\overline{a+p}) \oplus {\cal G}(b) = {\cal G}(\overline{a}) \oplus {\cal G}(b)=x$. In all cases, we have $a + b + p = (n+p) - u$ so $x$ is an excluded value for ${\cal G} (\overline{n+p})$, as desired. Secondly, suppose that $(n \bmod p) \not\in S$. Once again, let $x$ be an excluded value for ${\cal G}(\overline{n})$ with $0 \leq x < {\cal G}(\overline{n})$. As above, there are nonnegative integers $a$ and $b$ such that $a+b=n-u$ for some $0\leq u \leq k$, and either ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x$ or ${\cal G}(a) \oplus {\cal G}(b) = x$. Suppose, first of all, that $x \geq 2s = t 2^{h+1}$. We show that $x + s$ is an excluded value for ${\cal G}(\overline{n+p})$. In this case, $x$ contains a power of 2 greater than that contained by ${\cal G}(i)$ for any $i$, or by ${\cal G}(\overline{i})$, $0\leq i\leq e$, or by ${\cal G}(\overline{a})$, $(a\bmod p)\in S$. Therefore, neither the case ${\cal G}(a)\oplus {\cal G}(b) = x$ nor ${\cal G}(\overline{a})\oplus {\cal G}(b) = x$, $(a\bmod p)\in S$ may occur. Thus we must have $a > e$ and $(a \bmod p) \not\in S$. Now since $s=t2^{h}$ and ${\cal G}(b)<2^{h}$ have no powers of 2 in common, we have \begin{eqnarray*} {\cal G}(\overline{a+p})\oplus {\cal G}(b) &=& ({\cal G}(\overline{a})+s) \oplus {\cal G}(b)\cr &=& ({\cal G}(\overline{a})\oplus {\cal G}(b))+s\cr &=&x+s \end{eqnarray*} Therefore, every value in the set $\{ 3s, 3s+1, \ldots, {\cal G}(\overline{n})+s-1 \}$ is an excluded value for ${\cal G}(\overline{n+p})$. Now let $x$ be a nonnegative integer less than $3s$. We will now show that $x$ is an excluded value. Note that, since $n \geq 2e + 5p + 1$, ${\cal G}(\overline{n}) \geq 5s$ so $\overline{n}$ has an option with value $x$. Therefore, there are nonnegative integers $a$ and $b$ such that $a + b = n - u$ for some $0 \leq u \leq k$, and either ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x$ or ${\cal G}(a) \oplus {\cal G}(b) = x$. Suppose that ${\cal G}(a) \oplus {\cal G}(b) = x$. Since $a + b = n - u \geq (2e + 5p + 1) - p = 2e + 4p + 1$, clearly at least one of $a$ or $b$ is greater than $e$. Without loss of generality, we may take $b > e$, then we have ${\cal G}(a) \oplus {\cal G}(b+p) = {\cal G}(a) \oplus {\cal G}(b) = x$. On the other hand, suppose that ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x$. Then ${\cal G}(\overline{a}) = x \oplus {\cal G}(b) < x + {\cal G}(b) < 3s + s = 4s$ so $a \leq e + 4p$. As above, $a + b = n - u \geq 2e + 4p + 1$ so $b \geq e+1$ and thus ${\cal G}(\overline{a}) \oplus {\cal G}(b+p) = {\cal G}(\overline{a}) \oplus {\cal G}(b) = x$. Therefore, all $0 \leq x < 3s$ are excluded values for ${\cal G}(\overline{n+p})$ so we have shown that every value less than ${\cal G}(\overline{n})+s$ is an excluded value. Once again, suppose that $(n \bmod p) \in S$. We now show that $x = {\cal G}(\overline{n})$ is not an excluded value for ${\cal G}(\overline{n+p})$. To the contrary then, suppose that there are nonnegative integers $a$ and $b$ with $a + b = n + p - u$ such that ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x$ or ${\cal G}(a) \oplus {\cal G}(b) = x$. If $b > e + p$ then ${\cal G}(b-p) = {\cal G}(b)$ so either ${\cal G}(\overline{a}) \oplus {\cal G}(b-p) = x$ or ${\cal G}(a) \oplus {\cal G}(b-p) = x$. Since $a + b - p = n - u$, we have produced an option of $\overline{n}$ with value $x = {\cal G}(\overline{n})$ which is impossible. Conversely, if $b \leq e+p$ then $a \geq e + 2p + 1$. If ${\cal G}(a) \oplus {\cal G}(b) = x$ then, since $a > e + p$, we have ${\cal G}(a - p) = {\cal G}(a)$ so ${\cal G}(a-p) \oplus {\cal G}(b) = x$. On the other hand, suppose that ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x$. As was shown earlier, we must have $(a \bmod p) \in S$ so ${\cal G}(\overline{a-p}) = {\cal G}(\overline{a})$ and therefore, ${\cal G}(\overline{a-p}) \oplus {\cal G}(b) = x$. In either case, we have an option of $\overline{n}$ having value ${\cal G}(\overline{n})$ which is impossible. Thus, when $(n \bmod p) \in S$, ${\cal G}(\overline{n})$ is an excluded value for ${\cal G}(\overline{n+p})$. Finally, suppose that $(n \bmod p) \not\in S$. We show that ${\cal G}(\overline{n}) + s$ is an excluded value for ${\cal G}(\overline{n+p})$. Once again, suppose that there are nonnegative integers $a$ and $b$ with $a + b = n + p - u$ such that ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x + s$ or ${\cal G}(a) \oplus {\cal G}(b) = x + s$ where $x = {\cal G}(\overline{n})$. Since $(n \bmod p) \not\in S$ and $n \geq 2e + 5p + 1$, we have $x = {\cal G}(\overline{n}) \geq 5s$ and so neither the case ${\cal G}(a) \oplus {\cal G}(b) = x + s$ nor ${\cal G}(\overline{a}) \oplus {\cal G}(b) = x + s$, $(a \bmod p) \in S$ may occur. Therefore, $(a \bmod p) \not\in S$ and $a \geq e + p + 1$ by condition 6. Since $s = t 2^h$ and ${\cal G}(b) < 2^h$ have no powers of 2 in common, $$ {\cal G}(\overline{a-p}) \oplus {\cal G}(b) = ({\cal G}(\overline{a}) - s) \oplus {\cal G}(b) = ({\cal G}(\overline{a}) \oplus {\cal G}(b)) - s = (x+s)-s = x = {\cal G}(\overline{n}) . $$ But $(a-p) + b = n - u$ so we have an option of $\overline{n}$ having value ${\cal G}(\overline{n})$ which is a contradiction. Therefore, when $(n \bmod p) \in S$, ${\cal G}(\overline{n}) + s$ is an excluded value for ${\cal G}(\overline{n+p})$. The proof is now complete. \hfill$\Box$ This result can be used to determine whether the ${\cal G}-$sequence is periodic, i.e., $S=\{0,1,2,\ldots,p-1\}$ or arithmetic periodic, i.e. $S =\emptyset$. However, in testing for just periodicity the bounds can be sharpened. We leave the proof to the reader. {\bf Corollary 1.} {\it Periodic p-octal games.} Let $\overline{G}$ be a finite p-octal game with the underlying octal game $G$ given by ${\bf d_0.d_1d_2\ldots d_k}$. If there exist integers $e$ and $p$ such that $1$: ${\cal G}(n+p) = {\cal G}(n)$ for all $n>e$, and $2$: ${\cal G}(\overline{n+p})={\cal G}(\overline{n})$ for $e e$. \vskip 30pt \section*{\normalsize 3. An Example} Consider the p-octal game {\bf 0.516}. The first 52 ${\cal G}-$values are: \begin{verbatim} 2 2 2 4 4 4 6 6 8 4 4 10 8 8 8 12 12 12 11 14 15 8 12 12 11 16 15 8 18 12 11 16 15 8 20 12 11 22 15 8 20 12 11 24 15 8 26 12 11 24 15 8 \end{verbatim} Taking $e = 16, h = 4, p = 36, s = 16$ and $$ S = \{ 0, 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 22, 24, 25, 27, 28, 30, 31, 33, 34 \} $$ we show that this game satisfies the conditions of Theorem 1. \begin{enumerate} \item The underlying octal game is periodic with ${\cal G}-$sequence $1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 2, 2, \ldots$ so indeed ${\cal G}(i+36) = {\cal G}(i)$ for all $i \geq 16$. \item We have $\max \{ {\cal G}(i) \} = 2$. For $j \leq 16$ $\max \{ {\cal G}(\overline{j}) \} = 12$, and for $(j \bmod 36) \in S$ $\max \{ {\cal G}(\overline{j}) \} = 15$. Thus $2^h = 2^4 = 16$ exceeds all these maxima as required. \item We take $t = 1$ so $s = 2^4 = 16$. \item The periodic behaviour may be seen to hold up to a heap size of $2e + 6p = 248$. \item The arithmetic periodic behaviour may be seen to hold up to a heap size of $2e + 6p = 248$. \item For $i \leq 52$, $\max \{ {\cal G}(\overline{i}) \} = 26$ (at $i = 47$) which is less than $5s = 80$. \end{enumerate} Therefore, we conclude that, for $i > 16$, $$ {\cal G}(\overline{i + 36}) = \left\{ \begin{array}{ll} {\cal G}(\overline{i}) & (i \bmod {36}) \in S \\ {\cal G}(\overline{i}) + 16 & (i \bmod {36}) \not\in S. \\ \end{array} \right. $$ Note: $h = 4$ is the smallest value that will work in condition 2. This led to $s = 16$ and $p = 36$. In fact, however, the ${\cal G}-$sequence for this game is sapp with period 18 and saltus 8. \vskip 30pt \section*{\normalsize 4. ${\cal G}-$sequences}\label{Tables} These tables cover all the 3-digit p-octal games where the underlying octal game has a period less than 10 with a pre-period length of no more than 30. We use $A=10$, $B=11$, etc., and the dots signify the beginning and end of the period. In octal and hexadecimal games there is a standard form, essentially no game beginning with an even number has to be considered. No equivalent standard form exist for p-octal games. Table 1 contains some examples of periodic p-octal games. Tables 2 and 3 list, respectively, arithmetic periodic and sapp regular games; We also found several examples of 4-digit p-octal games which are arithmetic periodic or sapp regular; many of these, however, are equivalent to 3-digit games. \vskip 30pt \begin{tabular}{lcccl} &&&&{\bf Table 1: Examples of Periodic P-octal Games}\cr \cr Game & e&p & Saltus &First Nim-values \cr \hline\cr {\bf0.07}&124&34 &0&122334455647554\cr {\bf0.15}& 22&10&0& $2212244244 66488442A7 8\dot8788442C7\dot B$\cr {\bf0.17}&118&34&0& $2234254257$\cr {\bf0.26}&3&4&0&$123\dot456\dot7 $\cr {\bf 0.34}&16&8&0&$ 2324324523$\cr {\bf0.35}&6&6&0&$231243\dot46424\dot6 $\cr {\bf0.44}&396&24&0 &112233445566778\cr {\bf0.45}&730&20&0&$11243564758897A$ \cr {\bf0.51}&0&1&0 &$\dot2\dot 2$\cr {\bf0.52}&1&4&0&$ 2\dot 143\dot 6 $\cr {\bf0.53}&24&9&0&$2244614471$\cr {\bf0.54}&27&7&0&$2124446688$\cr {\bf0.57}&2&6&4&$ 22\dot 44664\dot4 $\cr {\bf0.71}&5&2&0&$ 23452\dot 5\dot4 $\cr {\bf0.72}&8&4&0&$ 23456745\dot 861A\dot 4$\cr {\bf0.75}&1&4&4&$2\dot 345\dot 4$\cr {\bf4.12}&8&7&0&$22441738\dot7486A4\dot7$\cr {\bf4.3}&2&2&0&$22\dot3\dot1$\cr {\bf4.32}&1&4&0&$2\dot465\dot7$\cr {\bf4.7}&4&3&4&$2453\dot 8A\dot8$\cr {\bf4.72}&4&3&0&$2468\dot A7\dot9$\cr \end{tabular} \newpage For the next two tables, many games have the same $\cal{G}-$sequence. We use the following shorthand in the game name to designate a set of games. $$ \begin{array}{ccc} \begin{array}{rcl} {\bf m} & = & 5, 7 \\ {\bf n} & = & 4, 5 \\ {\bf p}& = & 0, 1, 4, 5 \end{array} & \begin{array}{rcl} {\bf q }& = & 4, 5, 6, 7\\ {\bf r }& = & 0, 1, 2, 3, 4, 5, 6, 7 \\ {\bf s }& = & 1, 5 \end{array} & \begin{array}{rcl} {\bf t} & = & 6, 7 \\ {\bf u }& = & 2, 3 \\ {\bf v }& = & 4, 5 \end{array} \end{array} $$ \vskip 30pt \begin{tabular}{lcccl} &&&&{\bf Table 2: Arithmetic periodic P-octal Games}\cr \cr Game & e&p & Saltus &First Nim-values \cr \hline\cr {\bf0.157}&3&9&4&$222 \dot4 4 4 6 6 6 4 4 \dot 4$\cr {\bf0.175}&2&6&4&$22 \dot3 4 4 5 6 \dot4$\cr {\bf0.315}&3&10&4&$234 \dot2 4 5 2 4 6 5 4 6 \dot4$\cr {\bf0.335}&2&8&4&$23 \dot4 1 2 4 6 5 4 \dot6$\cr {\bf0.35m}&0&5&4&$\dot2 3 4 5 \dot4$\cr {\bf0.53n} {\bf0.57p}&2&6&4&$22 \dot4 4 6 6 4 \dot4$\cr {\bf0.72q}&2&6&4&$23 \dot4 5 6 7 4 \dot5$\cr {\bf0.75r}&1&4&4&$2 \dot3 4 5 \dot4$\cr {\bf4.spt}&3&15&12&$222 \dot4 4 4 6 8 8 4 A C 8 8 E C C \dot{C}$\cr {\bf4.stp} {\bf4.5uv}&2&8&8&$2 2 \dot4 4 6 8 4 A 8 \dot8$\cr {\bf4.stt} {\bf4.5ut}&2&3&4&$2 2 \dot4 4 \dot6$\cr {\bf4.3pm}&1&5&4&$2 \dot4 6 4 6 \dot4$\cr {\bf4.7pr}&1&3&4&$2 \dot4 6 \dot4$\cr {\bf4.7tp}&0&1&2&$\dot2$\cr \end{tabular} \vskip 10pt Note: {\bf 4.spt} shows that the saltus need not be a power of 2. \vskip 30pt \begin{tabular}{lcccl} &&&&{\bf Table 3: Sapp Regular P-octal Games}\cr \cr Game & e&p & Saltus &First Nim-values \cr \hline\cr {\bf0.5st}&16&18&8&$22244466844A888C \dot{{\bf C}} C B {\bf E} F 8 {\bf C} C B {\bf G} F 8 {\bf I} C B {\bf G} F \dot8 \; $\cr {\bf4.1uv}&6&12&8&$224468 \dot{{\bf 4}} 7 {\bf 8} 4 {\bf A} 7 {\bf 8} 4 {\bf C} 7 {\bf E} \dot4$\cr \end{tabular} \vskip 10pt Note: Within the period, the bold face numbers are arithmetic periodic. \newpage \section*{\normalsize References.} \footnotesize \parindent=0pt \parskip =5pt [1] I. Alth\"ofer, J. B\"ultermann, Superlinear period lengths in some subtraction games. Theoret. Comput. Sci. 148 (1995) pp. 111--119 [2] R. B. Austin, {\it Impartial and Partizan Games,} M.Sc. Thesis, The University of Calgary, 1976. [3] E. Berlekamp, J. H. Conway, R. K. Guy, {\it Winning Ways for your mathematical plays} Vol. {\bf 1}, 2nd edition, AKPeters, 2001 (1st edition, Academic Press, 1982). [4] I. Caines, C. Gates, R. K. Guy, R. J. Nowakowski, Periods in taking and splitting games, {\it Amer. Math Monthly} {\bf 106}, 359-361. [5] J. H. Conway, {\it On Numbers and Games,} AKPeters, 2001. [6] R. J. Guy, Unsolved Problems in Combinatorial Game Theory, {\it Games of No Chance}, R.J. Nowakowski Ed., Mathematical Sciences Research Institute Publications {\bf 29} 329-337, Cambridge University Press, 1996. [7] S. Howse, R. J. Nowakowski, Periodicity and Arithmetic-periodicity in Hexadecimal Games, to appear in J. Theoretical Comp. Sci. [8] A. Flammenkamp, Sprague-Grundy values of some octal games:\\ {\it wwwhomes.uni-bielefeld.de/achim/octal.html}. [9] A. Gangolli; T. Plambeck, A note on periodicity in some octal games. Internat. J. Game Theory {\bf 18} (1989) pp. 311--320. [10] R.~J.~Nowakowski, Regularity in hexadecimal games, preprint. \end{document} {\it Proof.} \hfill $\Box$