2014 dxdy logo

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

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




На страницу Пред.  1 ... 240, 241, 242, 243, 244  След.
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 17:45 
Аватара пользователя
Dmitriy40 в сообщении #1705884 писал(а):
Причина аномалии с 3 в том что чисел в паттерне слишком много (больше одного), 3шт (проверяемых, с простыми), вот и не все p-1 остатков получаются допустимыми как было бы для единственного простого. С n19d252 (19 симметрично расположенных простых в интервале [0..252]) даже по модулю 17 было всего 2 допустимых остатка, остальные запрещались по одному или нескольким простым.


Да, понятно.
Вот неспроста вероятность попасть в простое (с 6*lcm) по статистике оказалась меньше теоретической. Немного - в третьем знаке, и вроде бы укладывается в три сигма...
Но запущу-ка расчет статистики на несколько тысяч кандидатов.. Может в какой-то позиции \ с каким-то простым тоже более одного запрещенного остатка.

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 18:46 
EUgeneUS в сообщении #1705887 писал(а):
Может в какой-то позиции \ с каким-то простым тоже более одного запрещенного остатка.
Ну, там может получиться что и все остатки разрешены. Например на месте 480p, оно по модулю 3 всегда даёт 0, независимо от p и значит для p на этом месте разрешены все 3 остатка по модулю 3. И по модулю 5 тоже все 5шт разрешены.

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 18:53 
Аватара пользователя
Dmitriy40 в сообщении #1705893 писал(а):
Например на месте 480p, оно по модулю 3 всегда даёт 0, независимо от p и значит для p на этом месте разрешены все 3 остатка по модулю 3.


Хммм. Остаток ноль запрещен же - он же лишнюю тройку добавит (то есть p будет делиться на 3). Аналогично для 5.

-- 14.10.2025, 19:06 --

Yadryara в сообщении #1705867 писал(а):
Ещё и в других паттернах найдены приближения. Покажу пока наилучшие:


А почему у вас пропуски (неудачи) идут на разных местах?
Вы разве не до первой неудачи цепочку проверяете?

И еще просьба - можете выслать текущий вариант программы, с которой проводите эксперименты?

 
 
 
 Re: Пентадекатлон мечты
Сообщение14.10.2025, 19:35 
Аватара пользователя
EUgeneUS в сообщении #1705895 писал(а):
А почему у вас пропуски (неудачи) идут на разных местах?

Пропусков нет только на трёх местах — там, где в этом паттерне одиночные $p$.

Кстати, наконец-то начали лучшие совпадения попадаться:

Код:
                                                                             Valids
606402818949710702556903161178143151197645296548946   11111 1 1111111111 11      18
21766102877738194392931437163144706992418461424146    11 1111 11111 1 11111      17
178380987012396308863900153677813852686655763044946   1 1111111111111 11  1      17
839190911935283032541757641339028804086245959176146   1   11111111111 11111      17
7381053290475287446784877192019650965812213151883346  111 111 1 1 111111111      17

EUgeneUS в сообщении #1705895 писал(а):
Вы разве не до первой неудачи цепочку проверяете?

Это в двух словах не объяснить.

EUgeneUS в сообщении #1705895 писал(а):
И еще просьба - можете выслать текущий вариант программы, с которой проводите эксперименты?

Выслал Дмитрию.

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 08:07 
Аватара пользователя
Считаю в 12 потоков.

1 группа паттернов 123 (720 штук) считается до 1e52.
7 групп паттернов 13-19 (по 5040 штук в каждой) считаются до 1e51.
1 группа паттернов 26 (5040 штук) считается до 1e50.
3 группы паттернов 3-5 (по 40320 штук в каждой) считаются до 1e50.

Десятки тысяч паттернов уже обсчитаны. Время для подведения предварительных итогов, пожалуй, ещё не пришло. Нынешняя топовая табличка приближений к D(48,21) среди не более чем 52-значных чисел:

Код:
Start                                                 Location               Valids
154631495973083613535277148109710834053326309716946   111  11111111111111 1      18
585605360962144936768057576267008749038198122219346   1111111 111 1111111 1      18
606402818949710702556903161178143151197645296548946   11111 1 1111111111 11      18
21766102877738194392931437163144706992418461424146    11 1111 11111 1 11111      17
88459004668425618097049432547681760440087272643346    111 111 11 11 1111111      17
178380987012396308863900153677813852686655763044946   1 1111111111111 11  1      17
373798579271459461965814865637583613001311662572946   111111111   111111 11      17
839190911935283032541757641339028804086245959176146   1   11111111111 11111      17
7381053290475287446784877192019650965812213151883346  111 111 1 1 111111111      17

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 10:22 
VAL в сообщении #1704641 писал(а):
EUgeneUS в сообщении #1704638 писал(а):
Не думаю, что вероятности найти простое в разных позициях зависимы. Скорее всего они просто оказываются разными. А вот почему они оказываются разными - это вопрос, конечно.
То есть, вероятность того, что в числе $2^{37}n$ множитель $n$ будет прост в полтора раза выше, чем вероятность его простоты в числе $3^{37}n$ ? При том же самом $n$?! Странное утверждение!
Чтобы сравнить, во сколько раз чаще встречаются числа вида $2^{34} \cdot p$ по сравнению с числами вида $3^{34} \cdot q$ (где $p$ и $q$ — простые числа), рассмотрим асимптотическую плотность таких чисел в пределах большого $x$.
Количество чисел вида $A \cdot r$ (где $A$ — фиксированное целое, $r$ — простое) до $x$ приблизительно равно:
$N_A(x) \sim \frac{x}{A \cdot \log(x/A)}.$
Применим это для $A_1 = 2^{34}$ и $A_2 = 3^{34}$:
- Для $2^{34} \cdot p$: $  N_1(x) \sim \frac{x}{2^{34} \cdot \log(x / 2^{34})}.  $
- Для $3^{34} \cdot q$: $  N_2(x) \sim \frac{x}{3^{34} \cdot \log(x / 3^{34})}.  $
Отношение количеств:
$\frac{N_1(x)}{N_2(x)} = \frac{3^{34}}{2^{34}} \cdot \frac{\log(x / 3^{34})}{\log(x / 2^{34})}.$
Упростим отношение логарифмов. Для больших $x$:
$\log(x / A) = \log x - \log A \approx \log x,$
так как $\log A$ пренебрежимо мал по сравнению с $\log x$ (например, для $x \sim 10^{100}$, $\log x \approx 230$, а $\log 2^{34} \approx 23.5$, $\log 3^{34} \approx 37.3$).
Таким образом:
$\frac{\log(x / 3^{34})}{\log(x / 2^{34})} \approx 1.$
Следовательно:
$\frac{N_1(x)}{N_2(x)} \approx \frac{3^{34}}{2^{34}} = \left(\frac{3}{2}\right)^{34}.$
Вычислим:
$\left(\frac{3}{2}\right)^{34} = \frac{3^{34}}{2^{34}} \approx \frac{1.667 \times 10^{16}}{1.717 \times 10^{10}} \approx 970\,000.$

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 11:05 
Аватара пользователя
vicvolf
Вы, конечно, всё правильно написали, но немного не про то.

Там обсуждалась вероятность, а не количество.
Поэтому
1. Вместо
vicvolf в сообщении #1705956 писал(а):
$N_A(x) \sim \frac{x}{A \cdot \log(x/A)}.$


Нужно использовать:

$P_A(x) \sim \frac{1}{\log(x/A)}.$

2. И речь шла о вероятности быть простым фиксированному числу $n$.

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 11:46 
EUgeneUS в сообщении #1705960 писал(а):
Там обсуждалась вероятность, а не количество.
Там надо степень исправить на 37, но это только увеличит соотношение.

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 12:13 
Аватара пользователя
vicvolf
VAL в сообщении #1704641 писал(а):
При том же самом $n$?!

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 12:23 
EUgeneUS в сообщении #1705960 писал(а):
2. И речь шла о вероятности быть простым фиксированному числу $n$.
Если $n$ фиксировано, то уже известно, что оно простое или составное с вероятностью 1. Вообщем, задача не так поставлена.

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 12:23 
Аватара пользователя
Получил программу от Dmitriy40

Забавный факт обнаружился:

Код:
start=6.064028e50;\\Откуда начать поиск
stop= 6.064029e50;\\Где закончить поиск

parisize = 8000000, primelimit = 1048576, factorlimit = 1048576
1-5887   606402818949710702556903161178143151197645296548946   11111 1 1111111111 11      18   [1, 3, 4, 5, 2, 7, 6, 8, 9]
18min, 43,297 ms,1], ETA: 0 ms

====
start=1.064000028e53;\\Откуда начать поиск
stop= 1.064000029e53;\\Где закончить поиск

parisize = 8000000, primelimit = 1048576, factorlimit = 1048576
10min, 55,484 ms,1], ETA: 0 ms


Для больших чисел программа перебирает заметно быстрее, чем для меньших!
Почему так оказалось - понятно. Но прогнозировать такое было сложно.

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 13:25 
Аватара пользователя
Но время удручает.

10 минут на проверку 9! паттернов в диапазоне $10^{46}$
А для вероятности 0.95 нужно $2.7 \cdot 10^{53}$

Это 51369 потоко-лет. :roll: :cry:

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 13:28 
За ночь ради интереса перебрал все 9! вариантов до 5e48, заняло 10.5ч.
Самые длинные:
Код:
14-78462    4054427843685007678761054689486739499279168620946   111 1111 1 11111 11 1      16   [2, 9, 5, 8, 7, 1, 6, 4, 3]
49-276358   1609770849692896063285412871371657574193960875346   1 1 11111 1111111  11      16   [7, 8, 6, 5, 9, 4, 2, 3, 1]
10-70334     675316765727137388857296968791369010581278046546     1  11111111 1 11111      15   [2, 7, 9, 6, 1, 5, 3, 8, 4]
22-127083   3426281091350161357284426644686896276386601483346   1   111111111 1 111 1      15   [4, 2, 3, 7, 1, 5, 8, 6, 9]
25-134288   2581791426301369099934560090141163977369909438546   1 11 11 1 111111 11 1      15   [4, 3, 7, 6, 1, 5, 2, 9, 8]
31-177706   1777730187070289597223879408604491923932932819346   1111 111  11  11111 1      15   [5, 4, 2, 8, 9, 3, 6, 7, 1]
34-196681    385236555204379860040700086316757403359126675346    1 1 111 111 11 11111      15   [5, 9, 1, 3, 2, 4, 6, 7, 8]
35-197370   4782169045122473198930066445070685279518093116946    111  1  1111 1111111      15   [5, 9, 2, 1, 7, 6, 8, 4, 3]
42-227385   4888462525191848396632635165082679532714444488146   1111111 1  11 1 11 11      15   [6, 7, 1, 8, 9, 3, 4, 2, 5]
44-239119   1203184497465162855348104603765014756231359420946   1 1 111 11 11 11 1111      15   [6, 9, 4, 1, 7, 3, 2, 5, 8]
51-286154   2105106151650200055785788743993643318789327414546   11 1 11 111 1 11 1111      15   [8, 1, 7, 4, 6, 2, 3, 9, 5]
59-342149   2118533566899845201784331597262560551434157224146    11 11111 11111 1  11      15   [9, 4, 8, 2, 3, 1, 7, 5, 6]

EUgeneUS в сообщении #1705972 писал(а):
Для больших чисел программа перебирает заметно быстрее, чем для меньших!
А с ускорителями такого не должно быть - здесь "виноваты" ранние isprime, которые для больших чисел отбраковывают кандидатов чаще (невзирая на замедление проверки каждого этими же isprime), ускорители же работают в остатках по модулям, которые не зависят от величины чисел.

-- 15.10.2025, 13:44 --

EUgeneUS в сообщении #1705977 писал(а):
10 минут на проверку 9! паттернов в диапазоне $10^{46}$
А для вероятности 0.95 нужно $2.7 \cdot 10^{53}$

Это 51369 потоко-лет. :roll: :cry:
Это не слишком корректно, у меня что 1e45, что 1e46, перебираются одинаковое время, 1e47 всего вдвое дольше, и только дальше время растёт линейно - т.е. до 1e48 время тратится не на факторизацию, а до 1e47 и не на проверку паттернов. Потому что поставив next перед foreach(ost,dd, получим время работы внешнего цикла 5 минут для 1e47, а поставив next на две строки ниже перед forstep(i=sta+dd,sto,shag, получим время 13 минут для 1e47, почти как и для проверки 1e45 и 1e46 (т.е. по 1e46 проверка почти бесплатная).
Я же специально сделал Вам вывод ETA чтобы за несколько минут (по первым десяткам размещений, по первым единицам сильно ошибается) оценить общее требуемое время и не ждать часами и сутками для выяснения какая скорость проверки.
У меня до 2.7e48 собирается работать 6ч40м, значит до 2.7e53 надо 666667ч=76г. А оценка за ночь 10.5ч на 5e48 даёт 64г на 2.7e53. В одном потоке. Так что полсотни потоко-лет похоже на правду.
Поставив next строкой ниже, сразу после цикла forstep(i=sta+dd,sto,shag, получим время перебора всех паттернов без проверок вообще до 2.7e50 в 6.5ч или 0.74г до 2.7e53 или 1% от общего времени, что показывает ненужность оптимизации всех внешних циклов (при сохранении количества итераций) вплоть до проверки каждого паттерна.

-- 15.10.2025, 13:49 --

PS. Чтобы убрать огрызок ETA из вывода времени, надо добавить штуки три-четыре \t в последний print: print("Time: ",strtime(getwalltime()-t0),"\t\t\t\t").

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 17:07 
Аватара пользователя
Dmitriy40 в сообщении #1705979 писал(а):
Это не слишком корректно,


Да, где-то прокосячил с оценками.
Теперь так:
Код:
start=1.0e53;\\Откуда начать поиск
stop= 1.001e53;\\Где закончить поиск
...
parisize = 8000000, primelimit = 1048576, factorlimit = 1048576
1-102   100044158610448611111516844769147625506077436388080146   11 1 111 111 11  1 11      14   [1, 2, 3, 4, 9, 5, 8, 7, 6]
[1,2,4,3,5,9,7,6,8], ETA: 304h, 24min, 30,245 ms


304 часа на 1/2700 потребного количества.
94 потоко-года.
Похоже на Ваши оценки с учётом, что комп у меня медленнее.

-- 15.10.2025, 17:29 --

Yadryara в сообщении #1705949 писал(а):
Время для подведения предварительных итогов, пожалуй, ещё не пришло.


Выводы тут простые.
С такими мощностями:
EUgeneUS в сообщении #1705332 писал(а):
У меня сейчас - потоков 6-7. Скорее всего, можно будет восстановить до 14-15.

Dmitriy40 в сообщении #1705349 писал(а):
Я могу запустить 20-25 эквивалентных потока (4 обычных плюс 64 более медленных). Медленные сейчас заняты другим, но то можно и бросить.

Yadryara в сообщении #1705335 писал(а):
У меня 12 потоков и все 12 пока могу выделить.


Считать будем 1-3 года.

А какие ещё можно сделать выводы?

DemISdx, VAL, а вы будете участвовать в длительном, но перспективном расчете рекорда $D(48,21)$?

 
 
 
 Re: Пентадекатлон мечты
Сообщение15.10.2025, 17:42 
EUgeneUS в сообщении #1705994 писал(а):
Считать будем 1-3 года.
А какие ещё можно сделать выводы?
Проверить паттерн с 4-мя простыми, его реальную скорость и требуемое время по Вашей оценке.

Использовать ускорители. Многопоточно (раньше были однопоточными). Может быть даже смогу сделать прямо в них перебор 9! вариантов. И надо бы проверить даст ли выигрыш использование КТО, для трёх проверяемых мест как-то она слабо ускоряет, а усложняет код сильно.

Без этого мутить на пару лет счёт считаю рано.

Без ускорителей мне считать годами как-то влом.

 
 
 [ Сообщений: 3654 ]  На страницу Пред.  1 ... 240, 241, 242, 243, 244  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group