Analysis of a combinatorial game with prime numbers

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. :-).