2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение23.07.2019, 17:07 


16/08/05
1146
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.

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение23.07.2019, 17:47 
Аватара пользователя


29/04/13
7128
Богородский
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 $

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение23.07.2019, 18:36 


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

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

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение23.07.2019, 18:52 
Аватара пользователя


29/04/13
7128
Богородский
dmd, ну да, так и есть. $6$ насильно укороченных $6$-к у вас считаются и как $5$-ки.

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

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение23.07.2019, 19:16 


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

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение24.07.2019, 15:44 


02/04/18
240
И правда, так гораздо быстрее. Хотя нет 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 )

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение24.07.2019, 17:36 


16/08/05
1146
Если без оптимизации и без повторов, то 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);
};

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение25.07.2019, 01:10 
Заслуженный участник
Аватара пользователя


16/07/14
8348
Цюрих
Первые 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

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение25.07.2019, 15:25 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
mihaild в сообщении #1406985 писал(а):
Первые 100 можно покрыть 26 прогрессиями (а 25 нельзя)

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

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

-- 25.07.2019, 21:24 --

Dendr в сообщении #1406874 писал(а):
Для N=1000 получается 230 прогрессий

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

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение26.07.2019, 00:42 
Заслуженный участник
Аватара пользователя


16/07/14
8348
Цюрих
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 за разумное время вряд ли посчитает.

 Профиль  
                  
 
 Re: Покрытие простых арифиметическими прогрессиями из простых
Сообщение28.07.2019, 04:46 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
mihaild, спасибо за подробное объяснение!

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group