2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Покрытие простых арифиметическими прогрессиями из простых
Сообщение18.07.2019, 06:55 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Известно что первые 10 нечетных простых можно покрыть тремя арифметическими прогрессиями из простых:

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

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

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


29/04/13
7920
Богородский
У Вас два раза встречается $17$. Это ошибка?

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

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

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

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


01/06/12
1016
Adelaide, Australia
Yadryara в сообщении #1405615 писал(а):
У Вас два раза встречается $17$. Это ошибка?

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

Yadryara в сообщении #1405615 писал(а):
Длина арифметических прогрессий ограничена снизу?

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

Yadryara в сообщении #1405615 писал(а):
$(3,13), (5,11,17,23,29), (7,19,31)$

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

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

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


16/08/05
1152
Если не ошибся, то у меня получилось, что для 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

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


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

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


24/01/19

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

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


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

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

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


29/04/13
7920
Богородский
Ещё можно последовательность $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 $

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


01/06/12
1016
Adelaide, Australia
Yadryara в сообщении #1406115 писал(а):
Ещё можно последовательность $3, 6, 10, 13, 18, ...$ в OEIS забабахать

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

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


01/06/12
1016
Adelaide, Australia
Yadryara в сообщении #1406115 писал(а):
Пример для $18$-ти

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

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


01/06/12
1016
Adelaide, Australia
А как у вас получилось покрыть 6 простых двумя прогрессиями?

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


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

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


02/04/18
240
Явно чувствую, что не наилучший алгоритм использую, но он перебирает все возможные покрытия. На поиск наименьшего покрытия уходит слишком много времени, но близкие к наименьшему - довольно скоро находятся. Для тех же 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)

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


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

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


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

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

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



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

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


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

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