The Game of Subtracting Primes

Computer Science Level 3

Ivan and Jake are playing a game with the following rules:

The game starts with a parameter N which is a positive integer.
Ivan always plays first.
In each turn, the player can either choose to add or subtract the largest prime smaller than N, to N.
The loser is the person who cannot continue. The other person wins by default.

Example

N=10
Ivan: N -> N + 7 = 17
Jake: N -> N - 13 = 4
Ivan: N -> 4 - 3 = 1

Ivan wins because Jake cannot continue the game.

Now, suppose that Ivan and Jake know how to play optimally. For how many starting values of $N < 10^4$ does Jake win?

The answer is 3984.

3 solutions

Agnishom Chattopadhyay
May 9, 2015

If N = 1,2: you are at a loosing position.
If N = p + 1, p+2: you are at a winning position.
If both N - previousPrime and N + previousPrime are winning positions: you are at a loosing position.

Mathematica Code:

Wins[n_] := 
 If[And[n != 1, n != 2, Or[PrimeQ[n - 1], PrimeQ[n - 2]]], True, 
  If[And[Wins[n - NextPrime[n, -1]], Wins[n + NextPrime[n, -1]]], 
   False, True]]

Note that there is no guarantee (so far), that this computing procedure halts for all N but it will be enough for 10^4

I keep increasing the bound and hope it halts but after setting the bound as high as $10^8$ I still got $43$ numbers that is unable to compute. One of the number is $9983$ , can you show when does it terminates?

Christopher Boo - 5 years ago

Arguments get over 2 * 10^12. See my answer.

Borut Levart - 2 years, 8 months ago

Elmokhtar Mohamed Moussa
Aug 12, 2015

I got to say that I've really enjoyed solving this problem ! the key factor is to implement a powerful algorithm for the primality test. Here is my c++ code :

#include <iostream>
#include "miller-rabin.cpp"

using namespace std;
int prevPrm(int n){
    for(int i = n - 1; i > 0 ; i--){
        if(Miller(i)){
            return i;
        }
    }
    return -1;
}
int simulate(int n, int py){
    int p = prevPrm(n);
    if(p == -1){
        return -(3 - py);
    }
    if(prevPrm(n - p) == -1){
        return -py;
    }
    if(simulate(n - p, 3 - py) == -py){
        return -py;
    }
    else{
        return simulate(n + p, 3 - py);
    }
}
int main(){
    int cpt = 0, n = 1; 
    while(n < 10000){
        if(simulate(n, 1) == -2){
            cpt++;
        }
        n++;
    }
    cout << "total = " << cpt << endl;
    return 0;
}

Execution time : 0.4s !And again thanks for problem !

Where is your Miller-Rabin implementation?

Christopher Boo - 5 years ago

I took from internet, this one should do it : http://www.sanfoundry.com/cpp-program-implement-miller-rabin-primality-test/

Elmokhtar Mohamed Moussa - 4 years, 10 months ago

Borut Levart
Sep 24, 2018

My code is similar to @Agnishom Chattopadhyay except that while figuring out the answer it also caches the determined positions (solid speed-up) and sows new argument values. With bound 10^4 for example one can observe that the biggest argument to NextPrime is 2 092 126 336 061. Initially I determined the adding/subtracting prime in a different manner, via PrimePi, which takes more time.

ans[m_]:=
  Reap[Module[{x},
    x[1]=False;
    x[2]=False;
    x[n_]:=x[n]=
      Module[{p,y},
        (* p=Prime[#-Boole[PrimeQ[n]]]&[PrimePi[Sow[n]]]; *)
        p=NextPrime[Sow[n],-1];
        y=x[n-p];
        If[y,!And[y,x[n+p]],True]];
    Array[x,m-1]//Tally]]

{tally, {arg}} = ans[10000]; // RepeatedTiming
(* {0.491, Null} *)

{tally, Max@arg}
(* {{{False, 3984}, {True, 6015}}, 2092126336061} *)

The Game of Subtracting Primes

The answer is 3984.

3 solutions

0 pending reports