46
$\begingroup$

This is a variant of Prime number building game.

Player $A$ begins by choosing a single-digit prime number. Player $B$ then appends any digit to that number such that the result is still prime, and players alternate in this fashion until one player loses by being unable to form a prime.

For instance, play might proceed as follows:

  • $A$ chooses 5
  • $B$ chooses 3, forming 53
  • $A$ loses since there are no primes of the form 53x

Is there a known solution to this game? It seems like I might be able to try a programmatic search...or might some math knowledge help here?

$\endgroup$
  • $\begingroup$ What does this game have to do with nim? $\endgroup$ – Wojowu Dec 21 '18 at 6:54
  • 5
    $\begingroup$ Seems unlikely that there's anything better you can do than just listing out the whole game tree by brute force. $\endgroup$ – Eric Wofsey Dec 21 '18 at 6:59
  • $\begingroup$ Edited title. I think I had confused nim with this game's misère win condition. $\endgroup$ – scip Dec 21 '18 at 7:00
  • 4
    $\begingroup$ The game has a determinate winning strategy for the second player (see answers) if by 'append' you restrict adding digits to the right. A more complex version would allow a player to append a digit either to the right or the left. It's not clear to me that the game so enlarged would be so straight forward to analyze. $\endgroup$ – Keith Backman Dec 21 '18 at 17:51
  • $\begingroup$ @KeithBackman As regards your variant I edited my answer with a P.S. $\endgroup$ – Robert Z Dec 23 '18 at 9:28
73
$\begingroup$

The game is trivial to brute force; there just aren't very many possibilities. Assuming I have not made a mistake brute-forcing it by hand (with the aid of a computer to test for primality), the second player to move can win via the following strategy (this is not the only winning strategy):

  • If the first player starts with $2$, move to $29$, and then all the moves are forced until you win at $29399999$
  • If the first player starts with $3$, move to $37$. If they then move to $373$, move to $3733$ and you will win no matter what (at either $37337999$ or $373393$). If they instead move to $379$, you move to either $3793$ or $3797$ and win immediately.
  • If the first player starts with $5$, move to $53$ and win.
  • If the first player starts with $7$, move to $71$ and then every move is forced until you win at $719333$.

As a heuristic for why it should not be surprising that the game is so limited, note that by the prime number theorem, there are about $\frac{N}{\log N}$ primes less than $N$, so the probability of a random $n$-digit number being prime is about $\frac{1}{\log(10^n)}=\frac{1}{n\log(10)}$. Assuming that the primality of a number is independent from the primality of a number obtained by adding a digit at the end (which seems like a reasonable heuristic assumption), this gives that there are about $\frac{10}{\log(10)}$ $1$-digit numbers that are valid positions in this game, and then $\frac{10}{\log(10)}\cdot\frac{10}{2\log(10)}$ $2$-digit numbers, and in general $\frac{10^n}{n!\log(10)^n}$ $n$-digit numbers. Adding up all the valid positions (including the empty string at the start) gives about $$\sum_{n=0}^\infty\frac{10^n}{n!\log(10)^n}=e^{10/\log(10)}\approx 77$$ total positions. In fact, this heuristic estimate is not far from the actual value, which is $84$.

$\endgroup$
  • 11
    $\begingroup$ I like the heuristic argument! (+1) $\endgroup$ – Robert Z Dec 21 '18 at 8:08
44
$\begingroup$

As mentioned by others, it isn't too hard to create the whole trie.

Player $A$ is green and Player $B$ is orange:

enter image description here

For reference purposes, here's the corresponding Python code. It uses networkx and graphviz:

import networkx as nx
from networkx.drawing.nx_agraph import to_agraph

def is_prime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for d in range(3, int(n**0.5) + 1, 2):
        if n % d == 0:
            return False
    return True


def add_prime_leaves_recursively(current_number=0, current_representation='',
                                 base=10, graph=nx.DiGraph(), level=0,
                                 colors=['#FF851B', '#2E8B57']):
    graph.add_node(current_number,
                   label=current_representation,
                   color=colors[level % 2])
    for next_digit in range(base):
        next_number = current_number * base + next_digit
        if is_prime(next_number):
            graph.add_edge(current_number, next_number)
            add_prime_leaves_recursively(
                next_number,
                current_representation + '0123456789ABCDEFGHIJ'[next_digit],
                base, graph, level + 1)
    return graph


G = add_prime_leaves_recursively(base=10)
G.nodes[0]['color'] = 'black'

A = to_agraph(G)
A.draw('prime_number_construction_game.png', prog='dot')

This code can generate the diagram for any base below 20. The game is boring in base 3:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Beautiful code and image! $\endgroup$ – Vincent Dec 21 '18 at 13:57
30
$\begingroup$

Since there are "only" 83 right-truncatable primes (and 4260 left-truncatable primes), the game is a finite impartial game (like Nim) and for each position we can compute the corresponding Grundy value. So for example $g(53)=0$. This game is trivial to brute force, but by computing the Grundy values we can consider non-trivial combined games.

Note the second player, i.e. player $B$, has a winning strategy:

  • If player $A$ starts with $2$, then player $B$ appends a $9$ and the game is forced to $29399999$.

  • If player $A$ starts with $3$, then player $B$ appends a $7$, and the game is forced to $3793$, or $373393$, or $37337999$.

  • If player $A$ starts with $5$, then player $B$ appends a $3$.

  • If player $A$ starts with $7$, then player $B$ appends a $1$ and the game is forced to $719333$.

P.S. Also the variant proposed by Keith Backman, where a player is allowed to append a digit either to the right or the left, is a finite impartial game. In fact left- or right-truncatable primes are finite, with $149677$ terms (see OEIS A137812) and the largest one is $8939662423123592347173339993799$, so any game ends in at most $31$ moves.

$\endgroup$
  • 1
    $\begingroup$ I guess the tow direction game was easier to analyze than I naively imagined. Thanks for the fun analysis. $\endgroup$ – Keith Backman Dec 23 '18 at 21:37
  • $\begingroup$ @KeithBackman It seems that also in your variant the second player has a winning strategy but the analysis is much harder. $\endgroup$ – Robert Z Dec 24 '18 at 15:06

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.