1
$\begingroup$

This question is not a duplicate of the previous, because here we use a different function and get different values for the games:

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

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

$$g(n) = \{L_n | R_n \}$$

The rules of the game are:

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

$$g(n) = \{g(n/2) | \}$$

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

$$g(n) = \{| g((3n+1)/2) \}$$

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

$$g(n)=g(1) = \{| \}$$

Assuming the Collatz conjecture is true, 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 and what interpretation can be given to these values?

Here are some examples, but I do not see any pattern, where $g(n)$ denotes the numerical value of $n$:

$n,g(n)$

1 0
2 1
3 -1
4 2
5 0
6 0
7 -2
8 3
9 -1
10 1
11 -1
12 1
13 0
14 0
15 -3
16 4
17 0
18 0
19 -1
20 2
21 0
22 0
23 -2
24 2
25 -1
26 1

Some more examples in SAGEMATH

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

$\endgroup$
4
  • 2
    $\begingroup$ Does this answer your question? Conway's surreal numbers and the Collatz iteration as a game? $\endgroup$ Nov 4, 2020 at 17:07
  • $\begingroup$ @JoséCarlosSantos After an answer was accepted to that other question, stackExchangeUser edited this question into it (~21 hours ago), and then posted it as this new question ~6 hours ago. Rather than mark this as a duplicate, I think the edit to the other question should be removed as this is a distinct and more subtle question. $\endgroup$
    – Mark S.
    Nov 4, 2020 at 17:58
  • $\begingroup$ @JoséCarlosSantos: This is not a duplicate question as explained by MarkS. I will remove the edit to the previous question. $\endgroup$ Nov 4, 2020 at 18:11
  • $\begingroup$ @MarkS. Thanks for pointing out the difference in the questions. I will remove the edit to the previous question. $\endgroup$ Nov 4, 2020 at 18:11

1 Answer 1

1
$\begingroup$

Setup

I have a characterization, but the answer is pretty complicated. These definitions depend on the Collatz conjecture being true.

I will define a function related to the Collatz conjecture that associates strings of "$\mathrm{E}$"s and "$\mathrm{O}$"s to the positive integers. I will use multiplicative notation for concatenating strings, so that $\mathrm{E}\left(\mathrm{OE}\right)=\mathrm{EOE}$ and $\mathrm{E}^{3}=\mathrm{EEE}$. Define $C\left(1\right)$ to be the empty string. Then, for $n>1$, define $C(n)=\begin{cases} \mathrm{E}C\left(\frac{n}{2}\right) & \text{if }n\text{ is even}\\ \mathrm{O}C\left(\frac{3n+1}{2}\right) & \text{if }n\text{ is odd} \end{cases}$. For example, $C\left(7\right)=\mathrm{OOOEOEEOEEE}$, with the tail $\mathrm{OEEE}$ coming from $5\overset{\mathrm{O}}{\to}8\overset{\mathrm{E}}{\to}4\overset{\mathrm{E}}{\to}2\overset{\mathrm{E}}{\to}1)$. We can abbreviate this as $C\left(7\right)=\mathrm{O}^{3}\mathrm{E}^{1}\mathrm{O}^{1}\mathrm{E}^{2}\mathrm{O}^{1}\mathrm{E}^{3}$.

Answer

We can express the values of $g$ in terms of $C$ in a relatively simple way. Note that $g\left(1\right)=0$ by definition. For $n>1$, we have the following piecewise formula, where $m\ge1$ is the length of the initial run and $k\ge0$:

$$ g\left(n\right)=\begin{cases} \begin{cases} m-1 & \text{if }C\left(n\right)=\mathrm{E}^{m}\left(\mathrm{OE}\right)^{k}\mathrm{O}^{2}\cdots\\ m & \text{if }C\left(n\right)=\mathrm{E}^{m}\cdots\text{ otherwise} \end{cases} & \text{if }n\text{ is even}\\ \begin{cases} 1-m & \text{if }C\left(n\right)=\mathrm{O}^{m}\left(\mathrm{EO}\right)^{k}\mathrm{E}^{2}\cdots\\ -m & \text{if }C\left(n\right)=\mathrm{O}^{m}\cdots\text{ otherwise} \end{cases} & \text{if }n\text{ is odd} \end{cases} $$ In other words, using $\mathrm{A}$ and $\mathrm{B}$ as stand-ins for $\mathrm{E}$ and $\mathrm{O}$ in some order, and $\left[\mathrm{A}=\mathrm{O}\right]=\begin{cases} 0 & \text{if }\mathrm{A}=\mathrm{E}\\ 1 & \text{if }\mathrm{A}=\mathrm{O} \end{cases}$, we have: $$ g\left(n\right)=\left(-1\right)^{\left[\mathrm{A}=\mathrm{O}\right]}*\begin{cases} m-1 & \text{if }C\left(n\right)=\mathrm{A}^{m}\left(\mathrm{BA}\right)^{k}\mathrm{B}^{2}\cdots\\ m & \text{otherwise} \end{cases} $$

Proof

Since $C\left(n\right)$ determines $n$, I will define $G:\text{strings}\to\mathbb{N}$ so that $g\left(n\right)=G\left(c\right)$ if $c=C\left(n\right)$. In order to show that the above formula for $g$/$G$ is correct for $n>1$, we can induct on the number of alternations between $\mathrm{O}$ and $\mathrm{E}$.

Base cases

Firstly, $G\left(\mathrm{E}^{m}\right)=m$ (including if $m=0$) by a straightforward induction on $m$. And secondly, for $j\ge1$, $$G\left(\mathrm{O}^{j}\mathrm{E}^{m}\right)=\left\{ \mid G\left(\mathrm{O}^{j-1}\mathrm{E}^{m}\right)\right\} =\begin{cases} G\left(\mathrm{O}^{j-1}\mathrm{E}^{m}\right)-1 & \text{if }G\left(\mathrm{O}^{j-1}\mathrm{E}^{m}\right)\le0\\ 0 & \text{if }G\left(\mathrm{O}^{j-1}\mathrm{E}^{m}\right)>0 \end{cases}\text{.}$$ Note that we must have $m\ge3$ (as $1,2,4$ can't be reached from an odd number $n>1$). Therefore, $G\left(\mathrm{E}^{m}\right)>0$ and $G\left(\mathrm{O}\mathrm{E}^{m}\right)=0$. By induction on $j$, $G\left(\mathrm{O}^{j}\mathrm{E}^{m}\right)=1-j$. This agrees with the formula since $m\ge3$, so this has the form $G\left(\mathrm{O}^{j}\left(\mathrm{EO}\right)^{0}\mathrm{E}^{2}\cdots\right)$.

Induction step

E

Assume, for induction purposes, that the formula for $G$ holds for all strings with a given number of alternations that begin with $\mathrm{E}$, so that $G\left(\mathrm{E}^{\ell}\cdots\right)=\begin{cases} \ell-1 & \text{if }\mathrm{E}^{\ell}\left(\mathrm{OE}\right)^{k}\mathrm{O}^{2}\cdots\\ \ell & \text{otherwise} \end{cases}$.

Then we have $$G\left(\mathrm{O}\mathrm{E}^{\ell}\cdots\right)=\begin{cases} \begin{cases} -1 & \text{if }\mathrm{O}\mathrm{E}^{\ell}\left(\mathrm{OE}\right)^{k}\mathrm{O}^{2}\cdots\\ 0 & \text{otherwise} \end{cases} & \text{if }\ell=1\\ 0 & \text{if }\ell>1 \end{cases}=\begin{cases} -1 & \text{if }\left(\mathrm{OE}\right)^{k+1}\mathrm{O}^{2}\cdots\\ 0 & \text{otherwise} \end{cases}\text{.}$$ And $G\left(\mathrm{E}\mathrm{O}\mathrm{E}^{\ell}\cdots\right)=\begin{cases} 0 & \text{if }\mathrm{E}\left(\mathrm{OE}\right)^{k+1}\mathrm{O}^{2}\cdots\\ 1 & \text{otherwise} \end{cases}$. Since those values are nonnegative, we can conclude that $G\left(\mathrm{E}^{m}\mathrm{O}\mathrm{E}^{\ell}\cdots\right)=\begin{cases} m-1 & \text{if }\mathrm{E}^{m}\left(\mathrm{OE}\right)^{k+1}\mathrm{O}^{2}\cdots\\ m & \text{otherwise} \end{cases}$.

For higher powers of $\mathrm{O}$, now consider $G\left(\mathrm{O}^{2}\mathrm{E}^{\ell}\cdots\right)=\begin{cases} -2 & \text{if }\mathrm{O}\left(\mathrm{OE}\right)^{k+1}\mathrm{O}^{2}\cdots\\ -1 & \text{otherwise} \end{cases}$. And so, for $j\ge2$, $G\left(\mathrm{O}^{j}\mathrm{E}^{\ell}\cdots\right)=\begin{cases} -j & \text{if }\mathrm{O}^{j-1}\left(\mathrm{OE}\right)^{k+1}\mathrm{O}^{2}\cdots\\ 1-j & \text{otherwise} \end{cases}$. Since these are all negative, $G\left(\mathrm{E}\mathrm{O}^{j}\mathrm{E}^{\ell}\cdots\right)=0$, and $G\left(\mathrm{E}^{m}\mathrm{O}^{j}\mathrm{E}^{\ell}\cdots\right)=m-1$. Note that $\mathrm{E}^{m}\mathrm{O}^{j}\mathrm{E}^{\ell}\cdots$ has the form $\mathrm{E}^{m}\left(\mathrm{OE}\right)^{0}\mathrm{O}^{2}\cdots$, so this agrees with our formula.

O

The induction steps for adding two alternations that begin with $\mathrm{O}$ are completely analogous. Just flip signs and swap $\mathrm E$ and $\mathrm O$.

Commentary

The formula for $g$ depends on $C$, which basically requires us to run through an unbounded amount of steps of the Collatz sequence for a number, which is not ideal. It also doesn't have an obvious tidy characterization that's not recursive, like "write the $\mathrm{EO}$ string with $1$s and $0$s in a certain way, and then do something with the number to get the value of $G$".

Simple cases

The only thing I could think to do is collect together some simple cases that have a fixed form; but nothing can be done for the general case as that essentially requires you to prove Collatz.

For example, the numbers with $C\left(n\right)=\mathrm{E}^{m}$ are the powers of $2$, with $g\left(2^{m}\right)=m$. These are A000079 in the OEIS.

The numbers of the form $\mathrm{O}\mathrm{E}^{n}$ are those of the form $(4^{k}-1)/3$ for $k\ge1$ (A002450), and they have $g\left(n\right)=0$.

The numbers of the form $\mathrm{O}^{2}\mathrm{E}^{m}$ are those of the form $\left(64^{k}-10\right)/18$ for $k\ge1$ (A228871), and they have $g\left(n\right)=-1$.

The numbers of the form $E^{m}\mathrm{O}\mathrm{E}^{\ell}$ are those of the form $2^{m}(4^{k}-1)/3$ for $k\ge1$ (A181666), and have $g\left(n\right)=m$.

The numbers of the form $E^{m}\mathrm{O^{2}}\mathrm{E}^{\ell}$ are those of the form $2^{m}\left(64^{k}-10\right)/18$ for $k\ge1$ (no OEIS entry), and have $g\left(n\right)=m-1$.

The numbers of the form $\mathrm{O}\mathrm{E}^{m}\mathrm{O}\mathrm{E}^{\ell}$ have one of the two forms $\dfrac{4^{3k+r}-4^{r+1}-6}{18}$ or $\dfrac{4^{3k+r}-4^{r+2}-48}{144}$, etc.

Simpler Code

Your Sage code appears to be doing all of the work of the Conway notation. But since these games only have one move for one of the two players, you can calculate values of $g$ in a much more straightforward way. I imagine you could port the following code to Sage if desired:

Wolfram Language (Mathematica)

g[x_] := g[x] = If[x == 1, 0, 
  If[Mod[x, 2] == 0, If[g[x/2] >= 0, g[x/2] + 1, 0], 
   If[g[(3 x + 1)/2] <= 0, g[(3 x + 1)/2] - 1, 0]]];
Table[g[x],{x,1,10000}]//Print

Try it online!

$\endgroup$
11
  • $\begingroup$ Thanks for your very detailed answer. (+1) I will need some time to understand what you have written and accept the answer. $\endgroup$ Nov 5, 2020 at 7:12
  • $\begingroup$ @stackExchangeUser I want to emphasize that the bulk of my answer has nothing to do with Collatz, really. It's more answering something like "if you switch between two cases and jump to other numbers by some rule (e.g. Collatz), how does the 'Left game and right game' construction produce values?" I can't think of an application/reason for the left game and right game construction (if there's more context, add to your question) and my answer certainly cannot shed any light on Collatz, by design. $\endgroup$
    – Mark S.
    Nov 5, 2020 at 13:43
  • $\begingroup$ It would be interesting to investigate what happens, when we add two games known to iterate to $1$ by the modified Collatz function. $\endgroup$ Nov 5, 2020 at 15:33
  • $\begingroup$ @stackExchangeUser all of these games are integers. So we would just get the sum of those integers. $\endgroup$
    – Mark S.
    Nov 5, 2020 at 15:48
  • 1
    $\begingroup$ Ok thanks I am reading "Lessons in Play, An introduction to Combinatorial Game Theory", which is pretty good and I hope to gain some insight from this. Thanks again for your help! $\endgroup$ Nov 7, 2020 at 14:01

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.