28
$\begingroup$

Many years ago, a coworker showed me a programming problem involving a combinatorial game with prime numbers that he had gotten somewhere or other. (For some reason, he refused to tell me the source.) Actually it is an infinite family of games, depending on an integer $N \ge 2.$ The first player names some prime $p_1 \le N.$ Then the second player names some prime $p_1 <p_2 \le p_1+N.$ The game continues in this manner. Whenever a player names a prime $p_k,$ his opponent must name a prime $p_k <p_{k+1}\le p_k+N.$ The first player who is unable to name a prime loses. Of course, we assume that the players have unlimited tables of the primes available.

The programming problem is to write a function that will take $N$ as input and produce as output the prime that the first player should say on his first move in order to win, or $0$ if there is no such prime. It's easy to see what the optimum strategy is. Let $\pi_1$ be the smallest prime such that $\pi_1+k \text{ is composite } k=1,2,\cdots,N.$ Then the player who names $\pi_1$ wins. Then then $\pi_2$ be that largest prime such that $\pi_2 <\pi_1-N.$ Then the player who names $\pi_2$ wins. However, this is completely impractical, because even for rather small values of $N,$ $\pi_1$ is enormous.

Another friend and I solved the problem by starting from $2$ and going forward, rather than trying to go backwards from $\pi_1.$ For each prime $p$, we pretend that the goal of the game is to name $p$ and we label $p$ with the first move necessary to name it. For $p\le N,$ the label is just $p$. Then working through the primes, we label each $p$ with the label of the largest prime less than $p-N$. So for example, if $N=23,$ we label the primes up through $23$ with themselves, and then we label $29$ with the label of the largest prime less than $29-23,$ that is $5.$ Then we label $31$ with $7$ and $37$ with $13$. Later on, when we come to label $61,$ it gets the same label as $37,$ namely $13.$

What we find as we fill out the table is that we rather quickly get to an interval $I$ of length $N$ in which all the primes have the same label. Then this label will be the winning first move (or it will be $0$ if there is no such move.) The reason is, that in working backward from $\pi_1$ there is no way to skip over the interval $I$. $I$ must contain a winning prime, and while we don't know what it is, we know its label.

I found this solution very satisfying, and have always looked back on it fondly, but it has always bothered me that we have only empirical evidence that it works well. I recently wrote a program to compute the value up to $N=10,001$ and the the largest prime encountered was $2,030,647,991.$ According to the Wikipedia article on prime gaps, the largest known maximal gap as of October $2017$ is $1510$, occurring after the prime $6,787,988,999,657,777,797.$ This would be the $\pi_1$ value for $N=1509,$ for which my program only needed to go up to $6,307,507.$

My question is, does anybody know how to bound the largest prime that this algorithm would require to compute the first move for $N$? I would be interested in any kind of of result, including a heuristic "probabilistic" argument.

By the way, if you want to program this yourself, note that it's only necessary to compute the values for the odd numbers. A little thought shows that the winning first moves for $N=2n+1$ and $N=2n$ will be the same, except that if the winning first move when $N=2n+1$ is $N,$ then $N=2n$ is a loss for the first player, and if $N=2n+1$ is a loss for the first player, then the winning first move in $N=2n$ is $2.$

EDIT Results for $N\le 100:$

2 0 11
3 3 11
4 0 29
5 5 29
6 5 79
7 5 79
8 7 127
9 7 127
10 7 97
11 7 97
12 7 127
13 7 127
14 7 149
15 7 149
16 13 127
17 13 127
18 3 173
19 3 173
20 13 307
21 13 307
22 13 787
23 13 787
24 23 191
25 23 191
26 23 1009
27 23 1009
28 23 367
29 23 367
30 13 787
31 13 787
32 31 1361
33 31 1361
34 23 1361
35 23 1361
36 31 1361
37 31 1361
38 13 907
39 13 907
40 29 853
41 29 853
42 0 1361
43 43 1361
44 19 1031
45 19 1031
46 31 2437
47 31 2437
48 37 1423
49 37 1423
50 7 1151
51 7 1151
52 29 1277
53 29 1277
54 53 1361
55 53 1361
56 19 4327
57 19 4327
58 13 3433
59 13 3433
60 47 2333
61 47 2333
62 3 5381
63 3 5381
64 61 1693
65 61 1693
66 31 4127
67 31 4127
68 67 1811
69 67 1811
70 17 2999
71 17 2999
72 13 2027
73 13 2027
74 37 2609
75 37 2609
76 31 2371
77 31 2371
78 31 1361
79 31 1361
80 2 8263
81 0 8263
82 0 8263
83 83 8263
84 79 12889
85 79 12889
86 47 4547
87 47 4547
88 19 4001
89 19 4001
90 37 10007
91 37 10007
92 83 3407
93 83 3407
94 5 5623
95 5 5623
96 83 7283
97 83 7283
98 89 4441
99 89 4441
100 37 8501

The first number is $N,$ the second number is the winning move (or $0$) the third is the largest prime used in the calculation.

$\endgroup$
  • $\begingroup$ According to the rules, he must name a number $\le N.$ At each subsequent turn, the player is allowed to add no more that $N$ to the current prime. $\endgroup$ – saulspatz Feb 9 '18 at 22:03
  • $\begingroup$ I missed that in the quick read. $\endgroup$ – Ross Millikan Feb 9 '18 at 22:12
  • $\begingroup$ What is the answer if $N=23$ ? $\endgroup$ – Yuri Negometyanov Mar 30 '18 at 14:30
  • $\begingroup$ @YuriNegometyanov 13 $\endgroup$ – saulspatz Mar 30 '18 at 16:47
  • $\begingroup$ Seems interesting,thanks. And some another $N<350,$ please. $\endgroup$ – Yuri Negometyanov Mar 30 '18 at 16:53
5
+500
$\begingroup$

Yeah, but I based the coefficient guess on the largest prime observed up to $N$ and $2526959$ for $N=997$ or $3658283$ for $N=1138$ are more or less in line with my bet :-).

They have to vary widely because what is actually predicted is not an asymptotics but a distribution (i.e. $c$ is technically not a constant but a random variable with some limiting distribution that may be quite a headache to discern).

Here is the computation. The primes in $[0,M]$ are like random integers where any particular integer is picked independently with probability $p=(\log M)^{-1}$. Now we take a pair of primes separated by $\approx N$ near the end and ask if they have the same label. Let the distance between them be $a$. Go back by $N$ and see by how much the primes they refer to for their labeling are separated. The observation is that that separation changes by a random amount that is typically of order $p^{-1}$ and changes up or down are (about) equally likely. If we go back to $N$, we restart the game. Otherwise we have a random walk with steps like $\log M$ that moves on $[0,N]$. If we hit $0$, the labels get the same. So we want to know how soon we hit $0$ under such circumstances. The typical time is of order $(N/\log M)^2$ (assuming no drift, which seems correct at least in the "mittelspiel" when $a$ is far from both $0$ and $N$). Each step consumes $N$ units of the real space, whence the typical largest used prime should satisfy $M\asymp N^3/(\log^2 M)$, which is pretty much the same as I tried to predict.

This isn't worth a worn penny, of course, as far as the original problem is concerned because the very first assumption that primes are just random points is too naive to make an attempt to convert the rest of the argument into something more rigorous than the crude order of magnitude count worth anything, though if somebody wants to investigate the probabilistic version of the game just for the fun of it, it can make a fairly decent project. But you asked and I answered :-)

Edit This is to answer the two questions that saulspatz asked.

1) You have two "random primes" $p,q$ with $q-p=a$ and you are looking at their reference primes $p'<p-N,q'<q-N$. If $a$ is not too small, the distance from $p'$ to $p-N$ is a random variable $X$ essentially independent of and equidistributed with the distance $Y$ from $q'$ to $q-N$ (just look at what sites determine it and take into account that the stretch of length much more than $\log M\ll a$ free of random primes is highly unlikely), so $a$ changes to $a+X-Y$ but $X-Y$ is almost perfectly symmetric and the typical values of $X$ and $Y$ are about $\log M$, so their difference is of the same size. That's where the random walk approximation comes from.

2) You have a random walk on $[0,N]$ with typical step $\log M$ and resetting if you hit $N$. The question is how soon you hit $0$. If you think a bit, you'll realize that it is very close to asking how soon an unrestricted random walk starting at $0$ hits $N$ or $-N$. You do not need to remember much, just the general idea that after $Q$ steps you are typically about $\sqrt Q$ times the step length away, so if you want to be $R$ step lengths away, the typical time for that is $R^2$. The more careful computation (for which you need to formalize the word "typical" to "mean", "median", or something else) seems like a waste of time anyway (because the model itself is rather crude to start with), so I stopped where I stopped without trying to make any predictions about the distribution of $c$, etc. Also my impression was that the prediction of the rough order of magnitude with some simple (or, if you prefer, simplistic) explanation of why it should be so that fits the data decently is what you were primarily interested in. :-).

$\endgroup$
  • $\begingroup$ Two question. First, you say " The observation is that that separation changes by a random amount ...." Do you mean an empirical observation? Second, you say "The typical time is of order $(N/\log M)^2$..." Is this a result from random walk theory? (I've forgotten the little I ever knew about that.) $\endgroup$ – saulspatz Apr 3 '18 at 18:43
  • $\begingroup$ @saulspatz I tried to answer. See if what I wrote makes sense to you :-) $\endgroup$ – fedja Apr 3 '18 at 22:48
  • $\begingroup$ Makes sense to me. This argument is the kind I was thinking of when I said, "I would be interested in any kind of of result, including a heuristic 'probabilistic' argument." Thanks a bunch. $\endgroup$ – saulspatz Apr 3 '18 at 22:53

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.