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

Question

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.

Answer 1

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.