Un pequeño juego de teoría numérica

Question

Se me ocurrió este pequeño juego para dos jugadores:

Los jugadores se turnan para nombrar un número entero positivo. Cuando un jugador dice el número n, el otro jugador sólo puede responder de dos maneras diferentes: Puede responder con n+1 o puede dividir n por un número primo si la división sale bien (sin resto). Gana quien diga el número 1.

Ejemplo de juego:

A: 48 B: 24 A: 25 B: 26 A: 27 B: 9 A: 10 B: 2 A: 1

A gana.

Una ronda de este juego podría ser infinita, si ambos jugadores responden siempre con n+1, pero con un juego razonable (ambos jugadores intentando ganar), cada ronda es finita: Supongamos que uno de los jugadores acaba de decir el número n. Argumentamos que la secuencia alcanzará un número estrictamente menor que n tras un máximo de n pasos. Obsérvese que basta con que en el siguiente paso n un jugador elija dividir por un primo al menos una vez para alcanzar inmediatamente un número menor que n. Por el postulado de Bertrand, existe un número primo p con $n \leq p < 2n$ . Así, en los primeros n pasos del juego, o bien un jugador divide por un primo, en cuyo caso el resultado es estrictamente menor que n, o bien se alcanza p. Pero si se alcanza p, la única jugada razonable es responder "1", ya que así se gana el juego. Pero si se alcanza p, la única jugada razonable es responder "1", ya que así se gana la partida.

Por lo tanto, la secuencia siempre llegará a 1 en algún momento. Como se trata de un juego finito de información perfecta sin empates, siempre hay una estrategia ganadora para uno de los dos jugadores. Los siguientes números son números ganadores, es decir, el jugador que diga uno de estos números puede forzar una victoria.

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, ...

Esta secuencia no parece estar en OEIS, voy a sugerir una entrada para ella pronto.

Escribí un programa para generar números ganadores hasta 10000, y me di cuenta de que las diferencias entre los números ganadores son relativamente pequeñas y relativamente constantes. Aproximadamente un tercio de los números son ganadores y la diferencia entre dos números ganadores suele ser de 2, 3 ó 4.

Creo que el conjunto de números ganadores plantea algunas preguntas interesantes, así que sólo por diversión:

• ¿Existe un límite absoluto para el intervalo entre dos números ganadores consecutivos?
• ¿Converge la densidad de este conjunto? En caso afirmativo, ¿cuál es el valor?
• ¿Hay alguna forma fácil de ver si un número es ganador?
• ¿Cuál es la complejidad computacional de determinar si un número dado es ganador?
• ¿Existe una estrategia ganadora sencilla que un humano pueda recordar, o es sólo un caos?

Me interesaría conocer su opinión, y quizá usted también tenga algunas respuestas a otras preguntas interesantes que no he formulado.

EDITAR : Esta secuencia está ahora en OEIS: https://oeis.org/A362416

Answer 1

Editar : He añadido código para calcular los valores Nim para el primer $N$ posiciones de este juego después del post original, como pidió @Timothy-Chow. Desgraciadamente mis resultados no coinciden con los dados por @Peter-Taylor en los comentarios, así que tal vez no he calculado correctamente.

Viejo: Aquí está el código para los cálculos a los que aludí en los comentarios, seguido de los resultados al examinarlos $n$ hasta 10.000.000, de los cuales 3.261.995 son números ganadores. Como puede ver, la diferencia $g$ ocurre alrededor de $\frac{1}{2^{g-1}}$ del tiempo.

from sympy import primefactors
from collections import Counter
from functools import lru_cache

N = 10_000_000

@lru_cache(maxsize=N)
def iswinner(n):
    if n == 1:
        return True
    moves = [n // p for p in primefactors(n)] + [n+1]
    return all(not iswinner(move) for move in moves)

# yields the gaps in a sequence with more than 1 element
def gaps(seq):
    old = next(seq)
    for new in seq:
        yield new - old
        old = new

def winners():
    for n in range(1,N):
        if iswinner(n):
            yield n

freqs = Counter(gaps(winners()))

for gap in sorted(freqs.keys()):
    print(f'{gap:5}:{freqs[gap]:10}')

    2:   1570812
    3:    801091
    4:    446401
    5:    219317
    6:    111298
    7:     55754
    8:     29343
    9:     13833
   10:      7112
   11:      3482
   12:      1831
   13:       810
   14:       454
   15:       229
   16:       111
   17:        54
   18:        29
   19:        19
   20:         8
   21:         4
   22:         1
   23:         2

Edición 19 abril 2023 (Nimbers): Aunque hemos estado llamando a los números 1, 4, 6, 10, 14, ... ganador números, en realidad son perdiendo posiciones para el jugador que se enfrente a ellos. Así que los llamados números ganadores tienen valor Nim 0. (es decir. $\star 0$ para los versados en notación combinatoria de juegos) El valor Nim, también conocido como valor Grundy, es el número entero no negativo mínimo que no es igual al valor Nim de ninguna de sus posiciones alcanzables. Esta función de "mínimo excluido" se denominaba mex por John Horton Conway.

Los anteriormente denominados "números ganadores" tienen el valor 0. Estos se calcularon mediante programación dinámica, una técnica que normalmente sólo mira hacia atrás en la matriz, pero en este caso, ya que $n+1$ es un movimiento permitido desde $n$ tiene que mirar hacia delante. El problema del árbol de juegos infinito se evitó dándonos cuenta de que eventualmente llegaremos a un primo, y un primo es una posición ganadora (dividimos por p y dejamos a nuestro oponente con la posición perdedora 1 ). Sin embargo, al calcular las posiciones distintas de cero como valores Nim, no podemos suponer que un jugador se mueva de un primo $p$ a 1, porque puede ser ventajoso no pasar inmediatamente a *0 en una suma de partidas.

Este algoritmo busca la siguiente posición cero y rellena los valores hasta la posición cero anterior. Por ejemplo, supongamos que hemos calculado los nimbers hasta ahora, y que acabamos de descubrir que 10 es una posición de valor cero.

Ahora podemos calcular el valor Nim para 9, porque los únicos movimientos son a 3 y a 10, y sabemos que nimbers[3] es 1 y nimbers[10] es 0. Por lo tanto, por el principio de mínimo excluido, el valor Nim de 9 es 2. Después de eso podemos calcular los valores para 8 y 7.

La salida de este programa, que cuenta todos los valores Nim, es

0: 3,261,996
1: 3,203,496
2: 2,030,151
3: 1,224,407
4:   258,511
5:    21,142
6:       297

Lamentablemente, esto no coincide con los valores indicados en los comentarios, por lo que puede ser incorrecto. No dude en hacérmelo saber.

from sympy import primefactors
from collections import Counter
from functools import lru_cache
from itertools import count

N = 10_000_000

@lru_cache(maxsize=N)
def iswinner(n):
    if n == 1:
        return True
    moves = [n // p for p in primefactors(n)] + [n+1]
    return all(not iswinner(move) for move in moves)

# return first non-negative integer not in l
def mex(l):
    for x in count():
        if x not in l:
            return x

extra = 30
nimbers = [None]*(N+extra)
nimbers[1] = 0
last = 1
n = 2

while last < N:
    if iswinner(n):
        nimbers[n] = 0
        k = n - 1
        while nimbers[k] is None:
            moves = [k // p for p in primefactors(k)] + [k+1]
            nimbers[k] = mex([nimbers[move] for move in moves])
            k -= 1
        last = n
    n += 1

freqs = Counter(nimbers[1:N+1])

for key in sorted(freqs.keys()):
    print(f'{key:5}:{freqs[key]:10,}')