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

[dmd]

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

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

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

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

Да, именно это.

Всего программка насчитала 4950 прогрессий, которые распределены по соответствующим наборам как 6+21+112+453+4358=4950.

[Yadryara]

dmd, моя программа насчитала другой результат. См. выше. Если вы так уверены, то прошу предъявить хотя бы $21$ прогрессию длины $5$. Их в данном диапазоне $15$, а не $21$.

Есть подозрение что ваша программа раньше времени останавливается на $5$, то есть считает длину прогрессий равной $5$. А затем добавляет ещё одно простое и считает что у новой длина $6$. Но не вижу смысла в такой принудительной укоротке.

Хорошо, я сам предъявлю. Слева направо: номер, длина, старт, гэп.

$ 1. \quad 6 \quad 7 \quad 30 $

$ 2. \quad 6 \quad 107 \quad 30 $

$ 3. \quad 6 \quad 359 \quad 30 $

$ 4. \quad 6 \quad 11 \quad 60 $

$ 5. \quad 6 \quad 53 \quad 60 $

$ 6. \quad 6 \quad 13 \quad 90 $


$ 1. \quad 5 \quad 5 \quad 6 $

$ 2. \quad 5 \quad 5 \quad 42 $

$ 3. \quad 5 \quad 5 \quad 48 $

$ 4. \quad 5 \quad 5 \quad 12 $

$ 5. \quad 5 \quad 5 \quad 96 $

$ 6. \quad 5 \quad 5 \quad 126 $

$ 7. \quad 5 \quad 151 \quad 30 $

$ 8. \quad 5 \quad 61 \quad 90 $

$ 9. \quad 5 \quad 83 \quad 90$

$ 10. \quad 5 \quad 89 \quad 90$

$ 11. \quad 5 \quad 29 \quad 120$

$ 12. \quad 5 \quad 277 \quad 30 $

$ 13. \quad 5 \quad 401 \quad 30 $

$ 14. \quad 5 \quad 11 \quad 30 $

$ 15. \quad 5 \quad 43 \quad 60 $

[dmd]

Не знай, может и ошибся где-то.

(6-, 5- и 4-наборы прогрессий)

[7, 37, 67, 97, 127, 157]
[107, 137, 167, 197, 227, 257]
[359, 389, 419, 449, 479, 509]
[11, 71, 131, 191, 251, 311]
[53, 113, 173, 233, 293, 353]
[13, 103, 193, 283, 373, 463]

[5, 11, 17, 23, 29]
[5, 17, 29, 41, 53]
[11, 41, 71, 101, 131]
[37, 67, 97, 127, 157]
[137, 167, 197, 227, 257]
[151, 181, 211, 241, 271]
[277, 307, 337, 367, 397]
[389, 419, 449, 479, 509]
[401, 431, 461, 491, 521]
[5, 47, 89, 131, 173]
[5, 53, 101, 149, 197]
[43, 103, 163, 223, 283]
[71, 131, 191, 251, 311]
[113, 173, 233, 293, 353]
[61, 151, 241, 331, 421]
[83, 173, 263, 353, 443]
[89, 179, 269, 359, 449]
[103, 193, 283, 373, 463]
[5, 101, 197, 293, 389]
[29, 149, 269, 389, 509]
[5, 131, 257, 383, 509]

[11, 17, 23, 29]
[41, 47, 53, 59]
[61, 67, 73, 79]
[251, 257, 263, 269]
[7, 19, 31, 43]
[17, 29, 41, 53]
[47, 59, 71, 83]
[127, 139, 151, 163]
[227, 239, 251, 263]
[257, 269, 281, 293]
[397, 409, 421, 433]
[467, 479, 491, 503]
[5, 23, 41, 59]
[43, 61, 79, 97]
[53, 71, 89, 107]
[113, 131, 149, 167]
[313, 331, 349, 367]
[59, 83, 107, 131]
[79, 103, 127, 151]
[349, 373, 397, 421]
[419, 443, 467, 491]
[13, 43, 73, 103]
[23, 53, 83, 113]
[41, 71, 101, 131]
[67, 97, 127, 157]
[167, 197, 227, 257]
[181, 211, 241, 271]
[307, 337, 367, 397]
[349, 379, 409, 439]
[419, 449, 479, 509]
[431, 461, 491, 521]
[31, 67, 103, 139]
[241, 277, 313, 349]
[281, 317, 353, 389]
[311, 347, 383, 419]
[47, 89, 131, 173]
[67, 109, 151, 193]
[97, 139, 181, 223]
[107, 149, 191, 233]
[157, 199, 241, 283]
[227, 269, 311, 353]
[317, 359, 401, 443]
[337, 379, 421, 463]
[13, 61, 109, 157]
[53, 101, 149, 197]
[83, 131, 179, 227]
[5, 59, 113, 167]
[19, 73, 127, 181]
[29, 83, 137, 191]
[239, 293, 347, 401]
[379, 433, 487, 541]
[19, 79, 139, 199]
[47, 107, 167, 227]
[103, 163, 223, 283]
[131, 191, 251, 311]
[137, 197, 257, 317]
[151, 211, 271, 331]
[173, 233, 293, 353]
[277, 337, 397, 457]
[31, 97, 163, 229]
[41, 107, 173, 239]
[241, 307, 373, 439]
[251, 317, 383, 449]
[7, 79, 151, 223]
[67, 139, 211, 283]
[167, 239, 311, 383]
[23, 101, 179, 257]
[73, 151, 229, 307]
[113, 191, 269, 347]
[233, 311, 389, 467]
[5, 89, 173, 257]
[29, 113, 197, 281]
[149, 233, 317, 401]
[179, 263, 347, 431]
[11, 101, 191, 281]
[47, 137, 227, 317]
[151, 241, 331, 421]
[173, 263, 353, 443]
[179, 269, 359, 449]
[193, 283, 373, 463]
[277, 367, 457, 547]
[71, 167, 263, 359]
[101, 197, 293, 389]
[7, 109, 211, 313]
[47, 149, 251, 353]
[127, 229, 331, 433]
[23, 131, 239, 347]
[163, 271, 379, 487]
[223, 331, 439, 547]
[79, 193, 307, 421]
[37, 157, 277, 397]
[71, 191, 311, 431]
[73, 193, 313, 433]
[107, 227, 347, 467]
[149, 269, 389, 509]
[11, 137, 263, 389]
[31, 157, 283, 409]
[41, 167, 293, 419]
[101, 227, 353, 479]
[131, 257, 383, 509]
[5, 137, 269, 401]
[47, 179, 311, 443]
[67, 199, 331, 463]
[73, 211, 349, 487]
[29, 173, 317, 461]
[7, 157, 307, 457]
[13, 163, 313, 463]
[17, 167, 317, 467]
[73, 223, 373, 523]
[41, 197, 353, 509]
[43, 211, 379, 547]
[19, 193, 367, 541]

(gp-code)

 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"\n");

 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"\n");

 forstep(l=6,4,-1,
  for(i=1, #A,
   if(#A[i]==l, print(A[i]))
  ); print()
 );

[Yadryara]

dmd, ну да, так и есть. $6$ насильно укороченных $6$-к у вас считаются и как $5$-ки.

Например пятёрка $[37, 67, 97, 127, 157]$ это шестёрка $[7, 37, 67, 97, 127, 157] $ от которой почему-то отрезано первое простое, то бишь $7$.

[dmd]

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

[Dendr]

И правда, так гораздо быстрее. Хотя нет 100% уверенности, что так получается действительно оптимальное покрытие...

Алгоритм, на самом деле, может работать с любой упорядоченной последовательностью целых чисел (а значит, и рациональных), но с простыми более детерминировано - да и просто любопытно. Пусть к ней "прикреплен" список прогрессий, изначально пустой. Обозначу для последовательность буквой X, а список - Y.

На каждом шаге добавлять в Y прогрессию, которая удовлетворяет следующим критериям (формализую максимально возможно):
а) содержит только члены X,
б) среди прогрессий, удовлетворяющих критерию "а", содержит наибольшее количество членов, которые НЕ содержатся в прогрессиях из списка Y, и начинается с такого же члена,
в) среди прогрессий, удовлетворяющих критериям "а" и "б", имеет наименьший начальный член,
г) среди прогрессий, удовлетворяющих критериям "а", "б", "в", имеет наименьшую разность.

Этот алгоритм (код реализации на плюсах: http://cpp.sh/6r7xh - важное замечание: для больших чисел он-лайн компилятор выбрасывает из рекурсии) для N=100 дал ответ в 27 прогрессий (сгенерированный программой список откорректирован вручную, чтобы минимизировать повторы, поэтому, в частности, в самом начале встречается 6-членная прогрессия - исходно она начиналась с 11):

( 7, 37, 67, 97, 127, 157 )
( 71, 131, 191, 251, 311 )
( 13, 103, 193#, 283, 373, 463 )
( 53, 113, 173, 233, 293, 353 )
( 107, 137, 167, 197, 227, 257 )

( 359, 389, 419, 449, 479, 509 )
( 61, 151, 241, 331, 421 )
( 277, 307, 337, 367, 397 )
( 401, 431, 461, 491, 521 )
( 5, 11, 17, 23, 29 )

( 19, 79, 139, 199 ) ; ( 43, 211, 379#, 547 ) ; ( 3, 31, 59 ) ; ( 41, 179, 317 ) ; ( 73, 193#, 313, 433 )

( 83 263, 443 ) ; ( 109, 229, 349 ) ; ( 163, 271, 379#, 487 ) ; ( 457, 499, 541 ) ; ( 47, 89 )

( 101, 149 ) ; ( 181, 223 ) ; ( 239, 269 ) ; ( 281, 347 ) ; ( 383, 409 )

( 439, 467 ) ; ( 503, 523 )

Как видно, первоначальная оценка в 45 оказалась слишком грубой! Пересекаются же только 2 числа: 193 и 379 - в списке они помечены #.


Для N=1000 получается 230 прогрессий, повторов набирается при этом 29.

Вот первые 13 прогрессий, все состоят более чем из 6 членов:
( 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 )
( 3499, 3709, 3919, 4129, 4339, 4549, 4759, 4969, 5179 )
( 881, 1091, 1301, 1511, 1721, 1931, 2141, 2351 )
( 1637, 2267, 2897, 3527, 4157, 4787, 5417, 6047 )
( 7, 157, 307, 457, 607, 757, 907 )
( 47, 257, 467, 677, 887, 1097, 1307 )
( 53, 1103, 2153, 3203, 4253, 5303, 6353 )
( 179, 389, 599, 809, 1019, 1229, 1439 )
( 193, 613, 1033, 1453, 1873, 2293, 2713 )
( 359, 1619, 2879, 4139, 5399, 6659, 7919 )
( 1061, 1901, 2741, 3581, 4421, 5261, 6101 )
( 1753, 2593, 3433, 4273, 5113, 5953, 6793 )
( 4259, 4679, 5099, 5519, 5939, 6359, 6779 )

[dmd]

Если без оптимизации и без повторов, то 28 прогрессий:
[7, 37, 67, 97, 127, 157]
[107, 137, 167, 197, 227, 257]
[359, 389, 419, 449, 479, 509]
[11, 71, 131, 191, 251, 311]
[53, 113, 173, 233, 293, 353]
[13, 103, 193, 283, 373, 463]
[151, 181, 211, 241, 271]
[277, 307, 337, 367, 397]
[401, 431, 461, 491, 521]
[5, 23, 41, 59]
[349, 379, 409, 439]
[19, 79, 139, 199]
[3, 17, 31]
[499, 523, 547]
[433, 487, 541]
[29, 89, 149]
[383, 443, 503]
[43, 47]
[313, 317]
[223, 229]
[263, 269]
[101, 109]
[73, 83]
[457, 467]
[163, 179]
[331, 347]
[239, 281]
[61, 421]

#primes = 100 #progressions = 28

(код)

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

 S= Set(); A6= A5= A4= A3= A2= [];

 for(i=1, #A,
  if(#A[i]==6, A6= concat(A6, [A[i]]); S= setunion(S, A[i]));
  if(#A[i]==5, A5= concat(A5, [A[i]]));
  if(#A[i]==4, A4= concat(A4, [A[i]]));
  if(#A[i]==3, A3= concat(A3, [A[i]]));
  if(#A[i]==2, A2= concat(A2, [A[i]]));
 );

 Z= A6;

 for(i=1, #A5,
  t= 1; for(j=1, 5, if(setsearch(S, A5[i][j]), t= 0; break()));
  if(t, Z= concat(Z, [A5[i]]); S= setunion(S, A5[i]))
 );

 for(i=1, #A4,
  t= 1; for(j=1, 4, if(setsearch(S, A4[i][j]), t= 0; break()));
  if(t, Z= concat(Z, [A4[i]]); S= setunion(S, A4[i]))
 );

 for(i=1, #A3,
  t= 1; for(j=1, 3, if(setsearch(S, A3[i][j]), t= 0; break()));
  if(t, Z= concat(Z, [A3[i]]); S= setunion(S, A3[i]))
 );

 for(i=1, #A2,
  t= 1; for(j=1, 2, if(setsearch(S, A2[i][j]), t= 0; break()));
  if(t, Z= concat(Z, [A2[i]]); S= setunion(S, A2[i]))
 );

 k= 0;
 for(i=1, #Z, k= #Z[i]+k; print(Z[i]));
 print("\n#primes = "k"    #progressions = "#Z);
};

[mihaild]

Первые 100 можно покрыть 26 прогрессиями (а 25 нельзя)

Используется синтаксис Text

[3, 181, 359]
[5, 17, 29, 41, 53]
[7, 19, 31, 43]
[7, 37, 67, 97, 127, 157]
[11, 101, 191, 281]
[13, 103, 193, 283, 373, 463]
[23, 131, 239, 347]
[29, 149, 269, 389, 509]
[47, 59, 71, 83]
[47, 179, 311, 443]
[53, 113, 173, 233, 293, 353]
[61, 199, 337]
[73, 151, 229, 307]
[79, 109, 139]
[107, 137, 167, 197, 227, 257]
[163, 271, 379, 487]
[211, 367, 523]
[223, 331, 439, 547]
[241, 277, 313, 349]
[251, 317, 383, 449]
[397, 409, 421, 433]
[401, 431, 461, 491, 521]
[457, 499, 541]
[467, 479, 491, 503]
[89, 263]
[419]
 

Код: https://github.com/mihaild/dxdy/blob/ma ... er/main.py

[dimkadimon]

mihaild в сообщении #1406985 писал(а):

Первые 100 можно покрыть 26 прогрессиями (а 25 нельзя)

Поздравляю! Думаю это оптимальное решение, так как меньше 26 прогрессий я не находил. Опишите подробнее ваш LP метод, думаю всем будет интересно.

Очень интересно что ваша программа найдет для первой 1000? Тут мой рекорд 221 прогрессий.

-- 25.07.2019, 21:24 --

Dendr в сообщении #1406874 писал(а):

Для N=1000 получается 230 прогрессий

Очень хороший результат для такого быстрого greedy алгоритма. Спасибо!

[mihaild]

dimkadimon в сообщении #1407039 писал(а):

Думаю это оптимальное решение, так как меньше 26 прогрессий я не находил

Это точно оптимальный результат (если я нигде не ошибся) - солвер доказывает оптимальность.

dimkadimon в сообщении #1407039 писал(а):

Опишите подробнее ваш LP метод, думаю всем будет интересно

Заводим по переменной на каждое простое число и каждую прогрессию длины хотя бы 3, все переменные - 0 либо 1. Добавляем ограничение $p_i \leqslant \sum_j s_{i_j}$, где $p_i$ - переменная, соответствующая $i$-му простому числу, а $s_{i_j}$ - переменные, соответствующие прогрессиям, в которые это число входит.
Дальше минимизируем $\sum s_i - \frac{1}{2} \sum p_i$ - мы платим по $1$ за каждую взятую прогрессию, и по $0.5$ за каждое непокрытое число (т.к. мы сможем непокрытые числа покрывать по два).

dimkadimon в сообщении #1407039 писал(а):

Очень интересно что ваша программа найдет для первой 1000?

Ничего. Оно уже на 200 за разумное время вряд ли посчитает.

[dimkadimon]

mihaild, спасибо за подробное объяснение!

Rivera выставил задачу на своем сайте: https://www.primepuzzles.net/puzzles/puzz_963.htm