Prime Numbers and a Two-Player Game

848 Views Asked by At

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers.

Alex and Beth are playing the following game. Initially, there are $n\in\mathbb{N}_0$ marbles on a table. Alex and Beth alternatively pick out some marbles out of the table, with Alex going first. The number of removed marbles per turn must be a prime number (i.e., $2$, $3$, $5$, $7$, $11$, etc.). The first person who cannot make a move loses the game. If $W$ is the set of all nonnegative integers such that Alex can always win if $n\in W$, whereas $L$ is the set of all nonnegative integers such that Beth has a winning strategy if $n\in L$.

Is it true that $L$ is an infinite subset of $\mathbb{N}_0$ (clearly, $W$ is infinite, since it contains all the primes)? We now know that both $W$ and $L$ are infinite subsets of $\mathbb{N}_0$. What are natural densities of $W$ and $L$? What are logarithmic densities of $W$ and $L$? Does $L$ contain an infinite number of pairs of consecutive integers? Does $L$ contain only finitely many even integers? For a positive integer $k$, does each of $W$ and $L$ always have infinitely many subsets of consecutive integers of size $k$? Does $L$ contain an infinitely number of semiprimes? Is the sum $\sum_{n\in L\setminus\{0\}}\,\frac{1}{n}$ finite (clearly, $\sum_{n\in W}\,\frac{1}{n}$ is infinite)?

For a start, $W=\{2,3,4,5,6,7,8,11,12,13,14,15,\ldots\}$ and $L=\{0,1,9,10,25,34,35,\ldots\}$. I conjecture that $L$ is an infinite subset of $\mathbb{N}_0$ containing infinitely many semiprimes such that $\sum_{n\in L\setminus\{0\}}\,\frac{1}{n}$ is finite. Furthermore, I expect that the natural density and the logarithmic density of $W$ are both $1$, whereas the natural density and the logarithmic density of $L$ are both $0$. References are very welcome.

According to the OEIS link given by Michael Lugo in a comment below, it seems that $\{0,1\}$, $\{9,10\}$, $\{34,35\}$, and $\{309,310\}$ are the only subsets of $L$ consisting of consecutive integers (I could be wrong to assume that these are the only ones), and $W$ has at least three subsets of size $29$ which are composed by consecutive integers. Also, this set of data suggests that the natural density and the logarithmic density of $L$ exist and are equal, with the value somewhere between $0.1$ and $0.2$. In addition, $\sum_{n\in L\setminus\{0\}}\,\frac{1}{n}>2.2$, and of course, if the logarithmic density of $L$ exists and is positive, then this sum is infinite.

An interesting remark by Michael ($\neq$ Michael Lugo) is that the set $L$ contains very few even numbers. Among the smallest $10000$ elements of $L$, only $5$ of them are even. This leads to my speculation that $L$ has only finitely many even numbers. Michael also verifies that $L$ has a positive natural density of at least $0.1$ and at most $0.25$, if $L$ has only $5$ even elements.

If, instead, the number of removed marbles per turn must belong in nonempty set $S \subseteq \mathbb{N}$ such that $\mathbb{N}\setminus S$ is infinite, let $W_S$ and $L_S$ be the sets $W$ and $L$, respectively, for this particular $S$. What can be said about the finiteness of $W_S$ and of $L_S$? How about the finiteness of the reciprocal sums $\sum_{n\in W_S}\,\frac{1}{n}$ and $\sum_{n\in L_S\setminus\{0\}}\,\frac{1}{n}$? What do we know about the natural and the logarithmic densities of $W_S$ and $L_S$?

For example, if $S=\{1,2,\ldots,m\}$ for some $m\in\mathbb{N}$, then we have $W_S=\big\{n\in\mathbb{N}_0\,\big|\,(m+1)\nmid n\big\}$ and $L_S=\big\{n\in\mathbb{N}_0\,\big|\,(m+1)\mid n\big\}$. Hence, $W_S$ and $L_S$ are infinite sets with $\sum_{n\in W_S}\,\frac{1}{n}$ and $\sum_{n \in L_S\setminus\{0\}}\frac{1}{n}$ being also infinite. Note that the natural and logarithmic densities of $W_S$ are both $1-\frac{1}{m+1}$, and the natural and logarithmic densities of $L_S$ are both $\frac{1}{m+1}$.

Reference:

https://oeis.org/A025043

2

There are 2 best solutions below

1
On

Assume $L$ is finite, say $\max L=m$. Then For any $n>m$ there exists $p$ with $n-p\in L$. As this implies that all prime gaps are $<m$, it is absurd. Hence $L$ is infinite.

5
On

Suppose there are about $f(N)$ losing points in $[1,N]$. There would be around $f(N+1)\approx f(N)+1f'(N)$ losing points in $[1,N+1]$, so $f'(N)$ is the chance that $N+1$ is a losing point.
On the other hand the odds that $N+1$ is a losing point is the chance that all $N+1-a$ are composite.
Pretend that the $N+1-a$ are all $O(N)$, then this chance would be $$\left(1-\frac1{\ln N}\right)^{f(N)}=f'(N)$$
Let $f(N)=(\ln N)^2g(N)$.
$(1-1/\ln N)^{\ln N}$ is roughly $1/e$, so the equation is approximately $$N^{-g(N)}=\frac{2\ln Ng(N)}N+\ln(N)^2g'(N)$$ If $g(N)\approx 1$, then the left-hand side is too small; if $g(N)\approx1-\epsilon$ then the left-hand side is too big. So I believe $f(N)\approx(\ln N)^2$
EDIT : It turns out this is wrong because the numbers are mostly odd. That makes it much easier for a new odd number to make the list. If say a fifth of the odd numbers are in the list, then the chance of a new even $N$ to make the list would be $(1-1/\ln N)^{N/10}$. This goes to zero much faster than $1/N^2$, so has a finite sum, and I expect a finite number of even $N$ to make the list.