6
$\begingroup$

Consider a single-pile NIM variant, played under standard (not misere) objective, with the rule that you may remove any prime number from the pile. The winning positions of this game are all numbers $a_n$ where $a_0 = 0$ and for $A \equiv \{a_n\}$ consists of all numbers which are not of the form $p+a_k : p \text{ prime}, k<n$. (This sequence appears, to 10,000 terms, in OEIS as A025043.)

What is the asymptotic density (and if that is zero, bounds on a counting function) of winning positions?

Knowing the counting function of primes, one can frame a probabilistic argument about the likelihood that a given number $k \in A$ by solving an integral equation that looks something like $$ D(x) = 1 - \int_1^u\frac{D(u)}{\log u} du $$ (and you don't even have to solve the equation, just determine the asymptotic behavior of the solution). But that, of course, does not prove anything, since the primes could easily conspire to make the distribution different than that naive probability argument would suggest.

$\endgroup$
  • $\begingroup$ The integral equation is clearly wrong. If probability that $u$ is in the set is $D(u)$ and all of these are somehow independent, then the probability that $x$ is in not in the set is $\prod_u (1-D(x-u)/\log u)$. Assuming continuous approximation, this gives $\exp(-\int \frac{D(x-u)}{\log u}\,du)$. Of course, the events are not independent, and one has to worry (at bare minimum) about local factors coming from the fact that most primes are not divisible by $n$, for any fixed $n$ $\endgroup$ – Boris Bukh Oct 30 '15 at 19:04
  • 2
    $\begingroup$ If you replace the primes by the squares, then the density of winning positions is zero. Indeed, if $W$ is a set of winning positions, then $W-W$ contains no squares, which by Sarközy's theorem implies that $W$ has zero density. Sadly, this does not directly work on the primes since the difference set of $4\mathbb{N}$ contains no primes. $\endgroup$ – Boris Bukh Oct 30 '15 at 19:16
  • $\begingroup$ The obvious conjecture is that the density of winning positions $\rho(n)$ goes to $C/\sqrt{\ln n}$ and numerical work makes it seem that $C \approx 19$. But that is not even a hint at a proof of the general form of the counting function or density. $\endgroup$ – Mark Fischler Oct 30 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.