Progresiones aritméticas del mismo color.

15

El teorema de Van der Waerden dice que

Para cualquier enteros positivos dados ry k, hay un cierto número Ntal que si los números enteros {1, 2, ..., N}son de color, cada uno con uno de r diferentes colores, entonces hay al menos kenteros en progresión aritmética todos del mismo color. El menor Nes el número de Van der Waerden W(r, k).

Su objetivo es calcular el número de Van der Waerden W(r, k)con entradas enteras positivas ry k. Pocos bytes ganan.

Tenga en cuenta que esta función crece extremadamente rápido y requiere mucho tiempo para computar. Even W(4, 4)es desconocido. Puede suponer que su código se ejecuta en una computadora ideal con recursos ilimitados (tiempo, memoria, profundidad de pila, etc.). Teóricamente, su código debe dar la respuesta correcta incluso para valores para los que no se conoce la respuesta.

Los elementos integrados que calculan esta función no están permitidos.

Ejemplo

Para r = 2colores y progresiones de longitud k = 3, existe una 8secuencia de longitud que evita dicha progresión, es decir, 3elementos del mismo color con espacios iguales:

B R R B B R R B

Pero, no hay tal 9secuencia de longitud , entonces W(2, 3) == 9. Por ejemplo,

R B B R B R R B R
  ^     ^     ^

contiene la 3progresión aritmética del mismo color de longitud que se muestra.

Casos de prueba

Probablemente solo podrá probar casos pequeños.

+-----+-----+-----+-----+-----+-----+------+
|     | k=1 | k=2 | k=3 | k=4 | k=5 | k=6  |
+-----+-----+-----+-----+-----+-----+------+
| r=1 |   1 |   2 |   3 |   4 |   5 |    6 |
| r=2 |   1 |   3 |   9 |  35 | 178 | 1132 |
| r=3 |   1 |   4 |  27 | 293 |     |      |
| r=4 |   1 |   5 |  76 |     |     |      |
+-----+-----+-----+-----+-----+-----+------+

Mostrar fragmento de código

code-golf math sequence combinatorics subsequence xnor
fuente

Respuestas:

7

Python 3.5, 125 124 119 bytes

f=lambda r,k,*L:any(L[:x*k:x]==k*(*{*L[:x*k:x]},)for x in range(1,len(L)+1))*len(L)or max(f(r,k,i,*L)for i in range(r))

Es divertido porque, en el transcurso del golf, el programa se volvió más eficiente. Sin embargo, cualquier cosa más allá f(2,4)o f(3,3)aún lleva una eternidad.

Explicación

La versión inicial verificó si una secuencia contenía una progresión de longitud kprobando todos los índices y pasos de inicio posibles.

def f(r,k,L=[]):
 for i in range(len(L)):
  for j in range(len(L)):
   if len(set(L[i::j+1]))==1 and len(L[i::j+1])==k:
    return len(L)
 return max(f(r,k,L+[i])for i in range(r))

La versión de golf solo necesita probar todos los pasos posibles, ya que antepone nuevos elementos de secuencia. El x*klímite es para atender casos como [0, 0, 1], que contiene una progresión de longitud 2 pero no satisfaría la comprobación de unicidad sin límite.

En cuanto al cheque

L[:x*k:x]==k*(*{*L[:x*k:x]},)

En la primera pasada de la versión de golf, cuando Lestá vacía, len(L)es 0. Por lo tanto, la segunda mitad de la orsiempre se ejecutará. Después de eso Lno está vacío, por lo {*L[:x*k:x]}que (que es solo Python 3.5 set(L[:x*k:x])) tendrá al menos un elemento.

Como L[:x*k:x]puede tener como máximo kelementos y para los Lno vacíos k*(*{*L[:x*k:x]},)tiene al menos kelementos, los dos solo pueden ser iguales cuando hay exactamente kelementos en ambos. Para que esto suceda {*L[:x*k:x]}debe tener exactamente un elemento, es decir, solo tenemos un color en nuestra progresión.

Sp3000
fuente