# Game values of arithmetic functions

Douglas E. Iannucci111University of the Virgin Islands. and Urban
Larsson222National University of Singapore<EMAIL_ADDRESS>
###### Abstract

Arithmetic functions in Number Theory meet the Sprague-Grundy function from
Combinatorial Game Theory. We study a variety of 2-player games induced by
standard arithmetic functions, such as Euclidian division, divisors,
remainders and relatively prime numbers, and their negations.

## Introduction

Consider the following situation: two players, Alice and Bob, alternate to
partition a given finite number of positive integers into components of the
form of a non-trivial Euclidian division. Whoever will fail to follow the
rule, because each number is a “1”, loses the game. You are only allowed to
split one number at a time. For example, if Alice starts from the number $7$,
then her options are $1+\cdots+1$, $2+2+2+1$, $3+3+1$, $4+3$, $5+2$ and $6+1$;
here the ‘+’ sign from arithmetic functions becomes the disjunctive sum
operator (a convenient game component separator) in the game setting. By
observing that we may remove any pair of the same numbers (by mimicking
strategy), and we may remove a one unless the option is the terminal position
(since its set of options is empty), the set of options from $7$ simplifies to
$\\{1,2,4+3,5+2,6\\}$. Suppose now that Alice starts playing from the
disjunctive sum $7+2$. By the above analysis its easy to find a winning move
to $2+2+2+1+2$. What if she instead starts from the composite game $7+3$?

We study 2-player normal-play games defined with the nonnegative or positive
integers as the set of positions. The two players alternate turns and if a
player has no move option then he/she loses. At each stage of game, the move
options are the same independent of who is to play. In combinatorial game
theory, this notion is referred to as impartial. Games terminate in a finite
number of moves, and there is a finite number of options from each game
position; i.e., games are short. This allows us to use the famous theory
discovered independently by Sprague [8] and Grundy [4], which generalizes
normal-play nim, analyzed by Bouton [2], into disjunctive sum play of any
finite set of impartial normal-play games.

Arithmetic functions are at the core of number theory, in a similar sense that
nim and Sprague-Grundy are central to the theory of combinatorial games. We
consider arithmetic functions [5] of the form $f:X\rightarrow Y$, where the
set $X$ is either the nonnegative integers, $\mathbb{N}_{0}=\\{0,1,\ldots\\}$,
or the positive integers, i.e., the natural numbers
$\mathbb{N}=\\{1,2,\ldots\\}$, and where typically $Y=2^{X}$ is the set of all
subsets of the nonnegative or positive integers respectively. In some
settings, for example when the arithmetic function is counting the instances
of another arithmetic function, we may take $Y=\mathbb{N}_{0}$; in these
cases, we will refer to $f$ as a counting function, and the games as counting
games.

Arithmetic functions may conveniently be interpreted as rulesets of impartial
games, and here we present old and novel games within a classification scheme.
Each arithmetic function induces a couple of rulesets, and we let
$\mbox{opt}:X\rightarrow Z$, define the set of move options from $n\in X$,
given some arithmetic function $f$, with sometimes an imposed terminal sink,
or a modified codomain, for example, in the powerset games to come,
$Z=2^{2^{X}}$; in the singleton and counting game cases we may take $Z=Y$
(modulo sometimes adjustment for $0$).

More specifically, we interprete the arithmetic functions in terms of heap
games; for each game position, i.e., heap size represented by a number (of
pebbles). There are two main variations.

  * •

A player can _move-to_ a number or a disjunctve sum of numbers, induced by the
arithmetic function.

  * •

A player can _subtract_ a number or a disjunctive sum of numbers, induced by
the arithmetic function.

We will use the name of the arithmetic function and prepend the letters M or
S, respectively, for the move-to and the subtract versions of a particular
game. The following two examples are excerpts from Section 1.1.

######  Example 1.

If the players may move-to a divisor, we get for example: from $\mathrm{6}$
the options are $1$,$2$ and $3$. From $7$ you may only move to $1$. Here, the
divisors must be proper divisors.

######  Example 2.

If the players may subtract a divisor, we get for example: from $6$, the
options are $5,4,3$ and $0$. From $7$ you can move to $0$ or $6$.

Before this paper, instances where number theory connects with impartial games
might individually have seemed like ‘lucky cases’. However, we feel that the
relatively large number of such examples justifies a more systematic
study.333See classical works such as Winning Ways [1] for results on impartial
games coinciding with number theory.

Let us list some game rules induced by some standard arithmetic functions.
When there is only one single option, we may omit the set brackets.

  1. 1.

The aliquot (divisor) games:

    1. (a)

maliquot. Move-to a proper divisor of your number; i.e.,

$\mbox{opt}(n)=\\{d:d\mid n,\;0<d<n\\}.$

    2. (b)

saliquot. Subtract a divisor of your number; i.e.,

$\mbox{opt}(n)=\\{n-d:d\mid n,\;d>0\\}.$

  2. 2.

The aliquant (nondivisor) games:

    1. (a)

maliquant. Move-to a nondivisor of your number; i.e.,

$\mbox{opt}(n)=\\{k:1\leq k\leq n,\;k\nmid n\\}.$

    2. (b)

saliquant. Subtract a nondivisor of your number; i.e.,

$\mbox{opt}(n)=\\{n-k:1\leq k\leq n,\;k\nmid n\\}.$

  3. 3.

The $\tau$-games:444Here $\tau(n)$ counts the natural divisors of $n$:
$\tau(n)=\sum_{d\mid n}1$. The divisor function $\tau$ is multiplicative, with
$\tau(p^{a})=a+1$ for all primes $p$ and natural numbers $a$. In one of our
game settings, we use instead the number of proper divisors, and so let
$\tau^{\prime}=\tau-1$, so that in particular $\tau^{\prime}(1)=0$ and
$\tau^{\prime}(2)=1$ (here we lose multiplicativity).

    1. (a)

mtau. Move-to the number of proper divisors of your number; i.e.,

$\mbox{opt}(n)=\tau^{\prime}(n).$

    2. (b)

stau. Subtract the number of divisors of your number; i.e.,

$\mbox{opt}(n)=n-\tau(n).$

  4. 4.

The totative (relative prime residue) and the nontotative games:555The ‘move-
to’ and ‘subtract’ variations are the same, because $(k,n)=1$ if and only if
$(n-k,n)=1$.

    1. (a)

totative. Move-to any relatively prime residue; i.e.,

$\mbox{opt}(n)=\\{k:1\leq k\leq n:(k,n)=1\\}.$

    2. (b)

nontotative. Move-to any smaller residue that is not relatively prime to your
number; i.e.,

$\mbox{opt}(n)=\\{k:1\leq k<n:(k,n)>1\\}.$

  5. 5.

The totient ($\phi$) games:

    1. (a)

totient. Move-to the number of relatively prime residues modulo your number;
i.e.,

$\mbox{opt}(n)=\phi(n).$

    2. (b)

nontotient. Instead subtract this number; i.e.,

$\mbox{opt}(n)=n-\phi(n).$

  6. 6.

dividing. Divide your number into a maximum number of equal parts, at least
two; i.e.,

$\mbox{opt}(n)=\\{\;\underbrace{k+k+\cdots+k}_{m\;\text{$k$'s}}:km=n,\;m>1\\}.$

  7. 7.

dividing-and-remainder. Divide your number into a number of equal parts and a
remainder, which is smaller than the other parts and possibly 0; i.e.,

$\mbox{opt}(n)=\\{\,\underbrace{k+k+\cdots+k+r}_{m\;\text{$k$'s}}\\}:km+r=n,\;m>0,\;0\leq
r<k\,\\}.$

This game has two simpler variations, as defined in Section 3.2.

  8. 8.

factoring. Factor your number into at least two components, and at most the
number of prime factors, counting multiplicity; i.e.,

$\mbox{opt}(n)=\\{a_{1}+a_{2}+\cdots+a_{k}:1<a_{1}\leq a_{2}\leq\cdots\leq
a_{k},\,a_{1}a_{2}\cdots a_{k}=n\,\\}.$

Item 7 here is the game in the first paragraph of the paper. The goal of this
paper is to evaluate the nim-values, a.k.a. Sprague-Grundy values, of these
games, and hence winning strategies can be computed, via the nim-sum operator,
in disjunctive sum with any other normal-play game. The nim-values of a
ruleset are defined via the _minimal excludant function_ ,
$\mbox{mex}:2^{X}\rightarrow\mathbb{N}_{0}$, where $X$ is the set of
nonnegative (or positive) integers. Let $A\subset\mathbb{N}_{0}$ be a strict
subset of the nonnegative integers. Then
$\mbox{mex}(A)=\min\\{x:x\in\mathbb{N}_{0}\setminus A\\}$ and
$\mathcal{SG}(n)=\mbox{mex}\\{\mathcal{SG}(x):x\in\mbox{opt}(n)\\}$. Note
that, if there is no move option from $n$, then $\mathcal{SG}(n)=0$. Recall
that the nim-sum is used to compute the nim-value of a disjunctive sum of
games, i.e., $\mathcal{SG}(\sum n_{i})=\bigoplus\mathcal{SG}(n_{i})$, where
‘$\sum$’ is disjunctive sum operator, and ‘$\bigoplus$’ is the sum modulo $2$
without carry of the numbers $n_{i}$ in their binary representations.

If $f$ is a counting function, then there is exactly one option. The game on a
single heap reduces to a trivial she-loves-me-she-loves-me-not game, and in
particular, the $\mathcal{SG}$-function reduces to a binary output, that is,
$\mathcal{SG}(n)\in\\{0,1\\}$. Hence, such rulesets will be referred to as
binary rulesets. The same game, however, played on several heaps, with at
least one non-binary ruleset, can be highly non-trivial, and result in great
complexity. The question of which heap to move on does not have a polynomial
time solution in general, while many arithmetic functions are known to be
intractable. Our inspiration for studying binary counting games came from
Harold Shapiro’s classification for the recurrence of the totient function
[6]. A couple of examples will clarify these type of issues.

######  Example 3.

Let $0$ be the empty heap. Suppose that, from a heap of size $n>0$, the
players can remove the number of divisors of $n$. The option of $n=1$ is $0$.
A heap of size 2 also has $0$ as an option, but $1$ is the option of $3$. The
$\mathcal{SG}$-sequence thus starts: $0,1,1,0,0,1$. The heap of size 5 has $3$
as the option, for which the nim-value is $0$. On one heap, while play is
trivial, the problem of determining the winner is as hard as the complexity of
the sequence.

######  Example 4.

Let $0$ be the empty heap. Suppose that, from a heap of size $n>0$, the
players can move-to the number of proper divisors of $n$. The option of $n=1$
is $0$. The heaps of size two and three have moves to the heap with a single
pebble. The number of proper divisors of $n=4$ is $2$, and hence the option is
$2$. As for all primes, the option of $n=5$ is the heap of size one. Thus, the
$\mathcal{SG}$-sequence starts: $0,1,0,0,1,0$.

######  Example 5.

Consider binary games. Of course, even playing a disjunctive sum of binary
games, gives only binary values. Consider, for example totient, where
$\mathcal{SG}(2+3+4+5)=\mathcal{SG}(2)\oplus\mathcal{SG}(3)\oplus\mathcal{SG}(4)\oplus\mathcal{SG}(5)=1\oplus
0\oplus 0\oplus 1=0$. Hence $2+3+4+5$ is a second player winning position. To
see this in play, suppose that the first player selects the heap of size $4$
and moves to $2+3+\phi(4)+5=2+3+2+5$. Now, $\mathcal{SG}(2+3+2+5)=1\oplus
0\oplus 1\oplus 1=1$, which is a winning position for the player to move, and
indeed, since every move changes the parity, we have automatic, ‘random’
optimal play even if we play a sum of games, _provided_ that they are all
binary. In particular if we play a disjunctive sum of totient games, then the
optimal strategy is to play any move. Hence these games seem less interesting
in that respect, as 2-player games, but suppose that we instead play a
disjunctive sum of the totient game $G$ with the totative game $H$. Now an
efficient algorithm for computing the binary value (see Theorem 8) is
interesting again. What is a sufficient move in the first player winning
position $7_{{\rm totient}}+7_{{\rm totative}}$? (There are exactly three
winning moves.)

Those examples motivate play on arithmetic counting functions. Other examples
of binary games are the fullset games, where each move is defined by playing
to a disjunctive sum of all numbers induced by the arithmetic function.

For the powerset rulesets, the range of the opt function is the set of all
subsets of natural numbers, a generic game on a single heap decomposes to play
on several heaps. Hence, the full $\mathcal{SG}$-function is intrinsically
motivated in the solution of a single game, even if the starting position is a
single heap.

######  Example 6.

Consider the game played from a heap of size $n$, where the options are to
play to any non-empty set of proper divisors of $n$. If $n=6$, then the
options are the single heaps of size $1,2,3$ respectively, the pairs of heaps
$1+2,1+3,2+3$, and the triple $1+2+3$. A heap of size one has no option, and a
heap of size two or three has a heap of size one as option. Hence
$\mathcal{SG}(6)=2$. The nim-value of each prime is one, and so on.

######  Example 7.

Consider the game played from a heap of size $n$, where the options are to
play to any finite set of relatively prime residues smaller than $n$. If
$n=5$, then the options are all nonempty subsets of $\\{1,2,3,4\\}$. In spite
of the relatively large number of options, in this particular case, the
$\mathcal{SG}$-computation becomes easy. A heap of size one has no option and
so $\mathcal{SG}(1)=0$. Therefore, $\mathcal{SG}(2)=1$, and so
$\mathcal{SG}(3)=2$. A heap of size $4$ has $1,3,1+3$ as options, and so
$\mathcal{SG}(4)=1$. By this, obviously $\mathcal{SG}(5)=4$. A heap of size
$6$ has few options, and easily $\mathcal{SG}(6)=1$. A heap of size $7$ has
many options, and likewise easily $\mathcal{SG}(7)=8$, the smallest unused
power of two. This game is revisited in Theorem 17.

In view of the above examples, we use the following classification of games on
arithmetic functions; an _arithmetic game_ satisfies one of these items.

  * (i)

Play singletons from the arithmetic property;

  * (ii)

Play the number of elements from the arithmetic property;

  * (iii)

Play the disjunctive sum of all numbers from the arithmetic property;

  * (iv)

Play any non-empty subset of numbers from the arithmetic property, as a
disjunctive sum.

The word “Play …” (read: “Play is defined by…”) is intentionally left open for
interpretation. Here, it will have one out of two meanings; either the players
move-to the numbers, or they subtract the numbers, from the given heap (size).
The items (iii) and (iv) typically split a heap into several heaps to be
played in a disjunctive sum of heaps. Note that (iii) is binary, although it
does not concern counting functions. The rulesets induced by (iii) and (iv)
above are not listed above, but naturally build on items 1, 2 and 4. We define
them in their respective sections.

Some arithmetic functions directly induce a disjunctive sum of games, such as
the division algorithm or the factoring problem. For the ruleset on Euclidian
division from the first paragraph (Section 3.1), we conjecture that the
relative nim-values, $\mathcal{SG}(n)/n$, tend to 0 with increasing heap
sizes.

In Section 1, we study singleton games. In Section 2, we study counting games.
In Section 3, we study dividing games, where division induces a disjunctive
sum of games, and similar for Section 4 with factoring games. In Section 5, we
study disjunctive sum games on the full set induced by the arithmetic
function. In Section 6, we study powerset disjunctive sum games. Section 7 is
devoted to some future direction.

For reference, let us include a table of studied rulesets, in the order of
appearance, including some significant properties. The abbreviations are m-t:
move-to, subtr.: subtraction, div.:divisor, rel.:relative, n.:number, pr.:
problem, disj.: disjunctive. The solution functions are defined in the
respective sections, but let us list them here as well. In particular, we
encounter indexing functions, where numbers with a certain property are
enumerated, starting with $1$ for their smallest member, etc. In the table we
find the following functions $\Omega$: number of prime divisors counted with
multiplicity, $\omega$: the number of prime divisors counted without
multiplicity, $\Omega_{2}$: the number of prime divisors counted with
multiplicity, unless the divisor is 2, which is counted without multiplicity,
$v$: usual 2-valuation, $i_{o}$: index of largest odd divisor, $i_{p}$: index
of smallest prime divisor,

Ruleset | description | arithmetic f. | solution f. | Sec.
---|---|---|---|---
maliquot | m-t div. | aliquot | $\Omega$ | 1.1.1
saliquot | subtr. div. | aliquot | $v$ | 1.1.2
maliquant | m-t non-div. | aliquant | $i_{o}$ | 1.2.1
saliquant | subtr. non-div. | aliquant | partial sol. | 1.2.2
totative | m-t rel. prime | totative | $i_{p}$ | 1.3
nontotative | m-t nonrel. prime | totative | partial sol. | 1.4
totient | m-t n. rel. prime | totient | Shapiro | 2.1.1
nontotient | m-t num. nonrel. prime | totient |  | 2.1.2
mtau | m-t n. div. | $\tau$ | observation | 2.2.1
stau | subtr. n. div. | $\tau$ |  | 2.2.2
m$\Omega$ | m-t n. prime div. | $\Omega$ | observation | 2.3.1
s$\Omega$ | subtr. n. prime div. | $\Omega$ |  | 2.3.2
m$\omega$ | m-t n. dist. prime div. | $\omega$ | observation | 2.3.3
s$\omega$ | subtr. n. dist. prime div. | $\omega$ |  | 2.3.4
dividing | m-t disj. sum div. | aliquot | $\Omega_{2}$ | 3.1
div.-and-res. | m-t disj. sum Eucl. div. | Eucl. div. |  | 3.2
compl.-grundy | m-t disj. sum Eucl. div. | Eucl. div. |  | 3.2
div.-throw-res. | m-t disj. sum Eucl. div. | Eucl. div. | $i_{o}$ | 3.2
res.-throw-div. | m-t residue | Eucl. div. | yes | 3.2
m-factoring | m-t factoring | factoring | $\Omega$ | 4
s-factoring | subtr. factoring | factoring |  | 4
fs maliquot | m-t disj. sum all div. | aliquot | square free | 5
ps maliquot | m-t disj. sum div. | aliqout |  | 6
ps saliquot | subtr. disj. sum div. | aliqout | $v$ | 6
ps maliquant | m-t disj. sum div. | aliquant | $i_{o}$ | 6
ps saliquant | subtr. disj. sum div. | aliquant | $i_{p}$ | 6
ps totative | m-t disj. sum div. | totative |  | 6
ps nontotative | m-t disj. sum div. | totative |  | 6

##  1 Singletons

This section concerns items 1,2 and 4 from the introduction, the aliquots, the
aliquants and the totatives.

###  1.1 The aliquots

The first game, maliquot, is ‘nim in disguise’ (think of the prime factors of
a number as the pebbles in a heap) but since the factoring problem is hard,
the game is equally hard. Here, the arithmetic function is
$f(n)=\\{d:d\,|\,n,n\in\mathbb{N}_{0}\\}$. In this section, the set of game
positions is $\mathbb{N}$. Since all nonnegative integers divide 0, we do not
admit 0 to the set of game positions. The second game, saliquot, turns out to
be somewhat more interesting.

Let $n\in\mathbb{N}$. Then $\Omega(n)$ is the number of prime factors of $n$,
counting multiplicities, and $v=v(n)$ is the 2-valuation of $n=2^{v}m$, where
$m$ is odd.

####  1.1.1 maliquot, move-to a proper divisor

Here, the set of move options from $n$ is $\mbox{opt}(n)=\\{d:d\,|\,n,d\neq
n,n\in\mathbb{N}\\}$.

######  Example 8.

From 6 you have the options $1$, $2$ and $3$. From $7$ you may only move-to
$1$.

The unique terminal position is $1$. It follows that $\mathcal{SG}(1)=0$, and
if $p$ is a prime then $\mathcal{SG}(p)=1$. We have computed the first few
nim-values.  $n$ $\mbox{opt}(n)$ $\mathcal{SG}(n)$ 1 $\varnothing$ 0 2 1 1 3 1
1 4 1,2 2 5 1 1 6 1,2,3 2 7 1 1 8 1,2,4 3

######  Theorem 1.

Consider maliquot. Then, for all $n$, $\mathcal{SG}(n)=\Omega(n)$.

###### Proof.

We have that $0=\mathcal{SG}(1)=\Omega(1)$, since there are no options from
$1$, and $1$ does not have any prime factors. Suppose that $n>1$ has $k$ prime
factors, counting multiplicities. Then, for each $x\in\\{1,\ldots,k-1\\}$,
there is a divisor of $n$, corresponding to a move-to a number with $x$ prime
factors. Since you are not allowed to divide by $n$, the number of prime
factors decreases by moving, and so there is no option of nim-value $k$, by
induction. By the mex-rule, the result holds, $\mathcal{SG}(n)=k=\Omega(n)$. ∎

####  1.1.2 saliquot, subtract a divisor

This game is defined on the nonnegative integers, $\mathbb{N}_{0}$. Here

$\mbox{opt}(n)=\\{n-d:\;d\,|\,n,\,d>0\\}.$

######  Example 9.

The options of $6$ are $5$, $4$, $3$ and $0$. From $7$ you can move to $0$ or
$6$.

Since $0$ is always an option from $n$, it is clear that the nim-value of a
non-zero position is greater than $0$. The initial nim-values are:  $n$
$\mbox{opt}(n)$ $\mathcal{SG}(n)$ 0 $\varnothing$ 0 1 0 1 2 0,1 2 3 0,2 1 4
0,2,3 3 5 0,4 1 6 0,3,4,5 2 7 0,6 1 8 0,4,6,7 4 As the table indicates, the
nim-values concern the 2-valuation of $n$.

######  Theorem 2.

Consider saliquot. Then $\mathcal{SG}(0)=0$. Suppose that $n>0$ and let
$n=2^{k}m$, where $2\nmid m$ and $k\geq 0$. Then $\mathcal{SG}(n)=v(n)+1=k+1$.

###### Proof.

The case $0\,|\,0$ is excluded in the definition of opt. Hence there is no
move from 0 and so $\mathcal{SG}(0)=0$. Note that if $n>0$ then $0$ of nim-
value $0$ is an option.

Suppose that $n$ is odd. Then, for all $d\,|\,n$, $n-d$ is even. By induction
the even numbers have nim-value greater than one. Hence, since 0 is an option,
the mex-function gives $0+1=1$ as the nim-value of $n=2^{0}m$.

Suppose that $n$ is even. Then $n-1$, which is odd, is an option. It has nim-
value 1 by induction. (Hence, $\mathcal{SG}(n)\geqslant 2$.) Let
$d=2^{\ell}q\leqslant n$, where we may assume that $\ell>0$, since we are
interested in the even options.

Since $d$ is a divisor of $n$, we have that $0\leq\ell\leqslant k$, and $q\mid
m$, with odd $m>1$. We get $n-d=2^{k}m-2^{\ell}q=2^{\ell}(2^{k-\ell}m-q)$. The
number $x=2^{k-\ell}m-q$ is odd, of nim-value $1$ by induction, unless
$k=\ell$. In this case, if $m=q$, the option is $0$, so suppose $m>q$. Since
both $m$ and $q$ are odd, then the option of $n$ has a greater $2$-valuation
than $n$, i.e $v(n)\geq k+1$. Therefore, no option has $2$-valuation $k$, and
hence by induction no option has nim-value $k+1$.

Since $\ell$ can be chosen freely in the interval $0\leq\ell<k$, by induction
all nim-values $0\leq\mathcal{SG}(n-d)\leq k$ can be reached; since $m>1$, we
may take $q<m$. The result follows. ∎

###  1.2 The aliquants

The aliquant games are somewhat more intricate than the aliquots, but we still
have an explicit solution in the first variation. Here $f(n)=\\{d:d\nmid
n,n\in\mathbb{N}_{0}\\}$.

####  1.2.1 maliquant: move-to a non-divisor

Since all numbers divide $0$, $0$ does not have any options, and hence
$\mathcal{SG}(0)=0$. On the other hand, $0$ does not divide any nonzero
number, and hence $0$ will be an option from each number. The options are:
$\mbox{opt}(n)=\\{d<n:d\nmid n,n\in\mathbb{N}_{0}\\}.$ $n$ $\mbox{opt}(n)$
$\mathcal{SG}(n)$ 0 $\varnothing$ 0 1 0 1 2 0 1 3 0,2 2 4 0,3 1 5 0,2,3,4 3 6
0,4,5 2 7 0,2,3,4,5,6 4 8 0,3,5,6,7 1 In maliquant, the 2-valuation plays an
opposite role as in saliquot; here only the odd part of $n$ determines the
nim-value. Let $i_{o}:\mathbb{N}\rightarrow\mathbb{N}$ be the index function
for largest odd factor of a given natural number. That is, if $n=2^{k}(2m-1)$,
then $i(n)=m$. Clearly $i_{o}(2m-1)=m$ and $i_{o}(n)\leq(n+1)/2$.

######  Lemma 1.

For all $n\in\mathbb{N}$, the numbers in the set $\\{n,\ldots,2n-1\\}$
contribute all maximal odd factor indices in the set $\\{1,\ldots,n\\}$. That
is, $\\{i_{o}(x):n\leq x\leq 2n-1\\}=\\{1,\ldots,n\\}$.

###### Proof.

We use induction on $n$. Assuming the statement of the lemma holds for all
natural numbers up to $n$, we consider the set $\\{n+1,\dots,2n-1,2n,2n+1\\}$.
As $i_{o}(2n)=i_{o}(n)$ and $i_{o}(2n+1)=n+1$, it follows that
$\\{i_{o}(x):n\leq x\leq 2n+1\\}=\\{1,\ldots,n,n+1\\}$ ∎

######  Theorem 3.

Consider maliquant. Then, $\mathcal{SG}(0)=0$ and, for all $n\in\mathbb{N}$,
$\mathcal{SG}(n)=i_{o}(n)$.

###### Proof.

We use induction on $n\in\mathbb{N}$. If $n$ is odd, then write $n=2m-1$
whence $\\{m-1,\dots,2m-3\\}\subset\mbox{opt}(n)$. By Lemma 1 and induction
hypothesis, we have $\\{\mathcal{SG}(k):m-1\leq k\leq
2m-3\\}=\\{1,\dots,m-1\\}$. By induction hypothesis,
$\mathcal{SG}(k)=i_{o}(k)\leq m/2$ for all $k<m-1$, and hence
$\mathcal{SG}(n)=m=i_{o}(n)$. Even numbers are options, but they have nim-
values smaller than $m/2$, by induction.

If $n$ is even, write $n=2^{k}m$ where $k>0$ and $m$ is odd. Thus it suffices
to prove $\mathcal{SG}(n)=i_{o}(m)$. Note that, for all positive integers $l$,
we have $i_{o}(l)=i_{o}(m)$ if and only if $l=2^{j}m$ for some $j\geq 0$. Thus
if $m=1$ then $\mbox{opt}(n)$ omits all those elements $2^{j}$ with index $1$,
hence $\mathcal{SG}(n)=1$. Otherwise, if $m>1$, we observe that

$\left\\{2^{k-1}m+1,2^{k-1}m+2,\dots,2^{k}m-1\right\\}\subset\mbox{opt}(n).$

If we augment this set with the element $2^{k}m$, then by Lemma 1 the indices
of its elements are $\\{1,2,\dots,2^{k-1}m+1\\}$, which includes
$\\{1,2\dots,i_{o}(m)-1\\}$ as a subset. However, $\mbox{opt}(n)$ contains no
elements of the form $2^{j}m$, and hence $i_{o}(m)$ does not appear among the
elements $i_{o}(x)$ for all $x\in\mbox{opt}(n)$, yet all elements of
$\\{1,\dots,i_{o}(m)-1\\}$ do so appear. Thus by induction hypothesis
$\mathcal{SG}(n)=i_{o}(m)$. ∎

####  1.2.2 saliquant: subtract a non-divisor

Here we run into some mysterious sequences. We can only prove partial results.
The options are: $\mbox{opt}(n)=\\{n-d:d\nmid n,n\in\mathbb{N}_{0}\\}.$

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$ | $n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---|---|---|---
0 | $\varnothing$ | 0 | 10 | 1,2,3,4,6,7 | 2
1 | $\varnothing$ | 0 | 11 | 1,2,3,4,5,6,7,8,9 | 5
2 | $\varnothing$ | 0 | 12 | 1,2,3,4,5,7 | 4
3 | 1 | 1 | 13 | $1,\ldots,11$ | 6
4 | 1 | 1 | 14 |  $1,\ldots,6$, 8,9,10,11 | 6
5 | 1,2,3 | 2 | 15 |  $1,\ldots,9$,11,13 | 7
6 | 1,2 | 1 | 16 |  $1,\ldots,7$, 9,10,11,13 | 7
7 | 1,2,3,4,5 | 3 | 17 | 1,…,15 | 8
8 | 1,2,3,5 | 3 | 18 | 1,…, 8,10,11,13,14 | 4
9 | 1,2,3,4,5,7 | 4 | 19 | 1,…,17 | 9

The odd heap sizes turn out to be simple. We give some more nim-values for
even heap sizes, $n=0,2,\ldots$,

$\mathcal{SG}(n)=0,0,1,1,3,2,4,6,7,4,7,5,10,12,10,13,15,8,13,9,17,17,16,11,22,\ldots$

For even heap sizes $n\geq 2$,

$\mathcal{SG}(n)/n=0,1/4,1/6,3/8,1/5,1/3,3/7,7/16,2/9,7/20,5/22,5/12,6/13,5/14,$
$13/30,15/32,4/17,13/36,9/38,17/40,17/42,4/11,11/46,11/24,\ldots$

Sorting the ratios $\mathcal{SG}(n)/n$ by size, we find that the associated
nim-values $[n,\mathcal{SG}(n)]$ for the smallest ratios,
$[6,1],[10,2],[18,4],[22,5],[34,8],[38,9],[46,11]$ satisfy
$(n-2)/\mathcal{SG}(n)=4$. The half of each heap size in this sequence is odd,
and we get the odd numbers $3,5,9,11,17,19,23,\ldots$. We have not
investigated these patterns further, but we believe that, for all $n$,
$\mathcal{SG}(n)\geq(n-2)/4$. Indeed, by plotting the first 1000 nim-values in
Figure 1, this lower bound appears to continue.

Figure 1: The initial 1000 nim-values of saliquant.

######  Theorem 4.

Consider saliquant. Then $\mathcal{SG}(0)=0$, and if $n$ is odd, then
$\mathcal{SG}(n)=\frac{n-1}{2}$. Moreover, $\mathcal{SG}(n)<n/2$.

###### Proof.

Suppose that the statement holds for all $m<n$. If $n=2x+1$ then each
nonnegative integer smaller than $x$ is represented as a nim-value, and
specifically, for each odd number $2y+1$, with $y<x$, $\mathcal{SG}(2y+1)=y$.
Moreover, each odd number is an option of $x$, since each even integer is a
non-divisor of $n=2x+1$. Therefore, we use that, by induction, each even
number smaller than $n$ has a smaller nim-value and we are done with the first
part of the proof.

Suppose next that $n=2x$. Then, since both 1 and 2 are divisors, we know that
the largest option is smaller than $2x-2$. By induction, the nim-value of any
number smaller than $2x-2$ is smaller than $x-2$, namely
$\mathcal{SG}(2x-3)=\mathcal{SG}(2(x-2)+1)$ is the upper bound for a nim-value
of an option of $2x$. ∎

###  1.3 The totatives: move-to a relatively prime

Here $f(n)=\\{x\mid(x,n)=1\\}$. The totative games are defined by moving to a
relatively prime residue. We list the first few nim-values of totative.  $n$
$\mbox{opt}(n)$ $\mathcal{SG}(n)$ 1 $\varnothing$ 0 2 1 1 3 1,2 2 4 1,3 1 5
1,2,3,4 3 6 1,5 1 7 1, …, 6 4 8 1,3,5,7 1 We have the following result. The
solution involves the function $i_{p}$, the index of the smallest prime
divisor of a given number, where the prime 2 has index 1.

######  Theorem 5.

Consider totative. The nim-value of $n>1$ is the index of the smallest prime
divisor of $n$, and $\mathcal{SG}(1)=0$.

###### Proof.

There is no move from $1$, because the only number relatively prime with $1$
is $1$, and options have smaller size than the number. Hence, by the
definition of the mex-function, $\mathcal{SG}(1)=0$. Also,
$\mathcal{SG}(2)=1$, since the only relatively prime number of $2$ is $1$,
which has nim-value $0$, and $i_{p}(2)=1$. Suppose that the result holds for
all numbers smaller than $n$. From $n$ you can only access a smaller number
with no common divisor to $n$. Therefore none of its options has the same
smallest prime divisor. This is one of the properties of the mex-rule.

Thus, the index of the smallest prime divisor of $n$ will be chosen as nim-
value if each prime with a smaller index appears as an option. But, the set of
relatively prime numbers smaller than $n$ contains in particular all the
relatively prime numbers of the smallest prime divisor of $n$, and hence, all
the primes that are smaller than the smallest prime factor of $n$. By
induction, this is the desired set of nim-values, since the move-to 1 (of nim-
value $0$) is always available. ∎

This is sequence A055396 in Sloane [7]: “Smallest prime dividing $n$ is
$a(n)$-th prime $(a(1)=0)$.”

###  1.4 The non-totatives: move-to a non-relatively prime

Here is a table of the first few nim-values of nontotative:  $n$
$\mbox{opt}(n)$ $\mathcal{SG}(n)$ $n$ $\mbox{opt}(n)$ $\mathcal{SG}(n)$ 0
$\varnothing$ 0 10 0,2,4,5,6,8 5 1 0 1 11 0 1 2 0 1 12 0,2,3,4,6,8,9,10 6 3 0
1 13 $0$ 1 4 0,2 2 14 0,2,4,6,7,8,10,12, 7 5 0 1 15 0,3,5,6,9,10,12 4 6
0,2,3,4 3 16 0,2,4,6,8,10,12,14 8 7 0 1 17 0 1 8 0,2,4,6 4 18
0,2,3,4,6,8,9,10,12,14,15,16 9 9 0,3,6 2 19 0 1

This sequence does not yet appear in OEIS [7], but curiously enough, a nearby
sequence is A078898, “Number of times the smallest prime factor of $n$ is the
smallest prime factor for numbers $\leq n$; $a(0)=0$, $a(1)=1$.” For $n\geq
2$, $a(n)$ tells in which column of the sieve of Eratosthenes (see A083140,
A083221) $n$ occurs in. Here, $\mathcal{SG}(15)=4\neq 3=a(15)$ is the first
differing entry. In Figure 2 we plot the first $1000$ nim-values.

Figure 2: The initial $1000$ nim-values of nontotative.

Let us sketch a few nim-value subsequences. The primes have nim-value $1$, and
the prime squares have nim-value $2$. The numbers with close prime factors,
‘almost squares’, appear to have almost constant nim-values. On the other
hand, some numbers in arithmetic progressions appear to have nim-values in
almost arithmetic progressions. For all $n$, $\mathcal{SG}(2n)=n$. We give the
exact statements in Theorem 6 below.

For subsequences of the natural numbers, $s$, let the asymptotic relative nim-
value be

$r_{s}=\lim_{n}\frac{\mathcal{SG}(s(n))}{s(n)},$

if it exists. The subsequences of largest relative nim-values, apart from
$s_{0}=2,4,\ldots$ (with $\mathcal{SG}(2n)=n$), are $s_{1}=3,9,\ldots$ and
$s_{2}=5,25,35,55,65,\ldots$, with corresponding first differences
$\Delta_{1}=(6,6,\ldots)$ and $\Delta_{2}=(20,10,20,10,\ldots)$, with nim-
values in $\\{\lfloor(n+1)/4\rfloor\\}$ and $\\{\lfloor n/10\rfloor,\lceil
n/10\rceil\\}$ respectively. Thus $r_{0}=1/2$, $r_{1}=1/4$ and $r_{2}=1/10$,
where $r_{s_{i}}=r_{i}$. The region between ‘prime factorization’ and ‘purely
arithmetic behavior’ is still mysterious. We can identify at least one more
sequence of arithmetic behavior, with $r_{3}\approx 1/17$, but the
descriptions start to get quite technical here. Note that (ix) and (v) imply
(viii); it is handy to state (v) as a separate item as it is used several
places in the proof.

######  Theorem 6.

Consider nontotative. For $n\in\mathbb{N}$,

  1. (i)

$\mathcal{SG}(n)=1$ if and only if $n$ is prime;

  2. (ii)

$\mathcal{SG}(n)=2$ if and only if $n$ is a prime square;

  3. (iii)

$\mathcal{SG}(n)\in\\{3,4\\}$ if and only if $n=p_{i}p_{i+1}$, or $n=8$:
$\mathcal{SG}(n)=3$ if and only if $i$ is odd, with $p_{1}=2$;

  4. (iv)

$\mathcal{SG}(n)\in\\{5,6\\}$ if and only if $n=p_{i}p_{i+2}$ or $n=12$:
$\mathcal{SG}(n)=5$ if and only if $i\equiv 1,2\pmod{4}$.

Moreover, for $n\in\mathbb{N}$,

  1. (v)

$\mathcal{SG}(2n)=n$;

  2. (vi)

If $n\equiv 3\pmod{6}$, then $\mathcal{SG}(n)=\lfloor(n+1)/4\rfloor$;

  3. (vii)

if $n\equiv 5,25\pmod{30}$, then $\mathcal{SG}(n)\in\\{\lfloor
n/10\rfloor,\lceil n/10\rceil\\}$.

Lastly, for $n\in\mathbb{N}$,

  1. (viii)

$\mathcal{SG}(n)\leq n/2$;

  2. (ix)

if $n$ is odd, then $\mathcal{SG}(n)\leq(n+1)/4$.

###### Proof.

Note that $\mathcal{SG}(0)=0$ implies $\mathcal{SG}(n)>0$ if $n>0$. The
induction hypothesis assumes all the items. Not that item (v) takes care of
all cases where the prime $2$ divides $n$, so in all other items, we may
assume that the smallest prime dividing $n$ is greater than $2$.

For (i), the only non-relatively prime number of a prime is 0. Hence
$\mathcal{SG}(p)=1$ if $p$ is prime. If $n=pm$ is not a prime, then there is a
move to the prime divisor $p$, a non-relative prime, and there is a move to 0.
Hence the nim-value is greater than one.

For (ii) we consider prime squares $p^{2}$, and note that each option is of
the form $np$, $0\leq n\leq p-1$. In particular there are moves $p^{2}\mapsto
0$ and $p^{2}\mapsto p$, as noted in the first paragraph. Moreover, by
induction we assume that $\mathcal{SG}(m)=2$ if and only if $1<m<p^{2}$ is a
prime square. Then $m\neq np$, and so, by the minimal exclusive algorithm,
$\mathcal{SG}(p^{2})=2$. For the other direction, we are done with the cases
$0,1$ and primes. Consider the composite $n=pm$, not a prime square, where $p$
is the smallest prime factor. Then there is a move to $p^{2}$, and hence
$\mathcal{SG}(n)\neq 2$.

For (iii) we begin by proving that $\mathcal{SG}(n)\in\\{3,4\\}$ if
$n=p_{i}p_{i+1}$ or $n=8$, and where the nim-value is three if and only if the
index of the smaller prime is odd. The base case is $\mathcal{SG}(2\cdot
3)=3$, and where the exception $n=8$ is by inspection. For the generic case,
each option is of the form $np_{i}$, $0\leq n\leq p_{i+1}-1$ or $np_{i+1}$,
$0\leq n\leq p_{i}-1$. In particular, there is a move to $p_{i}$ (and to
$p_{i+1}$) of nim-value one, and there is a move to $p_{i}^{2}$ of nim-value
$2$. We must show that there is no move to another prime pair of the same
form, i.e., $p_{j}p_{j+1}$, with $j$ of the same parity as $i$. Observe that
there is a move to $p_{i-1}p_{i}$, with $j+1=i$, but there is no move to any
other almost square $p_{j}p_{j+1}$. By induction, this observation suffices to
find a move to nim-value $3$, if $i$ is even. For the other direction, we must
show that $\mathcal{SG}(n)\not\in\\{3,4\\}$ if $n$ is not an almost square. We
are done with the cases $n$ a prime or a prime square. Suppose that $n=px$ is
not of the mentioned form, where $p$ is the smallest prime factor of $n$. The
case $p=2$ is dealt with in item (v), so lets assume $p>2$. Then, there is a
move to $pq$ (non-relative prime with $n$), where $q$ is the smallest prime
larger than $p$, because by assumption, $x>q$. And there is a move to $pq$,
where $q$ is the largest prime smaller than $p$.

For (iv), we study the case $n=p_{i}p_{i+2}$. If $i=1$, then $n=10$, and
$\mathcal{SG}(10)=5$. If $i=2$, then $n=21$, and, by inspection,
$\mathcal{SG}(21)=5$. For the general case, among the options we find
$0,p_{i},p_{i}^{2},p_{i}p_{i+1},p_{i+1}p_{i+2}$. Hence, by the previous
paragraphs, the options attain all nim-values smaller than 5. Next, suppose
that $i\equiv 1,2\pmod{4}$, and we must show that there is no option of the
same form, to create nim-value $5$. Each option is a multiple of one of the
primes $p_{i}$ and $p_{i+2}$. The only possibility would be the option
$p_{i-2}p_{i}$. But $i-2\equiv 0,3\pmod{4}$. Hence no option has nim-value
$5$. The analogous argument suffices to show that no option has nim-value $6$
if $i\equiv 0,3\pmod{4}$, $i\geq 3$. The special case $n=12=2\times 2\times 3$
is not an option, by $i\geq 3$. On the other hand, the argument shows that
there is an option to nim-value $5$. Consider the other direction. Suppose
that $n=p_{i}x$, where $p_{i}>2$ is the smallest prime in the factorization of
$n$. (The case $p=2$ is dealt with below.) If $x>p_{i+2}$ then there is a move
to $p_{i}p_{i+2}$, and if $i\geq 3$, then there is a move to $p_{i-2}p_{i}$.
If $i=2$, then there is a move to $12$ of nim-value $6$. That concludes this
case. If $p_{i}<x<p_{i+2}$, then $x=p_{i+1}$, since $p_{i}$ is the smallest
prime in the decomposition of $n$, and we are done with this case.

For (v), we verify that, for all $n$, $\mathcal{SG}(2n)=n$. The options are of
the forms $2j$, with $0\leq j\leq n$, and so, induction on (v) gives that each
nim-value smaller than $n$ can be reached. Moreover induction on (viii) gives
that nim-value $n$ does not appear among the options.

For (vi) we must prove: if $n\equiv 3\pmod{6}$, then
$\mathcal{SG}(n)=\lfloor(n+1)/4\rfloor$. The claimed nim-value sequence for
the positions $3,9,15,21,27,\ldots$ is
$\lfloor(3+1)/4\rfloor,\lfloor(9+1)/4\rfloor,\lfloor(15+1)/4\rfloor,\ldots$,
which is $1,2,4,5,7,8,\ldots$. Clearly $n$ has each smaller position of the
same form as an option. Precisely, the multiples of 3 are missing in the nim-
value sequence. But, induction on (v), the multiples of $6$ have nim-values
multiples of $3$, and indeed, all multiples of $6$, smaller than $n$ are
options of $n$. By induction on item (ix), since $n$ is odd, the nim-value
$\lfloor(n+1)/4\rfloor$ does not appear among its options. The proof of (vii)
is similar to (vi), but more technical, so we omit it.

Item (viii) follows directly by induction (for example, if $n$ is even then
$n-2$ is the largest option and $\mathcal{SG}(n-2)\leq n/2-1$).

For item (ix), assume that $p>2$ is smallest prime divisor of $n$. The cases
with $p\leq 5$ have already been proved in items (vi) and (vii). Hence $p>5$.
It follows that with $t=\lfloor\frac{n}{2p}\rfloor$, $tp+3<n/2<(t+1)p-3$. It
follows that the nim-value $\lfloor\frac{n+1}{4}\rfloor$ cannot be reached
from $n$, by options of the form in (v). On the other hand it cannot be
reached, by moving to an odd number, since options $n-2p$ or smaller produce
too small nim-values, by induction. ∎

We do not yet know, if all nim-values can be obtained by analogous reasoning.
The initial occurrences (as for $n=12$ in the proof above) of nim-values that
do not follow general patterns may complicate things.

##  2 Counting games

This section concerns rulesets as in item (i) in the introduction. _Binary
games_ have only one option per heap. At each stage of play, the decision
problem reduces to which one of the heaps to make the move. The nim-value of
any sum of binary games is binary, that is, each nim-value $\in\\{0,1\\}$.
Indeed, the nim-value of a given disjunctive sum of binary games is 0 if and
only if the number of heaps of nim-value one is even. Of course, the nim-value
sequence for any given ruleset is valid in the much larger context of all
normal-play combinatorial games.

We begin in Section 2.1.1, by solving totient, and then we sketch a
classification scheme for nontotient. Then we list nim-values of other open
counting games.

###  2.1 Harold Shapiro and the totient games

Recall that Euler’s totient (or $\phi$) function counts the number of
relatively prime residues of a given number. For example $\phi(7)=6$ and
$\phi(6)=2$. Recall that this function is multiplicative. This is where we can
apply a known result by Harold Shapiro “An arithmetic function arising from
the $\phi$ function” [6]. The fundamental theorem for iteration of the Euler
$\phi$ function in his work is as follows. For all $x$, let
$\phi^{i}(n)=\phi^{i-1}(\phi(n))$. Since $\phi^{i}(n)<\phi^{i-1}(n)$ and
$\phi(n)$ is even, if $n>2$, we have that, for all $n$ and some unique $i>0$
(depending on $n$ only)

$\displaystyle\phi^{i}(n)=2.$ (1)

This lets us define the Class of $n$, as $C(n)=i$, when (1) holds, and
otherwise $C(1)=C(2)=0$.

######  Theorem 7 ([6]).

Let $m,n\in\mathbb{N}$. If $n$ is odd, then $C(n)=C(2n)$, and otherwise
$C(n)+1=C(2n)$. In general, if either $m$ or $n$ is odd, then
$C(mn)=C(m)+C(n)$. Otherwise, that is, if both $m$ and $n$ are even, then
$C(mn)=C(m)+C(n)+1$.

For example $\phi(7)^{2}=\phi(6)=2$, so $C(7)=2$. In general, for primes $p$,
$\phi(p)^{2}=\phi(p-1)$, so $C(p)=C(p-1)+1$. Here is an example:
$C(15)=C(3)+C(5)=1+C(4)+1=2+C(2)+C(2)+1=3$, and note that
$\phi(15)=\phi(3)\phi(5)=2\cdot 4=8$. Moreover $\phi(8)=4$ and $\phi(4)=2$, so
indeed $\phi^{3}(15)=2$.

This result lets us compute the nim-values of the first totient ruleset,
totient, simply by recalling the $\phi$-values for the primes.

####  2.1.1 totient, the move-to variation of the totient game

As mentioned, the nim-value table contains only $0$s and $1$s, and we call
this kind of games ‘binary games’. Indeed, there is only one option from $n$,
namely $\phi(n)$, the number of relatively prime residues of $n$.  $n$
$\mbox{opt}(n)$ $\mathcal{SG}(n)$ 1 $\varnothing$ 0 2 1 1 3 2 0 4 2 0 5 4 1 6
2 0 7 6 1 8 4 1

Here are a few more nim-values in the $\mathcal{SG}$-sequence:

$01001,01111,01010,01100,00101,0001$

where the “,” is for readability. Each game component has a forced move, that
if played alone may be regarded as an automaton. Starting from 8, for example,
the iteration of $\phi$ gives the sequence of moves $8\mapsto 4\mapsto
2\mapsto 1$, and the $\mathcal{SG}$-sequence, of course is alternating between
0s and 1s, terminating with the 0 at position 1. If played on a disjunctive
sum of totient, the nim-value sequence is of course also binary, alternating
between 0s and 1s, and it is 0 if and only if there is an even number of heaps
of nim-value 1. Suppose that we play $7_{\rm t}+7_{\rm s}$, where the first
$7$ is totient and the second $7$ is subtraction$\\{1,2\\}$, with nim-value
sequence $0,1,2,0,1,2,0,\ldots$, say with sink number $1$ on both components.
Then there are exactly two winning moves to $6_{\rm t}+7_{\rm s}$ or $7_{\rm
t}+5_{\rm s}$. Intelligent play from a general position $m_{\rm t}+n_{\rm s}$
requires full understanding of totient.

######  Theorem 8.

Consider totient, and let $C$ be as in Theorem 7. Then $\mathcal{SG}(1)=0$,
and for $n>1$, $\mathcal{SG}(n)=C(n)+1\pmod{2}$.

###### Proof.

Use Theorem 7. ∎

In general, thus it suffices to compute the parity of $C(n)$ and, given the
factorization of $n$, apply Theorem 7. For example,
$C(2^{3})=C(2)+C(2^{2})+1=3C(2)+2=2$, and without looking into the table, we
get $\mathcal{SG}(8)=1$. For another example, if $n=2\cdot 3^{7}\cdot 11$,
then $C(n)=7C(3)+C(11)=7+3=10$, since $\phi(3)=2$ and $\phi^{3}(11)=2$.
Therefore $\mathcal{SG}(48114)=(C(48114)+1)\pmod{2}=11\pmod{2}=1$, and we find
a unique winning move $48114_{\rm t}+3_{\rm s}\mapsto 48114_{\rm t}+2_{\rm
s}$, where s is still subtraction$\\{1,2\\}$.

####  2.1.2 nontotient, the subtraction variation of the totient game.

From a given number $n$, subtract the number of relatively prime numbers
smaller than $n$. We cannot adapt Theorem 8, because it relies on iterations
where you instead move-to this number, and the authors have not yet found a
similarly efficient tool. Let us list the initial options and nim-values. An
alternative way to think of the options is: move-to the number of nonrelative
primes, including the number. The nim-values alternate for heaps that are
powers of primes, starting with $\mathcal{SG}(p^{0})=0$. This happens, because
the number of nonrelatively prime numbers smaller than or equal a prime power
$p^{k}$ is $p^{k-1}$. Hence, $\mathcal{SG}(p^{k})=0$ if and only if $k$ is
even. Since $\phi$ is multiplicative it is easy to compute $f(n)=n-\phi(n)$,
for any $n$, or get a formula for $f$, for any given prime decomposition of
$n$. However, $f$ is not multiplicative, which limits the applicability of
such formulas. In some special cases, we can use the proximity to powers of
primes for fast computation of the nim-value. Take the case of $n=p^{k}q$, for
some distinct primes $p$ and $q$. Then $f(n)=n-\phi(n)=p^{k-1}(q+p-1)$.
Whenever $q+p-1$ is a power of the prime $p$, the nim-value of $n$ is
immediate by the parity of the new exponent. Take for example $p=2$ and $q=7$.
Then $p+q-1=2^{3}$, and so we can find the nim-value of, for example
$n=7168=2^{10}\times 7$ gives the exponent $9+3=12$ and so
$\mathcal{SG}(7168)=0$. Similarly, with $p=3$ and $q=7$, we can easily compute
$\mathcal{SG}(413343)=1$, because $p+q-1=3^{2}$, and $413343=3^{10}\times 7$.

Let ‘$\mathrm{dist}$’ denote the number of iterations of $f$ to an even power
of a prime. We get the following suggestive table of the first few nim-values.
We leave a further classification of $\mathrm{dist}$ as an open problem.

$n$ | $\mbox{opt}(n)$ | dist | $\mathcal{SG}(n)$
---|---|---|---
1 | $\varnothing$ | 0 | 0
2 | 1 | 1 | 1
3 | 1 | 1 | 1
4 | 2 | 0 | 0
5 | 1 | 1 | 1
6 | 4 | 1 | 1
7 | 1 | 1 | 1
8 | 4 | 1 | 1
9 | 3 | 0 | 0
10 | 6 | 2 | 0
11 | 1 | 1 | 1
12 | 8 | 2 | 0
13 | 1 | 1 | 1
14 | 8 | 2 | 0
15 | 7 | 2 | 0
16 | 8 | 0 | 0

###  2.2 The $\tau$-games

The $\mathcal{SG}$-sequences of mtau and stau do not yet appear in OEIS. The
number of divisors is multiplicative in the following sense:
$\tau(n)=(a_{1}+1)\cdots(a_{k}+1)$, where $n=p^{a_{1}}_{1}\cdots
p^{a_{k}}_{k}$.

####  2.2.1 Move-to the number of proper divisors

Consider mtau, where the single option is the number of proper
divisors.666Note that if we remove the word proper here, then both 1 and 2
become loopy, and thus all games would be drawn. See also Section 7 for some
more reflections on ‘loopy’ or ‘cyclic’ games. A heap of size one has no
option, so the nim-value sequence starts at $\mathcal{SG}(1)=0$. Let us list
the first few nim-values.

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---
1 | $\varnothing$ | 0
2 | 1 | 1
3 | 1 | 1
4 | 2 | 0
5 | 1 | 1
6 | 3 | 0
7 | 1 | 1
8 | 3 | 0
9 | 2 | 0

Note that each prime has nim-value $1$ because they have only one proper
divisor. From this small table we may deduce many more nim-values. The first
few 0-positions are

$1,4,6,8,9,10,12,14,15,18,20,21,22,24,25,26,27,28,30,\ldots$

Note that $16$ is the first composite number that is not included, and $36$ is
the second one, and then $48,80,81,100,$ etc. What is special about these
composite numbers?

The sequence of all ones has some resemblance to the sequence of all numbers
with a nonprime number of proper divisors. As mentioned, $16$ and $36$ are the
first composite members of this sequence. These two numbers are the smallest
composite numbers with a composite, i.e., nonprime, number of proper divisors,
such numbers generalize the primes, because primes also have a nonprime number
of proper divisors. We are interested in the smallest number
$n=p^{a_{1}}_{1}\cdots p^{a_{k}}_{k}$, for which
$\tau(n)-1=(a_{1}+1)\cdots(a_{k}+1)-1\in\\{16,36,48,80,\ldots\\}$, that is,
the smallest number $n$, such that
$(a_{1}+1)\cdots(a_{k}+1)\in\\{17,37,49,81,\ldots\\}$. An obvious candidate is
$n=2^{16}$, with $a_{1}=16$, and otherwise $a_{i}=0$. But it turns out that
$n=2^{6}\cdot 3^{6}=46656<2^{16}$ gives $\tau(46656)=(6+1)(6+1)=49$, and this
is indeed the smallest such number. Thus, we have the following observation.

######  Observation 1.

Consider mtau. If $n<46656$, then $\mathcal{SG}(n)=1$ if and only if $n$
consists of a nonprime number of divisors.

We note that neither sequence is listed in OEIS (see Section 2.3.1 for a
similar sequence that is listed).

####  2.2.2 Subtract the number of divisors

Consider stau. This variation has a $\mathcal{SG}$-sequence beginning with
$\mathcal{SG}(0)=0$. A heap of size one has one divisor, with an option to
zero. A heap of size two has two divisors and hence the option is zero, and so
on: $0,1,1,0,0,1,0,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1$. The ‘1’s occur at
$1,2,5,8,9,10,12,13,15,16,19,20\ldots$

###  2.3 The $\Omega$ and $\omega$-games

The sequence of number of prime factors counted with multiplicity, is called
$\Omega(n)$. Otherwise, when only the distinct primes are counted, it is
called $\omega(n)$.777That is, if $n$ has canonical form
$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$,
$\Omega(n)=a_{1}+a_{2}+\cdots+a_{k}$ and $\omega(n)=k$.

Somewhat surprisingly, nim-value sequences for the games that count the number
of prime divisors, do not yet appear in OEIS.

####  2.3.1 Move-to the number of prime divisors

The nim-value sequence of m$\Omega$ starts at a heap of size one, of nim-value
$0$, by definition. Any prime, has a move-to one, so all primes have nim-value
one, a square has a move-to the heap of size 2, and hence has nim-value $0$,
and so on. The nim-value sequence starts:

$0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,1,\ldots$

The indices of the ones is a generalization of the primes:

$2,3,5,7,11,13,16,17,19,23,24,29,31,36,37,40,41\ldots$

The number $64$ is in the sequence, and this distinguishes it from A026478.
Still it is not exactly A167175, since not all numbers with a nonprime number
of prime divisors are included. The sequences coincide until $2^{16}-1$
though, since the first such number to be excluded is $2^{16}$. Via a similar
(but easier) reasoning as in Section 2.2.1, we have the following observation.

######  Observation 2.

Consider m$\Omega$. If $n<2^{16}$, then $\mathcal{SG}(n)=1$ if and only if $n$
consists of a nonprime number of prime divisors, counted with multiplicity.

####  2.3.2 Subtract the number of prime divisors

Here we consider the ruleset s$\Omega$ ‘subtract the number of prime
divisors’. A heap of size one has nim-value $0$, by definition. A heap of size
two has a move to a heap of size one, and has nim-value one. A heap of size
three has a move to a heap of size two, and has nim-value $0$. The nim-value
sequence starts:

$0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,\ldots,$

and the indices of the ones are located at
$2,5,6,9,10,13,14,16,18,20,21,23\ldots$

This sequence does not appear in OEIS.

####  2.3.3 Move-to the number of distinct prime divisors

The nim-value sequence of m$\omega$ ‘move-to number of distinct prime
divisors’ starts at one, of nim-value zero. The first few nim-values are:
$0,1,1,1,1,0,1,1,1,0,1,0,\ldots$, and the corresponding indices of the ones
are $2,3,4,5,7,8,9,11,13,\ldots$

The first nim-value that distinguishes it from m$\Omega$ is for the heap of
size 4. Since it has only one distinct factor, this game behaves like a prime,
and the nim-value is one. Six is the first number that has more than one
distinct factor. Hence $7!$ is the smallest number with distinct factors, for
which the nim-value is one.

######  Observation 3.

If $n<7!$, then $\mathcal{SG}(n)=1$ if and only if $n$ contains exactly one
distinct factor.

####  2.3.4 Subtract the number of distinct prime divisors

The nim-value sequence of s$\omega$ ‘subtract the number of distinct prime
divisors’ starts at one, which does not have any prime divisor, and hence of
nim-value zero. Next, two has the option one, three has the option two, and
four has the option three. The first few nim-values are:

$0,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,\ldots,$

with $1$s at indices $2,4,7,9,10,13,14,16,19,20,23,\ldots$ Neither of these
sequences appear in OEIS.

##  3 Dividing games

The ruleset dividing deploys the notion of a disjunctive sum in their
recursive definition. That is, an option is typically, with some exception, a
disjunctive sum of games. A reference that goes into detail of such games is
[3].

###  3.1 The dividing game

For this game, the position is a natural number. The $Y$ in the definition of
opt is not $2^{X}$, but instead consists of disjunctive sums of natural
numbers. A player divides the current number into equal parts and we write “+”
to separate the parts, the new game components. To avoid long chains of
components, we use multiplicative notation, in the sense that $x\times y$
means $y$ copies of $x$ (that is, $x+\ldots+x$). In this notation, addition is
commutative, but multiplication is not. For example $\text{opt}(10)=\\{5\times
2,2\times 5,1\times 10\\}$. The current player moves in precisely one of the
components and leaves the other ones unchanged. For example, a move from $5+5$
is to $5+1\times 5=5$ (because no move is possible from $1\times 5$), and
indeed, by symmetry, this is the only admissible move. The number of options
is $\tau(n)-1$.

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---
1 | $\varnothing$ | 0
2 | $1+1$ | 1
3 | $1\times 3$ | 1
4 | $2\times 2,1\times 4$ | 1
5 | $1\times 5$ | 1
6 | $3\times 2,2\times 3,1\times 6$ | 2
7 | $1\times 7$ | 1
8 | $4\times 2,2\times 4,1\times 8$ | 1

Let $\Omega_{2}(n)$ denote the number of prime factors of $n$, where the
powers of 2 are counted without multiplicity, and the powers of odd primes are
counted with multiplicity.

######  Theorem 9.

Consider dividing. For all $n\in\mathbb{N}$, $\mathcal{SG}(n)=\Omega_{2}(n)$.

###### Proof.

$\mathcal{SG}(1)=0$, and $1$ does not have any prime components. Suppose that
$n$ is a power of two. Then $\mathcal{SG}(n)=1$, since each option permits the
mimic strategy. Similarly, if $n$ is a prime, then $\mathcal{SG}(n)=1$.
Suppose that $n=2^{k}p_{1}\cdots p_{j}$, with $k\in\mathbb{N}_{0}$ and each
$p_{i}$ odd. We use induction to prove that $\mathcal{SG}(n)=j$ if $k=0$, and
otherwise $\mathcal{SG}(n)=j+1$. If $k=0$, $n$ can be split into an odd number
of components each having $m$ prime factors for each $m\in[1,j-1]$. Induction
and the nim-sum together with the mex-rule gives the result in this case.
Similarly, if $k>0$, $n$ can be split into an odd number of components of $m$
prime factors for each $m\in[1,j]$, which proves that $\mathcal{SG}(n)=j+1$ in
this case. ∎

######  Example 10.

Suppose the position is $18+7=2\cdot 3^{2}+7$. How do you play to win? The
nim-value is $3\oplus 1=2$, where $\oplus$ denotes the nim-sum. Hence the next
player has a good move. The good move turns the 18-component to nim-value 1,
that is, we divide it into an odd number of even numbers with no odd factor.
This can be done in only one way: you move to $2\times 9+7=2+7$, and clearly
$\mathcal{SG}(2+7)=0$. The next player has exactly two options, but, either
way, you will finish the game in your next move.

###  3.2 The dividing and remainder game

The ruleset divide-and-residue is an extension of dividing, where you are
allowed to divide $n$ to $k$ equal parts $d$ and a remainder $r$ that is
smaller than the parts. Thus, here we have a lot more options (for a generic
game) than dividing, which is obvious by the representation $n=k\times d+r$,
with $0\leq r<d$. By moving we are free to choose any $1\leq d<n$, so we have
$n-1$ options, for all $n>0$. The $\mathcal{SG}$-sequence starts:

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---
1 | $\varnothing$ | 0
2 | $1+1$ | 1
3 | $2+1,1\times 3$ | 2
4 | $3+1,2\times 2,1\times 4$ | 1
5 | $4+1,3+2,2\times 2+1,1\times 5$ | 2
6 | $5+1,4+2,3\times 2,2\times 3,1\times 6$ | 3
7 | $6+1,5+2,4+3,3\times 2+1,2\times 3+1,1\times 7$ | 2
8 | $7+1,6+2,5+3,4\times 2,3\times 2+2,2\times 4,1\times 8$ | 3

An even number of heaps of the same sizes reduces to a heap of size one. A
heap of size one in a disjunctive sum, gets removed. We get an equivalent
reduced table:

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---
1 | $\varnothing$ | 0
2 | $1$ | 1
3 | $2,1$ | 2
4 | $3,1$ | 1
5 | $4,3+2,1$ | 2
6 | $5,4+2,2,1$ | 3
7 | $6,5+2,4+3,2,1$ | 2
8 | $7,6+2,5+3,2,1$ | 3
9 | $8,7+2,6+3,5+4,3,1$ | 4
10 | $9,8+2,7+3,6+4,3,2,1$ | 3

Note that, when we remove pairs of equal numbers, sometimes we must add the
option ‘1’ to symbolize a move to a terminal position of nim-value $2+2=0$.
From this table we may deduce that the game $7+3$ from the first paragraph in
the paper is indeed a losing position. divide-and-residue has a mysterious
$\mathcal{SG}$-sequence, as depicted in Figure 3.

Figure 3: The initial 20000 nim-values of divide-and-residue. They just about
touch the nim-value $2^{8}=256$.

Here are the 50 first nim-values, of the form [heap size, nim-value]:

$[1,0],[2,1],[3,2],[4,1],[5,2],[6,3],[7,2],[8,3],[9,4],[10,3],[11,4],[12,3],[13,4],[14,3],[15,4],[16,3],\newline
[17,4],[18,5],[19,4],[20,5],[21,3],[22,5],[23,4],[24,2],[25,1],[26,5],[27,6],[28,5],[29,6],[30,2],[31,6],\newline
[32,5],[33,3],[34,8],[35,9],[36,8],[37,9],[38,8],[39,9],[40,8],[41,9],[42,4],[43,9],[44,4],[45,9],[46,8],\newline
[47,9],[48,4],[49,9],[50,4].$

Early nim-values tend to be odd for heaps of even size, and even for those of
odd size. By an elementary argument we get: the heap of size 25 is the largest
heap of nim-value one, and one can prove the analogous statement for a few
more small nim-values. We conjecture that any fixed nim-value occurs finitely
many times.

For the upper bound, the nim-values seem to be bounded by $n^{3/5}$, for
sufficiently large heap sizes $n$. An empirical observation is that the growth
of nim-values appears to be halted at powers of two. For example, the nim-
value $2^{2}$ starts to appear at heap size $9$, but does not increase beyond
$2^{2}+2^{0}$ until the heap of size 27.

######  Conjecture 1.

Consider divide-and-residue. Then each nim-value occurs, and at most a finite
number of times. Moreover $\mathcal{SG}(n)/n\rightarrow 0$, as
$n\rightarrow\infty$.

There is no big surprise that this game is hard, since it is an extension of
grundy’s game [1, 7]. Indeed, the options of divide-and-residue in which the
divisor $d$ is greater than $n/2$ correspond to the rule of splitting a heap
into two unequal parts of grundy’s game. If we define the ruleset complement-
grundy, by requiring that $k\geq 2$ in divide-and-residue, then we can prove
the second statement in Conjecture 1 for this new game. Let us tabular the
first few nim-values, where options are displayed in reduced form:

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---
1 | $\varnothing$ | 0
2 | $1$ | 1
3 | $1$ | 1
4 | $1$ | 1
5 | $1$ | 1
6 | $2,1$ | 2
7 | $2,1$ | 2
8 | $2,1$ | 2
9 | $3,2,1$ | 2
10 | $3,2,1$ | 2
11 | $3,3+2,2,1$ | 2

Figure 4 shows that the initial regularity of nim-values is replaced by more
complexity further down the road, although not as severely as for divide-and-
residue. Note that the two games appear to share some geometric properties
such as a local stop of nim-value growth at powers of two, and a bounded
number of occurrences for each nim-value. In this case though, some nim-values
do not appear, such as $12,15,20$ etc. We do not yet know if the omitted nim-
values can be described by some succinct formula, and we do not even know if
the occurrence of each nim-value is finite.

Figure 4: The initial $20000$ nim-values of complement-grundy.

######  Theorem 10.

Consider complement-grundy. Then $\mathcal{SG}(n)/n\rightarrow 0$, as
$n\rightarrow\infty$.

###### Proof.

Consider the nim-value $2^{k}$. If it does not appear, we are done. Suppose it
appears for the first time at heap size $n_{k}$. By the mex rule, if a nim-
value is greater than $2^{k}$, it must have nim-value $2^{k}$ in its set of
options. By the rules of game, this can only happen for a heap of size $m\geq
3\cdot n_{k}$. In particular, this holds for the nim-value $2^{k+1}$, which
occurs for the first time at $m=n_{k+1}$, say. Thus, for nim-values that are
powers of two, we get
$\frac{2}{3}\mathcal{SG}(n_{k})/n_{k}\geq\mathcal{SG}(n_{k+1})/n_{k+1}$. This
upper bound holds for arbitrary nim-values, since the lower bound on where the
power of two $2^{k+1}$ can appear is the same lower bound where any other nim-
value greater than $2^{k}$ may appear. ∎

Two simpler variations of divide-and-residue are:

1) The remainder is not included in the disjunctive sum of an option: divide-
throw-residue.

2) Only the remainders are the options: residue-throw-divisor.

Figure 5: The initial nim-values of divide-throw-residue and residue-throw-
divisor, respectively.

The patterns of the nim-values of these rulesets are displayed in Figure 5.
For variation 1 (to the left), we prove that, for heaps $>1$, the
$\mathcal{SG}$-sequence coincides with OEIS, A003602: If $n=2^{m}(2k-1)$, for
some $m\geq 0$, then $a(n)=k$. The Sprague-Grundy sequence starts at heap of
size one with nim-values as follows

$0,1,2,1,3,2,4,1,5,3,6,2,7,4,8,1,9,5,10,3,11,6,12,\ldots$

It turns out the divide-throw-residue has the same solution as maliquant, the
game where the options are the non-divisor singletons; recall Theorem 3, where
this result is expressed as an index function, $i_{o}$, the index of the
largest odd divisor.

######  Theorem 11.

Consider divide-throw-residue. Then $\mathcal{SG}(n)=i_{o}(n)=k$, if
$n=2^{m}(2k-1)$, for some integer $m\geq 0$.

###### Proof.

Observe that the options in the interval $[\lfloor n/2\rfloor+1,n-1]$ are the
same as for maliquant. Assume first $n$ is even. Then $n/2+n/2$ is an option
in divide-throw-residue, but $n/2$ is not an option in maliquant. However,
$n/2+n/2$ only contributes the nim-value $0$ and may be ignored. Consider next
the disjunctive sum $m+\cdots+m$, with an odd number of components adding up
to $n$. Then there is a power of 2, say $2^{k}$ such that $2^{k}m\in[\lfloor
n/2\rfloor+1,n-1]$, i.e., $2^{k}m\nmid n$. And so, by induction,
$\mathcal{SG}(m)=\mathcal{SG}^{\rm M}(2^{k}m)$, where the M indicates
maliquant. On the other hand, there are options of maliquant of the form
$m\nmid n,m<n/2$. They do not have a match in divide-throw-residue. But, as we
saw in the proof of Theorem 3, they do not contribute to the nim-value
computation in maliquant. The case of odd $n$ is similar. ∎

For variation 2, we observe the following $\mathcal{SG}$-sequence:
$0,1,1,1,2,2,2,2,2,2,\ldots$, i.e., for $n>0$ if $3\cdot 2^{k}$ copies of
$k+1$ have appeared append $3\cdot 2^{k+1}$ copies of $k+2$ as the next nim-
values.

######  Theorem 12.

Consider residue-throw-divisor. For all $n\in\mathbb{N}$, $\mathcal{SG}(n)=k$
if

$n\in\\{3(2^{k-1}-1)+2,\ldots,3(2^{k}-1)+1\\}.$

###### Proof.

We leave this proof to the reader. ∎

##  4 The factoring games

Is there any game that has the number of prime factors of $n\in\mathbb{N}$ as
the sequence of nim-values? The answer is yes, as given by the almost trivial
aliquot game in Section 1.1.1. There is a related game that decomposes into
several components in play, namely to play to any factorization of $n$.

######  Example 11 (m-factoring).

Let $n=12$. Then the set of options is $\\{6+2,3+4,2+2+3\\}$. The unique
winning move is to $2+2+3$, because the nim-values in the set of options are
$1,1,0$, respectively. Hence $\mathcal{SG}(12)=2$.

######  Example 12 (s-factoring).

Let $n=12$. Then the set of options is $\\{6+10,9+8,10+10+9\\}$. The
$\mathcal{SG}$-sequence starts:
$0,0,1,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,2,1,1,1,1,1$, where the first heap is
the empty heap and the second 0 is due to that 1 does not have any prime
factors. $\mathcal{SG}(12)=2$.

m-factoring has a simple solution, but s-factoring we do not yet understand.
Recall the omega-functions from Section 2.3.

######  Theorem 13.

Consider m-factoring, and let $n\geqslant 2$, where each option is a non-
trivial disjunctive sum of a factoring of $n$. Then
$\mathcal{SG}(n)=\Omega(n)-1$. If no two distinct components may contain the
same prime number, then $\mathcal{SG}(n)=\omega(n)-1$.

###### Proof.

If $n$ is a prime, then $\mathcal{SG}(n)=0$, because no factoring to smaller
components is possible. If $n$ is composite with $k$ prime factors, then, by
induction, it is possible to play to an option of nim-value $\ell$, for each
$\ell\in\\{1,\ldots,k-2\\}$, by factoring $n$ into one number with $\ell$
prime factors, and $k-\ell$ other prime components. On the other hand, the
nim-value $k-1$ cannot be obtained as a move option, since
$(x_{1}-1)\oplus\cdots\oplus(x_{\ell}-1)\leqslant(x_{1}-1)+\cdots+(x_{\ell}-1)\leqslant
k-2$, if $k=x_{1}+\cdots+x_{\ell}$. The proof of the second part is similar. ∎

##  5 Full set games

In fullset maliquot a player moves to all the proper divisors in a disjunctive
sum.888Obviously we need to exclude the divisor $n\mid n$; the word “proper”
is implicit in the naming. Let us display the first few numbers with their
options and nim-values.

$n$ | $\mbox{opt}(n)$ | $\mathcal{SG}(n)$
---|---|---
1 | $\varnothing$ | 0
2 | $1$ | $1$
3 | $1$ | $1$
4 | $1+2$ | $0$
5 | $1$ | $1$
6 | $1+2+3$ | $1$
7 | $1$ | $1$
8 | $1+2+4$ | $0$
9 | $1+3$ | $0$

The nim-value sequence starts
$0,1,1,0,1,1,1,0,0,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,\ldots$. The non-unit proper
divisors of $24$ are $2,3,4,6,8$ and $12$. The only square-free ones are $2,3$
and $6$, an odd number. Such observations are relevant for the proof of the
location of the 0s.

######  Theorem 14.

Consider fullset maliquot. Then $\mathcal{SG}(n)\in\\{0,1\\}$, and
$\mathcal{SG}(n)=1$ if and only if $n>1$ is square-free.

Let us indicate the idea of the proof. The nim-value $\mathcal{SG}(4)=0$
because the only non-unit proper divisor, $2$, is square-free, and
$\mathcal{SG}(8)=0$, because there is exactly one square-free proper divisor,
namely 2. In the proof we will use the idea that $\mathcal{SG}(n)=0$ if and
only if $n$ has an even number of square-free proper divisors.

###### Proof.

We induct on the number of divisors.

If $n=p$ is prime, there is an even number, namely 0, of square-free non-unit
proper divisors. The nim-value $\mathcal{SG}(p)=1$ is correct, because the
move to the heap of size one is terminal.

Consider an arbitrary number $n$. Each move will alter the nim-value modulo 2.
We must relate this to the non-unit square-free proper divisors in the
components of the option of $n$. By induction, if this number is even if and
only if $\mathcal{SG}(n)=0$, we are done. Henceforth, we will ignore the
component of a heap of size one, since it has nim-value $0$ and will not
contribute to the disjunctive sum.

Suppose first that $n=p^{2}$ is a perfect square. Then the option is the prime
$p$, and hence $\mathcal{SG}(p^{2})=0$. Indeed, there is an odd number of
square-free non-unit divisors.

If $n=p^{t}$, $t>2$, is any other power of a prime, we must prove that
$\mathcal{SG}(n)=0$. The set of non-unit proper divisors is
$\\{p,\ldots,p^{t-1}\\}$, and hence there is exactly one square-free divisor
in the disjunctive sum $p+\cdots+p^{t-1}$. By induction, we get that each
component, except $p$ has nim-value $0$. This proves this claim.

Next, suppose $n=pq$, where $p$ and $q$ are primes. Then the option is $p+q$
of nim-value $1\oplus 1=0$. Hence $\mathcal{SG}(pq)=1$, and $n$ has an even
number of square-free non-unit proper divisors.

Similarly, if $n=p_{1}\cdots p_{j}$ is a product of distinct primes, then
$\mathcal{SG}(n)=1$. This follows, because the number of proper non-unit
divisors,

$\displaystyle\sum_{1\leq i<j}{j\choose i},$ (2)

is even, where $j$ is the number of prime factors in $n$ (this holds both for
even and odd $n$). And, by induction, each such individual component divisor
has nim-value 1. Note that, by moving in one such divisor, the number of
components in the disjunctive sum changes parity; if moved in a prime, then
the prime is deleted, if moved in $pq$, then this component splits to $p+q$,
and so on.

By combining these observations, we prove the general case of an arbitrary
prime factorization. Assume $n$ contains a square. We must show that
$\mathcal{SG}(n)=0$. By induction, we are concerned only with the square-free
divisor components, and we show that the number of such divisors is odd.

Indeed, if we assume $j$ in (2) is the number of distinct prime factors, then
there is one missing term, namely ${j\choose j}$. Namely, the divisor composed
of all square-free factors must be counted, whenever $n$ contains a square.
Apart from this, no new square-free divisor is introduced. Thus, the number of
such components is odd, and since by induction they have nim-value $1$, the
result $\mathcal{SG}(n)=0$ holds. ∎

We have investigated a few more of the fullset games, including those in the
subclass ‘subtraction’, but not yet found other examples with sufficient
regularity to prove basic correspondence with number theory. Apart from
fullset maliquot, this class, for now, remains a mystery. For example, for
fullset totient, the sequence starts $0,1,0,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0$.
The heap of size one has nim-value zero by definition, and the heap of size
two has nim-value one, because one is relatively prime with two.
$\mathcal{SG}(3)=0$, because the option is $1+2$ of nim-value $0\oplus 1=1$.
The sequence of the indices of the ones is $2,4,5,10,11,12,13,15$, and so on.
This sequence does not yet appear in OEIS.

##  6 Powerset games

We study six version of the powerset games on arithmetic functions, and we
begin by listing the first 20 nim-values for the respective ruleset. All start
at a heap of size one, except item 2, which starts at the empty heap (defined
as terminal).

  1. 1.

powerset maliquot: move-to an element in the powerset of the proper divisors.

$0,1,1,2,1,2,1,4,2,2,1,4,1,2,2,8,1,4,1.$

  2. 2.

powerset saliquot: subtract an element in the powerset of the divisors.

$0,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1.$

  3. 3.

powerset maliquant: move-to an element in the powerset of the non-divisors.

$0,0,1,0,2,1,4,8,16,2,32,1,64,4,128,8,256,16,512$

  4. 4.

powerset saliquant: subtract an element in the powerset of the non-divisors.

$0,0,1,1,2,1,4,4,8,2,16,8,32,32,64,64,128,8,256,64.$

  5. 5.

powerset totative: move-to an element in the powerset of the relatively prime
numbers smaller than the heap.

$0,1,2,1,4,1,8,1,2,1,16,1,32,1,2,1,64,1,128.$

  6. 6.

powerset nontotative: move-to an element in the powerset of the non-relatively
prime numbers smaller than the heap.

$0,0,0,1,0,2,0,4,1,8,0,16,0,32,4,64,0,128,0.$

For single heaps, these games tend to have nim-values powers of two. The
intuition of this is that by induction there is plenty opportunity, in a
powerset, to construct any number between the powers of two, by using various
sums of single heaps. We will study the precise behavior in a couple of
instances, namely items 2,3 and 5.

######  Theorem 15.

Consider powerset saliquot. Then $\mathcal{SG}(0)=0$, and
$\mathcal{SG}(n)=2^{p}$, if $2^{p}$ is largest power of two divisor of $n\geq
1$.

###### Proof.

A heap of size zero has nim-value 0 because it is terminal by definition. The
heap of size one has nim-value $1=2^{0}$, because $1\mid 1$. The heap of size
two has nim-value $2=2^{1}$, because $1,2\mid 2$, and
$\mathcal{SG}(2-1)=1,\mathcal{SG}(2-2)=0$. Both these cases satisfy the
largest power of two divisor criterion.

Suppose the statement holds for all numbers smaller than the heap size
$n=2^{p}a$, with $a$ odd, say. We must show that all nim-values less than
$2^{p}$ exist among the options of $n$. For each $q<p$, we will find a number
$0\leq m<n$ with $2^{q}$ largest power of $2$ divisor of $m$, and where $n-m$
is a divisor of $n$. For example with $m=n-2^{q}a\in\mathbb{N}$, then
$n-m=2^{q}a\mid n$, and $m=2^{q}a(2^{p-q}-1)$ has greatest power of two
divisor $2^{q}$. By induction, $\mathcal{SG}(m)=2^{q}$. Let $q$ range between
$0$ and $p-1$. By the rules of powerset, and by using the disjunctive sum
operator, this suffices to establish that all nim-values less than $2^{p}$
exist among the options of $n$.

Next, we must prove that the nim-value $2^{p}$ does not exist among the
options. It suffices to show that no individual heap in an option, which is a
disjunctive sum, is of the same form as $n$. This follows, since, by
induction, all numbers smaller than $n$ have nim-values powers of two, and
apply nim-sum.

A divisor of $n$ is of the form $2^{q}y$, where $y\mid a$ is odd, and where
$q\leq p$.

Suppose first $q=p$. Then $n-2^{p}y=2^{p}y(a/y-1)$. But $a/y$ is odd, and
hence $a/y-1$ is even, so $n-2^{p}y=2^{z}b$, with $z>p$ and $b$ odd, unless
$a=y$ when $n-2^{p}y=0$.

In case $q<p$, we get $n-2^{q}y=2^{q}y(2^{-q}n/y-1)$, and since $2^{-q}n/y-1$
is odd, by induction, the heap is not of the same form (since $q<p$). ∎

Recall the indexing function, $i_{o}$, of largest odd divisor, concerning the
singleton version of maliquant. It applies here as well with some initial
modification; while it looks like one could ‘peel’ off the $2$’s it does not
work due to the irregular set of initial nim-values.

######  Theorem 16.

Consider powerset maliquant. The sequence starts at a heap of size one, and
the first eight nim-values are, $0,0,1,0,2,1,4,8$. Otherwise, if $n=2k+1,k\geq
4$, then $\mathcal{SG}(n)=2^{k}$, and if $n\geq 10$ is even, then
$\mathcal{SG}(n)=\mathcal{SG}(n/2)$.

###### Proof.

The smaller heaps are easy to justify by hand. The heap of size 8 is pivotal.
It achieves nim-value 0, by the option $3+6$, both numbers being nondivisors.
And the nim-values $1,2,4$ may be combined freely by using the nondivisor
heaps $5,6,7$. Hence, the nim-values of the small heaps are verified.

For the base cases, we consider the heaps of sizes $9$ and $10$, of nim-values
$16=2^{4}$, with $2\cdot 4+1=9$ and $2=\mathcal{SG}(5)$ respectively.

For the induction, let us start with a heap of even size, $n=4t+2$, say. It
suffices to show that $\mathcal{SG}(n)=\mathcal{SG}(n/2)$. Observe that each
number between $n/2$ and $n$ is a nondivisor to $n$, and hence may be part of
a disjunctive sum to build desirable nim-values, by induction. Since
$n/2=2t+1$ is odd, each power of two $2^{4},\ldots,2^{t}$ appears among the
nim-values for heap sizes in $[9,n/2]$. By induction, each power of two
$2^{0},\ldots,2^{t-1}$ appears as a nim-value in the heap interval
$I=[n/2-1,\ldots n-1]$. Namely, for $y\in[0,t-1]$, multiply $2y+1$ by $2$
iteratively until $2^{s}(2y+1)\in I$. Thus all numbers smaller than $2^{t}$
appears as options, but note that the nim-value $2^{t}$ appears only as a nim-
value for a divisor of $n$, and hence this is the minimal exclusive. This
proves that $\mathcal{SG}(n)=2^{t}$, if $n$ is even, as desired.

Now, consider odd $n=2t+1$, say. By induction the nim-value of each heap
smaller than $n$ is less than $2^{t}$. In case of $t$ even, the powers of two,
$2^{t/2},\ldots,2^{t-1}$ appear for nim-values of odd heaps in the interval
$[t,\ldots,2t-1]$. And similar to the case for even $n$, the smaller power of
two nim-values can also be found in this interval. Therefore each nim-value
smaller than $2^{t}$ appear as an option of a disjunctive sum of non-divisors
of $n$. Hence, the minimal excusive is $\mathcal{SG}(n)=2^{t}$. ∎

Recall the function $i_{p}$, the index of the smallest prime divisor of $n$,
where the prime 2 has index 1, for the solution of totative, from Section 1.3.
It applies for the powerset game as well.

######  Theorem 17.

Consider powerset totative. Then $\mathcal{SG}(n)=2^{i-1}$, where $i=i_{p}$.

###### Proof.

The nim-value of a heap of size one is 0, since it is terminal. A heap of size
two has a move to the heap of size one, because 1 is relatively prime with all
numbers greater than 1. Hence $\mathcal{SG}(2)=1=2^{0}$. Suppose the statement
holds for all numbers smaller than $n>1$.

If $n$ is even, we must prove that there is a move to nim-value 0, but no move
to nim-value 1. The first part is done in the first paragraph. Hence, let us
show, by induction, that there is no move to nim-value 1. Since all smaller
heaps of odd size have even nim-values, then a disjunctive sum of nim-value 1
must contain a heap of even size. This is impossible, since heaps of even size
are not relatively prime with $n$.

Suppose that $n$ is odd, so that the index of the smallest prime divisor of
$n$ is $i>1$. We must show that $\mathcal{SG}(n)=2^{i-1}$. By induction, each
smaller prime divisor, with index $q<i$ say, has appeared in a heap size
smaller than $n$, with nim-value $2^{q-1}$. Since any disjunctive sum of heap
sizes relatively prime with $n$ is permitted as an option, by induction, each
nim-value smaller than $2^{i-1}$ can be obtained.

Next, we show that there is no option of nim-value $2^{i-1}$. This generalizes
the idea used in the second paragraph. A disjunctive sum of nim-value
$2^{i-1}$ must contain a component of nim-value $2^{i-1}$. But, by induction,
those heap sizes are not relatively prime with $n$. ∎

##  7 Discussion–future work

A natural generalization of counting the number of elements satisfying an
arithmetic function is to instead consider their sum, or partial sums. For
example, consider the sum generalization of the mtau, that is, the option of
$n$ is the sum of the proper divisors of $n$. For example $4$ has the proper
divisors $1$ and $2$ and therefore the option is $3$. Loops and cycles occur
for perfect numbers (those where the sum of proper divisors equals the number)
and (temporarily) increased heap sizes for abundant numbers (those where the
sum of proper divisors is greater than the number). The first loop appears at
$1+2+3=6$ (where ‘+’ is arithmetic sum).

This might at first sight seem to disqualify the Sprague-Grundy
function,999Fraenkel et al have developed a generalized Sprague-Grundy
function for cyclic short games. but in fact, since the game is binary, the
cycles are trivial, in the following sense. If we play a disjunctive sum of
games where one component will not end, then the full game will not end. And
reversely, if no component contains a cycle, but perhaps temporarily
increasing heap sizes, then the full game will end and a winner may be
declared. The nim-value sequence of this ruleset begins at a heap of size one,
as follows: $0,1,1,0,1,\infty,1,0,1,1,1,?$, where the infinity at heap size 6
indicates the loop, $1+2+3=6$.

Let us compute the nim-value for $n=12$, which is indicated by ‘?’ in the
sequence above. The sum of proper divisors is $16$ (temporary increase),
followed by options $15$ and $9$, in the next two moves. The sequence above
indicates that $\mathcal{SG}(9)=1$, and therefore, $\mathcal{SG}(12)=0$. The
recurrence where a number is mapped to the sum of its proper divisors has been
studied in number theory literature, without the games’ twist. It seems well
worthy some more attention.

Even more interesting is the same ruleset but where the player may pick any
partial sum of proper divisors. We have the following table, where for example
the options of a heap of size $4$ are $1,2$ and $1+2$.  $n$ $\mbox{opt}(n)$
$\mathcal{SG}(n)$ 1 $\varnothing$ 0 2 $1$ $1$ 3 $1$ $1$ 4 $1,2,3$ $2$ 5 $1$
$1$ 6 $1,2,3,4,5,6$ $\infty_{3}$ 7 $1$ $1$ 8 $1,2,3,4,5,6,7$ $\infty_{3}$ 9
$1,3,4$ $3$

Here $\infty_{3}$, means the nim-value 3, but with an additional option an
infinity, namely $\infty_{3}$. Consider for example the disjunctive sum of
heaps $6+9$. Then every move apart from playing to $\infty_{3}$ is losing. So,
this game is a draw. However, playing instead $6+7$, the first player wins by
moving to $2+7$, $3+7$ or $5+7$. That is, a loopy game component is sensitive
to the disjunctive sum. The $\omega$ game also seems to have an interesting
sum variation, but now we are ready to go and prepare some lunch.

Acknowledgement. This work started when the second author visited the first
author at the University of the Virgin Islands in April 2015. It breaks my
heart to acknowledge that the first author passed away 15 October 2020. Doug
is deeply missed. Many thanks to the referee, whose comments helped to improve
the readability of this paper.

## References

  * [1] E. R. Berlekamp, J. H. Conway, R. K. Guy. Winning Ways, Academic Press, London, 1982.
  * [2] C. Bouton, “Nim, a game with a complete mathematical theory,” _Annals of Math._ , 2nd ser., 3, no. 1/4, 35–39 (1901–2).
  * [3] A. Dailly, E. Duchene, U. Larsson, G. Paris, Partition games, _Discrete Applied Mathematics_ , 285, (2020) 509–525.
  * [4] P. Grundy, “Mathematics and games,” _Eureka_ 2, 6–8 (1939).
  * [5] G. H. Hardy and E. M. Wright, _An Introduction to the Theory of Numbers_ (5th ed.). Oxford: Clarendon Press (1979) [1938].
  * [6] H. Shapiro, An Arithmetic Function Arising from the $\Phi$ Function, _The American Mathematical Monthly_ , 50:1, 18-30 (1943).
  * [7] N. Sloane, _The On-Line Encyclopedia of Integer Sequences (OEIS)_ , website at http://oeis.org/.
  * [8] R. Sprague, “Über mathematische Kampfspiele,” _Tôhoku J. Math._ , 41, 438–444 (1936).