A362416 - OEIS

%I #29 Jun 03 2023 07:26:37

%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) Also see links.

%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