50
$\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$
5
  • $\begingroup$ What does this game have to do with nim? $\endgroup$
    – Wojowu
    Dec 21, 2018 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$ Dec 21, 2018 at 6:59
  • $\begingroup$ Edited title. I think I had confused nim with this game's misère win condition. $\endgroup$
    – scip
    Dec 21, 2018 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$ Dec 21, 2018 at 17:51
  • $\begingroup$ @KeithBackman As regards your variant I edited my answer with a P.S. $\endgroup$
    – Robert Z
    Dec 23, 2018 at 9:28

3 Answers 3

74
$\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$
1
  • 12
    $\begingroup$ I like the heuristic argument! (+1) $\endgroup$
    – Robert Z
    Dec 21, 2018 at 8:08
43
$\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
  • 2
    $\begingroup$ Beautiful code and image! $\endgroup$
    – Vincent
    Dec 21, 2018 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$
2
  • 1
    $\begingroup$ I guess the tow direction game was easier to analyze than I naively imagined. Thanks for the fun analysis. $\endgroup$ Dec 23, 2018 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, 2018 at 15:06

You must log in to answer this question.

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