A362416 Winning numbers of game where you can either add one or divide by a prime.

1, 4, 6, 10, 14, 16, 22, 25, 27, 34, 36, 38, 40, 46, 49, 51, 56, 58, 60, 63, 65, 69, 74, 77, 82, 84, 86, 88, 91, 94, 96, 100, 104, 106, 111, 115, 117, 119, 121, 123, 129, 132, 134, 136, 140, 142, 144, 146, 150, 152, 156, 158, 160, 162, 166, 169, 171, 178, 183

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

Cf. A363369 (shortest game).

Sequence in context: A063745 A123666 A095305 * A058917 A310584 A165779

Adjacent sequences: A362413 A362414 A362415 * A362417 A362418 A362419

Keyword

nonn

Author

Leif Sabellek, Apr 19 2023

Extensions

Terms a(29) and beyond from Andrew Howroyd, Apr 20 2023

Status

approved