Покрытие простых арифиметическими прогрессиями из простых

[dimkadimon]

Известно что первые 10 нечетных простых можно покрыть тремя арифметическими прогрессиями из простых:

$(3,17,31), (5,11,17,23,29), (7,13,19)$

Вопрос: сколько требуется арифметических прогрессий из простых чтобы покрыть первые 100 нечетных простых? А сколько для первых 1000?

[Yadryara]

У Вас два раза встречается $17$. Это ошибка?

Длина арифметических прогрессий ограничена снизу?

$(3,13), (5,11,17,23,29), (7,19,31)$

Например, вот этот вариант Вы считаете подходящим?

[dimkadimon]

Yadryara в сообщении #1405615 писал(а):

У Вас два раза встречается $17$. Это ошибка?

Нет это не ошибка. Цифры могут повторятся, главное чтобы все простые покрывались.

Yadryara в сообщении #1405615 писал(а):

Длина арифметических прогрессий ограничена снизу?

Нет. Прогрессии могут иметь две или одну цифру. Конечно интересный вариант поставить ограничение длинны снизу в 3 цифры, но тогда не уверен что всегда будут решения.

Yadryara в сообщении #1405615 писал(а):

$(3,13), (5,11,17,23,29), (7,19,31)$

Например, вот этот вариант Вы считаете подходящим?

Да этот вариант подходящий.

[dmd]

Если не ошибся, то у меня получилось, что для 100 простых всего прогрессий 4950 и самая большая из них состоит из шести простых с шагом 30. И тогда на вскидку количество покрывающих прогрессий может быть равно 45. Но как их точно посчитать? Полный обход дерева вариантов слишком огромен.

(gp-код)

app()=
{
 A= []; so= 0; 
 for(d=2, 544,
  for(i=2, 100,
   p= prime(i);
   P= concat([], [p]); \\print(d"    "p"    "P);
   while(p+d<=547,
    p= p+d; \\print1(p", ");
    if(isprime(p), P= concat(P, [p]), break())
   );
   if(#P>1, A= concat(A, [P]));
  )
 );
 print(#A);

 for(i=1, #A, if(#A[i]>so, so= #A[i]; print(so"    "A[i])))
};

4950
3 [3, 5, 7]
5 [5, 11, 17, 23, 29]
6 [7, 37, 67, 97, 127, 157]

Весь набор прогрессий 6:6, 5:21, 4:112, 3:453, 2:4358.

(код)

 n6=n5=n4=n3=n2=0;
 for(i=1, #A,
  if(#A[i]==6, n6++);
  if(#A[i]==5, n5++);
  if(#A[i]==4, n4++);
  if(#A[i]==3, n3++);
  if(#A[i]==2, n2++);
 );
 print(n6"    "n5"    "n4"    "n3"    "n2)

6 21 112 453 4358

[dmd]

Теоретический минимум: 6 шистизначных плюс 13 пятизначных прогрессий = 19 прогрессий.

[podih]

Можно начать покрывать множество с 11 и до конца. По идее, это и будет 6 набором. Типа, (11 , 17, 23), (13, 19) и т. д.

[dimkadimon]

Сначала можно найти наилучшие покрытие из прогрессий длинной 3 и больше (их не так много). К этому решению можно всегда добавить прогрессии длинной 2 в "слепую" - каждые два пропущенных числа можно покрыть одной такой прогрессией.

Кстати идею для задачи я взял от сюда:
https://math.stackexchange.com/question ... ect=1&lq=1

[Yadryara]

Ещё можно последовательность $3, 6, 10, 13, 18, ...$ в OEIS забабахать. То бишь четырьмя прогрессиями можно покрыть максимум $13$ чисел, а пятью — $18$ ? Пример для $18$-ти:

$ 5, 11, 17, 23, 29 $

$ 7, 19, 31, 43 $

$ 41, 47, 53, 59 $

$ 13, 37, 61 $

$ 3, 67 $

[dimkadimon]

Yadryara в сообщении #1406115 писал(а):

Ещё можно последовательность $3, 6, 10, 13, 18, ...$ в OEIS забабахать

Согласен. Я уже начал работать над этой последовательностью, но еще не опубликовал.

[dimkadimon]

Yadryara в сообщении #1406115 писал(а):

Пример для $18$-ти

Хорошая находка!

[dimkadimon]

А как у вас получилось покрыть 6 простых двумя прогрессиями?

[Yadryara]

dimkadimon, не помню. Возможно, ошибся где-то. Для $13$, $18$ и $22$ решения записаны.

[Dendr]

Явно чувствую, что не наилучший алгоритм использую, но он перебирает все возможные покрытия. На поиск наименьшего покрытия уходит слишком много времени, но близкие к наименьшему - довольно скоро находятся. Для тех же 18 почти сразу дошел до 6-компонентного, а на нахождение 5-компонетного потратил несколько часов.

Очевидно, что всегда есть набор N/2, а дальше начинаются перегруппировки. Но вряд ли слишком кардинальные.

Пока что для 100 простых рекорд - 46 прогрессий (сгруппированы по 5 в строку):
(3, 5, 7) (11, 13) (17, 19) (23, 29) (31, 37, 43)
(41, 43) (47, 53, 59) (61, 67, 73, 79) (71, 73) (83, 89)
(97, 101) (103, 107) (109, 113) (127, 131) (137, 139)
(149, 151) (157, 163) (167, 173, 179) (181, 191) (193, 197)
(199, 211, 233) (227, 229) (233, 239) (241, 251) (257, 263, 269)

(271, 277, 283) (281, 283) (293, 307) (311, 313) (317, 331)
(337, 347) (349, 353) (359, 367) (373, 379) (383, 389)
(397, 401) (409, 419) (421, 431) (433, 439) (443, 449)
(457, 461) (463, 467) (479, 491, 503) (487, 509) (499, 523, 547)
(521, 541)

[Yadryara]

dmd в сообщении #1405689 писал(а):

Весь набор прогрессий 6:6, 5:21, 4:112, 3:453, 2:4358.

Что это значит? $6$ прогрессий длины $6$, $21$ прогрессия длины $5$, $112$ прогрессий длины $4$ ?

Нет, это у вас суммарные количества: $6$ прогрессий длины $6$, $21$ прогрессия длиной не меньше $5$, $112$ прогрессий длиной не меньше $4$.

Или

$6$ прогрессий длины $6$, $15$ прогрессий длины $5$, $91$ прогрессия длины $4$.

[Yadryara]

В OEIS, кстати, немало последовательностей посвященных арифм. прогрессиям из простых чисел. Вот здесь, например, про гэпы для первых прогрессий соотв. длины: A093364. Нетрудно заметить, что эти гэпы, то бишь разности прогрессий, кратны праймориалам.