OFFSET
1,2
COMMENTS
Two players take turns naming a positive integer. When one player says the number n, the other player can either reply with n+1 or with n/p for some prime p if n/p is an integer. We call these two types of moves a successor move and a division move, respectively. The player who says the number 1 wins. This sequence consists of the winning numbers, i.e., the player that says one of these numbers can force a win.
Note that a round of this game could be infinite if both players always make successor moves, but with reasonable play (both players trying to win), each round is finite: Assume that one player just said the number n. We argue that the sequence will reach a number strictly smaller than n after at most n steps. It suffices that within the next n steps, a division move is made at least once to immediately reach a number smaller than n. By Bertrand's Postulate, there is a prime p with n <= p < 2n. So within the first n steps of the game, either one player makes a division move, in which case the result is strictly smaller than n, or the players keep making successor moves until p is reached. But if p is reached, the only reasonable play is to make a division move and say "1", since this wins the game.
LINKS
Kevin Ryde, Table of n, a(n) for n = 1..10000
Math Overflow, A little number theoretic game.
Kevin Ryde, PARI/GP Code
PROG
(PARI)
upto(n)={
my(a=vector(nextprime(max(5, n))), r=1); a[1]=1;
while(r<#a,
for(k=2, #a, if(!a[k], my(z=0);
foreach(factor(k)[, 1], p, if(a[k/p]>0, a[k]=-1); z+=!a[k/p]);
if(!a[k], a[k]=if(a[k+1]>0, -1, a[k+1]<0 && !z)); if(a[k], r++);
)));
[i | i<-[1..n], a[i]>0]
} \\ Andrew Howroyd, Apr 20 2023
(PARI) Also see links.
(Python)
from functools import lru_cache
from sympy import factorint, isprime
@lru_cache(maxsize=None)
def winning(q):
if q == 1: return True
if isprime(q): return False
pf = factorint(q)
if winning(q+1) or any(winning(q//p) for p in pf):
return False
if not winning(q+1) and all(not winning(q//p) for p in pf):
return True
print([k for k in range(1, 200) if winning(k)]) # Michael S. Branicky, Apr 20 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Leif Sabellek, Apr 19 2023
EXTENSIONS
Terms a(29) and beyond from Andrew Howroyd, Apr 20 2023
STATUS
approved