Одноцветные арифметические прогрессии

15

Теорема Ван дер Вардена гласит, что

Для любых заданных натуральных чисел rи kсуществует некоторое число, Nтакое, что если целые числа {1, 2, ..., N}раскрашены, каждый из которых имеет свой r цвет, то kв арифметической прогрессии есть по крайней мере целые числа одного и того же цвета. Наименее таковым Nявляется число Ван дер Вардена W(r, k).

Ваша цель состоит в том, чтобы вычислить число Ван-дер-Вардена с W(r, k)учетом целочисленных входных данных rи k. Побеждает несколько байтов.

Помните, что эта функция растет очень быстро и требует много времени для вычислений. Даже W(4, 4)неизвестно. Вы можете предположить, что ваш код работает на идеальном компьютере с неограниченными ресурсами (время, память, глубина стека и т. Д.). Ваш код должен теоретически дать правильный ответ даже для значений, для которых ответ неизвестен.

Встроенные модули, которые вычисляют эту функцию, не допускаются.

пример

Для r = 2цветов и прогрессии длины k = 3существует 8последовательность длины , которая избегает такой прогрессии, то есть 3элементы с одинаковым расстоянием одного цвета:

B R R B B R R B

Но такой длины- 9последовательности нет W(2, 3) == 9. Например,

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

содержит 3показанную арифметическую прогрессию длины -цвета.

Контрольные примеры

Вы, вероятно, сможете проверять только небольшие случаи.

+-----+-----+-----+-----+-----+-----+------+
|     | 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 |     |     |      |
+-----+-----+-----+-----+-----+-----+------+

Показать фрагмент кода

code-golf math sequence combinatorics subsequence XNOR
источник

Ответы:

7

Python 3,5, 125, 124, 119 байтов

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))

Это забавно, потому что в процессе игры в гольф эта программа стала более эффективной. Все, что находится за пределами f(2,4)или f(3,3)все еще занимает вечность, хотя.

объяснение

Первоначальная версия проверила, содержит ли последовательность прогрессию длины k, попробовав все возможные начальные индексы и шаги.

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))

Версия для игры в гольф требует всего лишь попробовать все возможные шаги, так как она добавляет новые элементы последовательности. x*kКрышка заботиться о случаях , как [0, 0, 1], которая содержит прогрессию длины 2 , но не удовлетворяла бы уникальность проверки раскрытой.

Что касается проверки

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

На первом проходе версии для гольфа, когда Lон пуст, len(L)равно 0. Таким образом, вторая половина orвсегда будет выполняться. После этого Lон не пустой, поэтому {*L[:x*k:x]}(для Python это всего лишь 3.5 set(L[:x*k:x])) будет по крайней мере один элемент.

Поскольку L[:x*k:x]может иметь не более kэлементов, а для Lнепустых k*(*{*L[:x*k:x]},)- не менее kэлементов, эти два могут быть равны только тогда, когда kв обоих есть ровно элементы. Чтобы это произошло, {*L[:x*k:x]}должен быть ровно один элемент, т.е. у нас только один цвет в нашей прогрессии.

Sp3000
источник