1
$\begingroup$

The Nim function for take-a-prime game $(u_n)$ is defined recursively as follows:

For all $n \in \mathbb{N}$, $u_n$ is the lowest number in $\mathbb{N}$ such that for all prime numbers $p$ (with $n−p \geq 0$), $u_n \neq u_{n-p}.$

As you can show, this sequence has interesting patterns.

First terms of Nim function for take-a-prime game

Question: Is this sequence bounded?

Context: I came across this question ten years ago with classmates. Some of them guessed the sequence should be bounded, others thought it should have a very slow rate of divergence (such as $\log \log n$).

Facts:

  • This is sequence A014589 of OEIS, with first reference in 1996 in the dissertation of Achim Flammenkamp.

  • The sequence seems to take values between 0 and 11. Value 11 appears at $n=156$. I've checked all terms before $32452843$.

  • Stacked plot of proportions to obtain values from 0 to 11 as the length of the sequence increases seems to converge, see following figure: 0 is on the bottom (in dark orange) and 11 is on the top (in pink).

Stacked plot of proportions to obtain values from 0 to 11

Relation with other math.stackexchange posts: Some posts discuss about related sequences, and from what I can understand, it is related with the proportion of $0$ in the current A014589, see: Is there a last winning position in "Prime Nim"? and Prime one heap Nim.

Stronger/weaker questions: In take-a-prime game, the subset $S$ of $\mathbb{N}$ is the set of prime numbers. Which properties must have $S$ to bound the related Nim function for take-a-$S$ game? Are there some probabilistic results? For example: If the number of elements in $S$ smaller than $n$ is $a_n$ asymptotically, then probability [to define properly] to have a bounded Nim function is $1$.

$\endgroup$

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.