2
$\begingroup$

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.

$\endgroup$
6
  • $\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

2
$\begingroup$

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.

$\endgroup$
10
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.