%I #31 Dec 19 2024 11:54:21
%S 1,4,6,10,14,16,22,25,27,34,36,38,40,46,49,51,56,58,60,63,65,69,74,77,
%T 82,84,86,88,91,94,96,100,104,106,111,115,117,119,121,123,129,132,134,
%U 136,140,142,144,146,150,152,156,158,160,162,166,169,171,178,183
%N Winning numbers of game where you can either add one or divide by a prime.
%C 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.
%C 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.
%H Kevin Ryde, <a href="/A362416/b362416.txt">Table of n, a(n) for n = 1..10000</a>
%H Math Overflow, <a href="https://mathoverflow.net/questions/445015/a-little-number-theoretic-game">A little number theoretic game</a>.
%H Kevin Ryde, <a href="/A362416/a362416.gp.txt">PARI/GP Code</a>
%o (PARI)
%o upto(n)={
%o my(a=vector(nextprime(max(5,n))), r=1); a[1]=1;
%o while(r<#a,
%o for(k=2, #a, if(!a[k], my(z=0);
%o foreach(factor(k)[,1], p, if(a[k/p]>0, a[k]=-1); z+=!a[k/p]);
%o if(!a[k], a[k]=if(a[k+1]>0, -1, a[k+1]<0 && !z)); if(a[k], r++);
%o )));
%o [i | i<-[1..n], a[i]>0]
%o } \\ _Andrew Howroyd_, Apr 20 2023
%o (PARI) \\ See Ryde link.
%o (Python)
%o from functools import lru_cache
%o from sympy import factorint, isprime
%o @lru_cache(maxsize=None)
%o def winning(q):
%o if q == 1: return True
%o if isprime(q): return False
%o pf = factorint(q)
%o if winning(q+1) or any(winning(q//p) for p in pf):
%o return False
%o if not winning(q+1) and all(not winning(q//p) for p in pf):
%o return True
%o print([k for k in range(1, 200) if winning(k)]) # _Michael S. Branicky_, Apr 20 2023
%Y Cf. A363369 (shortest game).
%K nonn
%O 1,2
%A _Leif Sabellek_, Apr 19 2023
%E Terms a(29) and beyond from _Andrew Howroyd_, Apr 20 2023