2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Минимальные простые в строке
Сообщение27.12.2021, 19:58 
Аватара пользователя


22/11/13
498
Имеем следующее семейство бесконечных последовательностей простых чисел:

$$\begin{bmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\color{red}{3} & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 \\
\color{red}{5} & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\
13 & \color{red}{11} & 19 & 17 & 29 & 23 & 31 & 37 & 43 & 41 \\
19 & \color{red}{17} & 31 & 23 & 41 & 29 & 37 & 43 & 61 & 47 \\
43 & 41 & 47 & \color{red}{31} & 73 & 37 & 53 & 59 & 101 & 71 \\
53 & 61 & 67 & \color{red}{41} & 83 & 47 & 73 & 79 & 131 & 101 \\
89 & 73 & 79 & \color{red}{53} & 107 & 59 & 97 & 103 & 167 & 113 \\
103 & 101 & 107 & \color{red}{67} & 149 & 73 & 139 & 131 & 181 & 127 \\
151 & 149 & 139 & \color{red}{83} & 181 & 89 & 251 & 163 & 197 & 191 \\
223 & 167 & 157 & \color{red}{101} & 199 & 107 & 269 & 181 & 233 & 227 \\
263 & 227 & 197 & 181 & 239 & \color{red}{127} & 349 & 241 & 293 & 307 \\
307 & 271 & 241 & 269 & 283 & \color{red}{149} & 503 & 263 & 337 & 373 \\
331 & 367 & 313 & 293 & 307 & \color{red}{173} & 599 & 311 & 409 & 397 \\
383 & 419 & 443 & 397 & 359 & \color{red}{199} & 677 & 337 & 461 & 449 \\
439 & 503 & 499 & 509 & 443 & \color{red}{227} & 733 & 421 & 601 & 617 \\
499 & 563 & 619 & 569 & 503 & \color{red}{257} & 823 & 541 & 631 & 647 \\
563 & 659 & 683 & 601 & 599 & 353 & 887 & 701 & 727 & 743 \\
631 & 727 & 751 & 839 & 701 & 421 & 1091 & 769 & 761 & 811 \\
739 & 907 & 787 & 911 & 773 & 457 & 1163 & 877 & 797 & 883 \\
853 & 983 & 863 & 1063 & 811 & 571 & 1201 & 953 & 911 & 997 
\end{bmatrix}$$

Числа выделенные красным - это минимальные в каждой строке. Вот как они начинаются:
$$3, 5, 11, 17, 31, 41, 53, 67, 83, 101, 127, 149, 173, 199, 227, 257, 313, 347, 383, 421, 461, 503, 547, 593$$
Их, собственно, и требуется отыскать (и чем больше, тем лучше).

Здесь $k$-ая последовательность простых чисел задается следующим образом:

  • начинается с простого числа под номером $k+1$, назовем его $p_1$
  • второе число - это наименьшее простое $p_2$, такое что $2|(p_2-p_1)$
  • третье число - это наименьшее простое $p_3$, такое что $4|(p_3-p_2)$
  • четвертое число - это наименьшее простое $p_4$, такое что $6|(p_4-p_3)$
  • $n$-ое число - это наименьшее простое $p_n$, такое что $2(n-1)|(p_n-p_{n-1})$

Вот простейшая и крайне медленно работающая реализации на PARI, которая выдает последовательности с дубликатами (в данном конкретном случае работает для $p_1=3$):
Код:
d(n)=prime(n+1)
d2(n)=if(n==1,2,if(d1(n)>d1(n-1),d2(n-1)+2,d2(n-1)))
d1(n)=if(n==1,d(1),if((d(n)-d1(n-1))%d2(n-1)==0,d(n),d1(n-1)))

В том же Excel'е ввод аналогичных формул мгновенно дает результат, от рутины избавляют макросы, но я уверен, что можно слепить что-нибудь гораздо более простое.

 Профиль  
                  
 
 Re: Минимальные простые в строке
Сообщение27.12.2021, 20:33 
Заблокирован


19/02/13

2388
А как задаётся ваша матрица, в которой искомые простые скрыты? Что это за строки?

 Профиль  
                  
 
 Re: Минимальные простые в строке
Сообщение27.12.2021, 21:35 
Аватара пользователя


22/11/13
498
Vladimir-80 в сообщении #1544492 писал(а):
А как задаётся ваша матрица, в которой искомые простые скрыты? Что это за строки?

В матрице $k$-ый столбец - это $k$-ая последовательность.
kthxbye в сообщении #1544484 писал(а):
Здесь $k$-ая последовательность простых чисел задается следующим образом:

начинается с простого числа под номером $k+1$, назовем его $p_1$
второе число - это наименьшее простое $p_2$, такое что $2|(p_2-p_1)$
третье число - это наименьшее простое $p_3$, такое что $4|(p_3-p_2)$
четвертое число - это наименьшее простое $p_4$, такое что $6|(p_4-p_3)$
$n$-ое число - это наименьшее простое $p_n$, такое что $2(n-1)|(p_n-p_{n-1})$

 Профиль  
                  
 
 Re: Минимальные простые в строке
Сообщение27.12.2021, 21:50 
Заблокирован


19/02/13

2388
kthxbye в сообщении #1544505 писал(а):
В матрице $k$-ый столбец - это $k$-ая последовательность.


Это как, если первый столбец начинается с единицы?
При том, что
kthxbye в сообщении #1544484 писал(а):
$k$-ая последовательность простых чисел задается следующим образом:

начинается с простого числа под номером $k+1$, назовем его $p_1$


 Профиль  
                  
 
 Re: Минимальные простые в строке
Сообщение27.12.2021, 22:01 
Аватара пользователя


22/11/13
498
Vladimir-80 в сообщении #1544507 писал(а):
Это как, если первый столбец начинается с единицы?

Первая строка - индексы последовательностей.

 Профиль  
                  
 
 Re: Минимальные простые в строке
Сообщение27.12.2021, 22:14 
Заслуженный участник


20/08/14
11073
Россия, Москва
Используется синтаксис Text
? v=primes([3,10^5]); forstep(k=0,200,2, if(k>0, for(i=1,#v, forprimestep(x=v[i]+k,,k, v[i]=x;break););); print1(vecmin(v),", "); );
3, 5, 11, 17, 31, 41, 53, 67, 83, 101, 127, 149, 173, 199, 227, 257, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601, 2081, 2819, 2903, 3677, 3853, 3943, 4127, 4409, 4793, 5087, 5387, 5591, 5903, 6221, 6329, 6659, 6883, 6997, 7229, 7583, 7703, 8069, 8317, 8443, 8699, 9349, 9613, 11087, 11903, 12041, 12601, 12743, 13463, 13901, 14197, 14347, 15107, 15569, 15881, 16829, 17789, 19559, 20051, 20549, 20717, 20887, 21059, 21407, 22111, 23357, 23537, 23719, 25999, 26297, 26861, 27241, 27817, 29147, 30059, 30707, 31051,
time = 1,296 ms.


-- 27.12.2021, 22:34 --

Забавно что 25999, 29147, 31051 все находятся левее предыдущих минимумов. Т.е. уход минимумов вправо вовсе не монотонный.

-- 27.12.2021, 22:54 --

Список простых, в колонке от которых находится соответствующий минимум:
Используется синтаксис Text
3, 3, 5, 5, 11, 11, 11, 11, 11, 11, 17, 17, 17, 17, 17, 17, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 179, 2213, 2213, 2213, 2213, 109, 919, 1249, 919, 919, 919, 919, 919, 919, 919, 919, 919, 919, 919, 2213, 2213, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 839, 839, 839, 31, 31, 31, 31, 31, 31, 2213, 2213, 2213, 2213, 281, 2213, 2213, 2213, 281, 281, 281, 281, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2213, 2503, 61, 2213, 61, 61, 61, 61, 61, 61, 61, 61, 61, 911, 911, 911, 911, 31, 31, 31, 31, 31, 31, 31, 31, 5857, 5857, 5857, 5857, 5857, 5857, 5857, 5857,

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

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



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

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


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

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