2014 dxdy logo

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

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




На страницу Пред.  1 ... 230, 231, 232, 233, 234
 
 Re: Пентадекатлон мечты
Сообщение07.10.2025, 13:00 
Yadryara в сообщении #1704792 писал(а):
Самое главное что именно количество делителей ведь интересует, а не то как именно они соберутся.
Не скажите, второе тоже интересует: стоит ли размещать в паттерн кубы и более старшие степени, ради скорости isprime против factor.
В общем инструменты есть, можно развлекаться.

 
 
 
 Re: Пентадекатлон мечты
Сообщение07.10.2025, 15:43 
Yadryara в сообщении #1704763 писал(а):
А докуда проверено по этой программе? И какова вообще история поиска 21-ки (очковтирательства :-) ) ? То есть как долго длился поиск, по каким паттернам, что найдено за это время?
Историю поиска помню плохо: много воды утекло.
Всего у меня 4 программки (при поиске 20-ки использовалось полсотни одновременно, а всего больше 100).
Одна из них, судя по протоколам запускалась многожды, остальные - пару тройку раз. Успехи не впечатляют. Больше 18 из 21 позиции не совпали ни разу. Вот наиболее близкие промахи:
Код:
90715763859608616730714175556209422588238079327693680146
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0] 18
85214054718602387929373909199904790013177732572016804946
# [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0] 18
29825395661688231658603848650736899419196053570174356946
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0] 18
Приведены лишь те позиции, где выполнялась факторизация. До этого в еще трех позициях сработал ispseudoprime().
То, что в последних позициях везде нули, говорит лишь о том, что после второго промаха поиск прекращался.

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 02:41 
Аватара пользователя
Благодарю.

Удобно действовать по аналогии. Как видим на примере паттерна из единственной показанной здесь программы для поиска 21-к, он тоже построен согласно Концепции Минимальных Квадратов (КМК). Только для поиска D(12,15) была КМК37-11, а здесь КМК59-3.

Для D(12,15) — 6 обязательных чисел и 6 произвольных.
Для D(48,21) — 8 обязательных чисел и 9 произвольных.

Для D(12,15) — комплект состоит из $64\cdot 6! = 46080$ паттернов.
Для D(48,21) — комплект состоит из $x\cdot 9!$ паттернов.

То есть речь идёт, видимо, о миллионах паттернов в одном только комплекте КМК59-3.

И помнится немало сил было потрачено на поиск наиболее перспективных паттернов из этих 46080. Насколько помню, VAL убеждал, что различия если и есть, то крошечные. И в итоге было решено проверять все 46080. Поэтому и компиляция занимала так много времени, что для каждого паттерна компилилась своя программа.

Но. Впс два года занимался кортежами. Был придуман приём, который я назвал "разбиение по чистоте". И мы с Демисом тщательно проверили реальный эффект от него, попутно найдя весьма немало кортежей.

Можно ли его применить здесь? Хочется сказать: да, конечно. Ведь здесь тоже задача сводится к поиску простых чисел, будь то одиночные $p$, парные $pq$ или тройные-четверные $pqr$-$pqrs$. Как понял, для 48 делителей одиночных простых — от 3-х до 7.

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 04:27 
Аватара пользователя
VAL в сообщении #1704814 писал(а):
Больше 18 из 21 позиции не совпали ни разу.

Не согласен. Один раз 48 делителей было у 19-ти чисел из 21-го. Для полноты картины я проверял сплошную полосу шириной в 31 число:

Код:
      1112222222222333333333344444444    H21   ML     ALL
e53   7890123456789012345678901234567

852    1111111 1111111111 11               2   10      19

907    1111111111111111 1  1     1         3   16      19
298    111111111111111 11  1     1         3   15      19
1073   1 1111111111111  1111               3   13      18

1119   111 111111111111   11               4   12      17

1124   111111111111 11   1 1               5   12      16

H21 — это как раз важнейший критерий, количество пропусков (Hole) в полосе паттерна шириной 21.
ML — MaxLen, наибольшая подрядность.
АLL — общее количество чисел по 48 делителей в полосе шириной 31.

Пока нет путаницы: 56-значные найдены Вами, 57-значные — Макаровой по Вашей программе.

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 08:11 
Аватара пользователя
Yadryara в сообщении #1704792 писал(а):
Самое главное что именно количество делителей ведь интересует, а не то как именно они соберутся.


Для моих целей интересует именно количество делителей.

-- 08.10.2025, 08:14 --

Yadryara в сообщении #1704915 писал(а):
Насколько помню, VAL убеждал, что различия если и есть, то крошечные. И в итоге было решено проверять все 46080. Поэтому и компиляция занимала так много времени, что для каждого паттерна компилилась своя программа.

Но. Впс два года занимался кортежами. Был придуман приём, который я назвал "разбиение по чистоте". И мы с Демисом тщательно проверили реальный эффект от него, попутно найдя весьма немало кортежей.


Именно для оценки "качества" паттернов (и не только) решалась задача по оценке вероятности найти цепочку по паттерну за один раз.

В целом она решена. Хотя и требует вычислительных экспериментов для каждого паттерна.

Ниже опишу пошаговую "инструкцию". Чтобы в одном месте было.

-- 08.10.2025, 08:34 --

1. Шаг 1.
Считаем "базовые" вероятности $P^{(k)}(N)$ для нахождения чисел, свободных от квадратов, с $k$ простыми различными делителями.
Для этого берем:
vicvolf в сообщении #1703438 писал(а):
Асимптотическая формула для количества $k$-почти простых чисел $\pi_k(x)$, при фиксированном $x$:

$\pi_k(x) \sim \frac{x}{\log x} \cdot \frac{(\log \log x)^{k-1}}{(k-1)!}$


И дифференцируем:
$P^{(k)}(N) = \frac{d \pi_k(N)}{d N}$

"Базовые вероятности" для каждого $k$ зависят только от $N$.
Можно брать с точностью до $O(\frac{1}{(\ln(N))^2})$. Я в своих экспериментах брал полную производную.

2. Шаг 2. Считаем "базовые" вероятности $P_i^{(k_i)}(N_i)$ - для каждого места в шаблоне.
Для каждого i-го места в шаблоне считаем
а) $a_i$ - произведение всех множителей, заданных шаблоном
б) $N_i = N/a_i$ - число, где ищем неизвестные с учетом, что оно меньше, чем $N$
в) подставляем $N_i$ в "базовые вероятности": $P_i^{(k_i)}(N_i)$. $k_i$ - тоже задаётся шаблоном, это необходимое количество простых множителей в неизвестном числе.

"Базовые" вероятности $P_i^{(k_i)}(N_i)$ для каждого места в шаблоне зависят от $N$ и от самого шаблона. Но не от способа "запуска шаблона".

3. Шаг3. Фильтрация при запуске расчета по шаблону и поправочные коэффициенты.

Как известно, применение шаблона с найденным шагом даёт "бракованные" цепочки: для каждой второй добавляется лишняя двойка, для каждой третьей - лишняя тройка и т.д.
Как для "боевого" расчета, та и для расчетов для нахождения поправочных коэффициентов, должна выполняться предварительная фильтрация для исключения всех таких цепочек.
Дальнейшее справедливо при соблюдении этого условия.

При применении шаблона гарантируется, что неизвестные числа не делятся на простые, которые применяются в шаблоне. Это сильно увеличивает вероятность найти простое, менее сильно увеличивает вероятность найти $pq$ и т.д.
Поэтому нужно найти поправочные коэффициенты $b_k$ - насколько увеличиваются "базовые вероятности" при применении шаблона.

Поправочный коэффициент для неизвестных простых легко рассчитывается аналитически: $\frac{1}{b_1} = \prod\limits_{p_l}^{}(1 - 1/p_l)$, где произведение считается по всем простым, которые используются в шаблоне в любой степени (в расчете используется первая степень для всех простых!).
Для бОльшего количество простых множителей у меня нет аналитического выражения для поправочных коэффициентов (для $b_k, k>1$), их нужно рассчитывать численно. Об этом ниже.

Поправочные коэффициенты зависят от шаблона (от того какие простые числа там используются), но не зависят от $N$ и от номера места в шаблоне (то есть для всех неизвестных простых будет один и тот же поправочный коэффициент, для всех $pq$ - один и тот же свой, и т.д.)

4. Шаг 4. Финальный.
Умножаем базовые вероятности для каждого места в шаблоне на поправочный коэффициент, и получаем вероятность найти подходящее неизвестное число для каждого места в шаблоне: $\hat{P_i (N)} = b_{k_i}P_i^{(k_i)}(N_i)$
Можно эти вероятности перемножить и получить вероятность найти цепочку за одну проверку для данного шаблона, если искать в районе числа $N$.

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 09:18 
Аватара пользователя
3.1. Шаг 3.1. Дополнительный.
Расчет $b_k, k>1$

а) Нужно выбрать количество испытаний $n$ - чтобы собрать статистику, достаточную для оценки $b_k$ с точностью до 3-го значащего знака.
несколько сотен тысяч, может быть - миллион, представляется достаточным.
б) Исходя из $n$ и известного шага нужно выбрать $N$ - размерность чисел, где будет осуществляться расчет.
Порядок $N$ не должен сильно изменяться при проведении $n$.
Неизменность десятичного порядка выглядит обязательной. Но лучше бы все $n$ укладывались в $[N, 2N]$.
в) провести расчет, получить оценки вероятностей для $\hat{P_i (N)}$.
г) зная $N$ и экспериментальные оценки $\hat{P_i (N)}$, расcчитываем оценки для $b_k$.
д) если в шаблоне несколько мест с одинаковым $k$, то по ним можно усреднить, для повышения точности оценки $b_k$
е) проверяем, что оценка $b_1$ (для неизвестных простых) совпадает со значением, полученным аналитически. Если не совпадает, то это указывает, скорее всего на некорректную "предварительную фильтрацию" (см. Шаг 3).

Собственно говоря, всё.
Позже напишу, что со всем этим можно делать.

-- 08.10.2025, 09:48 --

Что со всем этим можно делать.

1. Совпадение аналитической вероятности с экспериментальной оценкой для неизвестных простых - индикатор, что "предварительная фильтрация" эффективна.
В частности, для пентадекатлона:
аналитическая вероятность для простых в районе $N=10^{38}$: от $0.078$ до $0.084$ (для разных позиций первого попавшегося шаблона, который сохранился у меня в архивах),
а экспериментальная - около $0.06$
Это указывает, что "предварительная фильтрация" путем умножения шага на $6$ - неэффективна.
К тому же такая "предварительная фильтрация" выкидывает из проверки половину не "бракованных" цепочек.

2. Можно сравнивать, какие шаблоны "лучше", "какие" хуже, а какие примерно одинаковы.
В частности, легко получить ответ - есть ли лучшие или худшие шаблоны, если переставлять необязательные простые в квадратах?
Предварительно, такие перестановки влияют только на $N_i$, и то в очень ограниченном виде. А значит шаблоны с перестановкой необязательных простых в квадратах примено одинаковы.
Но у желающих появился способ это проверить.

3. Можно прогнозировать, в каком порядке $N$ найдётся цепочка.

4. Если известны оценки (хотя бы в попугаях) времени проверки на $p, pq,$ и т.д. - можно оценивать ожидаемое время нахождения цепочки.

5. С учетом п.4. можно сравнивать шаблоны по ожидаемому времени нахождения цепочек. Только нужно не забывать, что для разных шаблонов - разный шаг и по разному растёт $N$

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 10:26 
Аватара пользователя
Я вот выше писал, что мол адаптируйте и считайте. Гладко было на бумаге.

Сам попытался адаптировать быструю программу для D(48,20) для счёта D(48,21). И подзапутался, ибо старая для D(48,20) и менее старая для D(48,21) не просто разные, они отличаются сильнее чем поначалу казалось.

Понятно что массив M это старый MM,
массив u это старый uu, только нумерация позиций не с 0, а с 1-цы.

А вот nu больше похож на u чем на старый u2.

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 10:33 
Аватара пользователя
И ещё пара комментариев

i. $pqr$ и $p^3r$

При экспериментальном расчёте $b_3$ (для $pqr$) нужно учитывать "попадания" именно в $pqr$, но не в $p^3r$.
Дело в том, что вероятность попасть в $pqr$ зависит сильно другим образом от $N$, чем вероятность попасть в $p^3r$.
При "боевом" расчете $N$ будет гораздо больше, чем при оценке $b_3$, и вероятность попасть в $p^3r$ улетит в ноль. А рассчитанный $b_3$ окажется завышенным. Не сильно завышенным, но всё равно неприятно.

Аналогично и для подобных случаев ($pqrs$, $p^8s$ и $p^3rs$, и т.д.)

ii. Расчет $b_k$ в случае "неэффективной предварительной фильтрации".

В случае "неэффективной предварительной фильтрации" оценки $b_k$ всё также не будут зависеть от $N$, и вся методика будет работать.
Конечно, при условии, что "предварительная фильтрация" будет такой же, как для оценки $b_k$, так и для собственно поиска цепочек.
Но это не отменяет того, что на эффективность "предварительной фильтрации" нужно обращать внимание. Всё таки иметь вероятность от $0.078$ до $0.084$ в 11 позициях, гораздо приятнее, чем $0.06$ :wink:

 
 
 
 Re: Пентадекатлон мечты
Сообщение08.10.2025, 14:03 
Аватара пользователя
EUgeneUS в сообщении #1704929 писал(а):
Для моих целей интересует именно количество делителей.

Тут неправильно написал. Интересуют именно, как соберутся.
Более подробно в комментарии i. в сообщении выше.

 
 
 [ Сообщений: 3504 ]  На страницу Пред.  1 ... 230, 231, 232, 233, 234


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