# Conway's surreal numbers and the Collatz iteration as a game?

Let us define a game based on the Collatz function $$C(n) = n/2$$ if $$n$$ is even, otherwise $$=3n+1$$.

Each number $$n$$ represents a game played by left $$L$$ and right $$R$$:

$$n = \{L_n | R_n \}$$

The rules of the game are:

If $$n$$ is even, the left player can play the game:

$$n = \{n/2 | \emptyset \}$$

If $$n \neq 1$$ is odd, the right player can play the game:

$$n = \{\emptyset| 3n+1 \}$$

If $$n=1$$, the game is over as no player can make a move:

$$n = \{\emptyset| \emptyset \}$$

Assuming the Collatz conjecture, this game starting with an arbitrary number $$n$$, has always an end.

So these games define surreal numbers and we could add and multiply, negate those games, which I think would be fun.

Q: How do I find the numeric value of these surreal numbers? Is there an algorithm to do this?

Example:

x7  =  (frozenset(), frozenset({x22}))
x22  =  (frozenset({x11}), frozenset())
x11  =  (frozenset(), frozenset({x34}))
x34  =  (frozenset({x17}), frozenset())
x17  =  (frozenset(), frozenset({x52}))
x52  =  (frozenset({x26}), frozenset())
x26  =  (frozenset({x13}), frozenset())
x13  =  (frozenset(), frozenset({x40}))
x40  =  (frozenset({x20}), frozenset())
x20  =  (frozenset({x10}), frozenset())
x10  =  (frozenset({x5}), frozenset())
x5  =  (frozenset(), frozenset({x16}))
x16  =  (frozenset({x8}), frozenset())
x8  =  (frozenset({x4}), frozenset())
x4  =  (frozenset({x2}), frozenset())
x2  =  (frozenset({x1}), frozenset())
x1  =  (frozenset(), frozenset())


sorted by value:

[1, 5, 13, 17, 11, 7, 9, 2, 10, 26, 34, 22, 14, 4, 20, 52, 28, 8, 40, 16]


Example Sage-Math-Script.

• also asked at MO, since I am not sure about the difficulty of the question: mathoverflow.net/questions/375541/… Nov 3, 2020 at 8:34
• Conway's games don't suit Collatz's conjecture well in that "Collatz's game" is naturally presented as a one player game with only one option at each turn. Also, it is unclear to me whether you are setting $n=\{\frac{n}{2}\ | \ \varnothing\}$ as a definition or if you are saying there is an equality. If $n$ is a natural number seen as a game, then $\{\frac{n}{2}\ | \ \varnothing\}$ is a well-defined game which is also a natural number, and we have $n=\{\frac{n}{2}\ | \ \varnothing\}$ if and only if $n=1$ or $n=2$. Nov 3, 2020 at 10:37
• @nombre: the example with $n=7$ should make clear what I mean. Nov 3, 2020 at 11:05
• If $n=7$, then the game $\{\varnothing \ | \ 3 n +1\}$ has value $0$ (this yields the same value for all natural numbers $n$). The thing is, there is no nice relation between $C(n)$ and $\{\varnothing \ | \ 3 n +1\}$. Nov 3, 2020 at 11:12
• @nombre: We have $v(1)=0$,$v(2)=1$,$v(4)=3$. I do not understand your claim, that every number has value 0. Nov 3, 2020 at 11:21

# Notation Issue

In Combinatorial Game Theory, integers like $$4$$ each denote a particular game or game value, like $$\{3\mid\,\}$$ (note that we don't write $$\varnothing$$ in this notation).

As nombre pointed out in the comments, the written equations like "$$n=\{\frac{n}{2}\mid\varnothing\}$$" are rarely/never true under standard notation for combinatorial games.

If you don't intend to be referencing the standard meanings of $$n$$, $$3n+1$$, and $$\frac{n}{2}$$ in this notation, you should either have a gigantic disclaimer that the usual notation does not apply, or just use something else for the games you would like to describe.

I'll use $$g(n)$$ where you have $$n$$, etc. So we have $$g(1)=\{\,\mid\,\}$$, $$g(n)=\{g(n/2)\mid\,\}$$ for even $$n$$, and $$g(n)=\{\,\mid g(3n+1)\}$$ for odd $$n>1$$. Technically, this is only a valid definition for all $$n$$ if the Collatz conjecture is true.

# Example Numeric Values

Let's start building a table and see if we see any patterns. $$g(1)=\{\,\mid\,\}=0$$. $$g(2)=\{g(1)\mid\,\}=\{0\mid\,\}=1$$. \begin{align}g(3)&=\{\,\mid g(10)\}\\&=\{\,\mid \{g(5)\mid\,\}\}\\&=\{\,\mid \{\{\,\mid g(16)\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{g(8)\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{g(4)\mid\,\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\{g(2)\mid\,\}\mid\,\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\{1\mid\,\}\mid\,\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{2\mid\,\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{3\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid 4\}\mid\,\}\}\\&=\{\,\mid \{0\mid\,\}\}\\&=\{\,\mid 1\}\\&=0\end{align} $$g(4)=2$$, $$g(5)=0$$, $$g(6)=\{g(3)\mid\,\}=\{0\mid\,\}=1$$. \begin{align}g(7)&=\{\,\mid g(22)\}\\&=\{\,\mid \{g(11)\mid\,\}\}\\&=\{\,\mid \{\{\,\mid g(34)\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{g(17)\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid g(52)\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{g(26)\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{g(13)\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{\{\,\mid g(40)\}\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{\{\,\mid \{g(20)\mid\,\}\}\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{\{\,\mid \{\{g(10)\mid\,\}\mid\,\}\}\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{\{\,\mid \{\{1\mid\,\}\mid\,\}\}\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{\{\,\mid \{2\mid\,\}\}\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{\{\,\mid 3\}\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{\{0\mid\,\}\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid \{1\mid\,\}\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{\{\,\mid 2\}\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid \{0\mid\,\}\}\mid\,\}\}\\&=\{\,\mid \{\{\,\mid 1\}\mid\,\}\}\\&=\{\,\mid \{0\mid\,\}\}\\&=\{\,\mid 1\}\\&=0\end{align}

## Claim

In general, the numeric value of $$g(n)$$ appears to be the highest exponent $$m$$ such that $$2^m$$ divides $$n$$.

# Proof

Let's assume, for induction, that the claim is true of all the values of $$g$$ that arise during the calculation of $$g(n)$$. Note that $$g(1)=0$$. If $$n$$ is even, then $$g(n)=\{g(n/2)\mid\,\}=g(n/2)+1$$, which matches the highest power of $$2$$ for $$n$$. If $$n$$ is odd and greater than $$1$$, then $$g(n)=\{\,\mid g(3n+1)\}$$. Since $$3n+1$$ is even, $$g(3n+1)\ge1$$, so that $$g(n)=0$$, as desired.

• So the OP's question gives a nice piecewise recursive definition of the $2$-adic valuation! Nov 3, 2020 at 12:28
• @nombre Yes, but $n+1$ in place of $3n+1$ would have done the same. Nov 3, 2020 at 12:34
• What changes if we replace $3n+1$ with $(3n+1)/2$ when $n$ is odd? Nov 3, 2020 at 19:09
• @MarkS. : I do not think that for even numbers your observation holds: For instance $g(14)=0$, see sagecell.sagemath.org/?q=ppddjg for more examples. Nov 4, 2020 at 7:34