\\ Kevin Ryde, May 2023

\\ This is some PARI/GP code to calculate terms of A362416
\\ up to up to a given maximum value.  A362416 is the winning
\\ start positions for a game x -> x+1 or x/prime.
\\
\\ The code deterines the winning/losing state of each starting
\\ x in downward runs hi-1 .. lo+1 where lo,hi are consecutive
\\ primes (knowing primes are always losing positions).
\\
\\ Requires PARI 2.13 or higher for foreach().

default(recover,0);
default(strictargs,1);


\\ Return a vector of the terms of A362416 which are <= limit.
A362416_upto(limit) =
{
  my(win = Vecsmall([1],nextprime(limit)),
     lo=3,hi=5);
  while(lo < limit,
        forstep(x=hi-1, lo+1, -1,
           foreach(factor(x)[,1], p,  \\ p prime factor of x
              if(win[x/p],next(2)));
           win[x]=1;
           x--);   \\ skip x-1 which is certainly losing
        lo=hi;
        hi=nextprime(hi+1));
  
  select(x->win[x], [1..limit]);
}

{
  my(terms=A362416_upto(40));
  print1("A362416 = ");
  for(n=1,#terms, print1(terms[n],", "));
  print("...");
}


\\ Game Notes
\\ ----------
\\
\\ The game starts by player 1 saying a number x.
\\ Player 2 says x+1 or some x/p where p is a prime dividing x.
\\ Player 1 says further +1 or /p from there, and so on.
\\ The winner is the player who says "1".
\\
\\ A winning x is one which allows player 1 to force a win by
\\ suitable choices of +1 or /p, no matter what player 2 does.
\\ These are the terms of A362416.
\\
\\ A losing x is, conversely, one where player 1 cannot force a win.
\\ Player 2 has one or more winning positions among x+1, x/p,
\\ and wins by choosing one of them.
\\
\\ In terms of moves,
\\
\\     x is winning = every x+1 and x/p is a losing position
\\                    (ie. any choice by player 2 is losing)
\\
\\     x is losing = some x+1 or x/p is a winning position
\\                   (ie. a winning choice for player 2)


\\ Implementation Notes
\\ --------------------
\\
\\ win[x]==1 means x is a winning start position.
\\ Initial win = [1,0,0,...] is x=1 winning.
\\
\\ All primes x are losing positions, since player 2 can say x/x = 1.
\\ Other x are considered in downward runs between successive primes,
\\
\\     prime                    prime
\\     "lo"   lo+1  ...   hi-1   "hi"
\\             | <--- x --- |
\\
\\ If win[x+1]==1 or any win[x/p]==1, then x is losing so leave
\\ win[x]=0 which is its default.
\\
\\ If win[x+1]==0 and all win[x/p]==0, then x is winning so set
\\ win[x]=1.
\\
\\ The code doesn't test win[x+1]==0 as such because if set
\\ win[x]=1 then skip its x-1 (by x--) since that's definitely
\\ losing and should leave win[x-1]=0 (its default).
\\
\\ x/p is at most x/2 and this is < lo by Bertrand's postulate
\\ that any interval n to 2*n has at least one prime, which in
\\ this case means prime "lo" between x and x/2.
\\
\\ win[] and the x range extends to nextprime(limit) so as
\\ to ensure the last downwards hi .. lo covers the "limit".
\\ The extra is small compared to the requested limit since
\\ prime gaps are small within the feasible sizes for this
\\ algorithm.


\\ Other Ways - forfactored()
\\ --------------------------
\\
\\ Each x could be considered consecutively with forfactored()
\\ by first basing winning just on x/p and on finding a losing
\\ position revise back the preceding run of winning positions
\\ (if any).  For example,
\\
\\      ...   x-4  x-3  x-2  x-1   x
\\     c   d   1    1    1    1    0    win[]
\\             ^         ^
\\             0         0              change
\\
\\ At x-1, its "+1" move is to losing x, which is good,
\\ so x-1 remains winning.
\\
\\ But x-2 now has a +1 move to a winning position available to
\\ player 2, so x-2 changes to a losing position.
\\
\\ Similarly x-3 unchanged but x-4 change to losing.
\\ Every second 1 changes to 0 this way.
\\
\\ This approach measures slower, presumably mostly due to
\\ interpreter overheads.  In A362416_upto(), individual
\\ factor() is quite fast on small x, and for medium size
\\ limits factor() is only applied to about 60% to 65% of
\\ 1..limit (composite x for which x+1 is losing).


\\ Other Ways - List()
\\ -------------------
\\
\\ Winning x could be held in a List() ready to become the
\\ returned vector, rather than select() in A362416_upto().
\\ setsearch() in that list is then the win[] test but (maybe
\\ not surprisingly) this measures slower than win[] array.
\\
\\ With forfactored(), list terms near the end would be deleted
\\ when revising winning positions preceding a losing position.
\\ With downwards runs, a listinsert() can maintain ascending
\\ order by inserting new wins at what was the end of the list
\\ before the present hi-1..lo+1 block.


print("end");