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?


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.

  • $\begingroup$ also asked at MO, since I am not sure about the difficulty of the question: mathoverflow.net/questions/375541/… $\endgroup$ Nov 3, 2020 at 8:34
  • 2
    $\begingroup$ 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$. $\endgroup$
    – nombre
    Nov 3, 2020 at 10:37
  • $\begingroup$ @nombre: the example with $n=7$ should make clear what I mean. $\endgroup$ Nov 3, 2020 at 11:05
  • 2
    $\begingroup$ 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\}$. $\endgroup$
    – nombre
    Nov 3, 2020 at 11:12
  • $\begingroup$ @nombre: We have $v(1)=0$,$v(2)=1$,$v(4)=3$. I do not understand your claim, that every number has value 0. $\endgroup$ Nov 3, 2020 at 11:21

1 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}$$


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


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.

  • $\begingroup$ Thank your for your detailed answer. $\endgroup$ Nov 3, 2020 at 12:27
  • $\begingroup$ So the OP's question gives a nice piecewise recursive definition of the $2$-adic valuation! $\endgroup$
    – nombre
    Nov 3, 2020 at 12:28
  • $\begingroup$ @nombre Yes, but $n+1$ in place of $3n+1$ would have done the same. $\endgroup$
    – Mark S.
    Nov 3, 2020 at 12:34
  • $\begingroup$ What changes if we replace $3n+1$ with $(3n+1)/2$ when $n$ is odd? $\endgroup$ Nov 3, 2020 at 19:09
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 4, 2020 at 7:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .