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?

Answer

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 NlogN primes less than N, so the probability of a random n-digit number being prime is about 1log(10n)=1nlog(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 10log(10) 1-digit numbers that are valid positions in this game, and then 10log(10)102log(10) 2-digit numbers, and in general 10nn!log(10)n n-digit numbers. Adding up all the valid positions (including the empty string at the start) gives about n=010nn!log(10)n=e10/log(10)77 total positions. In fact, this heuristic estimate is not far from the actual value, which is 84.

Attribution
Source : Link , Question Author : scip , Answer Author : Eric Wofsey

Leave a Comment