# Prime number construction game

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?

• What does this game have to do with nim? – Wojowu Dec 21 '18 at 6:54
• Seems unlikely that there's anything better you can do than just listing out the whole game tree by brute force. – Eric Wofsey Dec 21 '18 at 6:59
• Edited title. I think I had confused nim with this game's misère win condition. – scip Dec 21 '18 at 7:00
• 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. – Keith Backman Dec 21 '18 at 17:51
• @KeithBackman As regards your variant I edited my answer with a P.S. – Robert Z Dec 23 '18 at 9:28

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$$.

• I like the heuristic argument! (+1) – Robert Z Dec 21 '18 at 8:08

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

Player $$A$$ is green and Player $$B$$ is orange: 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

base=10, graph=nx.DiGraph(), level=0,
colors=['#FF851B', '#2E8B57']):
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):
next_number,
current_representation + '0123456789ABCDEFGHIJ'[next_digit],
base, graph, level + 1)
return graph

G.nodes['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: • Beautiful code and image! – Vincent Dec 21 '18 at 13:57

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.

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