Пентадекатлон мечты

[Dmitriy40]

VAL

(Оффтоп)

509562375280524362136320293261120283041279785753884888244145194356349740254034836192041791475412215036355843721 = 13304622419747522542973160667251660190698490272728952923 × 38299649490556092026602223404448677843168946572185307627

Хватило 3ч (в 4 потока).

[VAL]

Dmitriy40 в сообщении #1703408 писал(а):

VAL
[..]
Хватило 3ч (в 4 потока).

Спасибо!

$M(3240) \ge 8$

(Начало цепочки)

n = 1408122207239958728018574844975712259427979872544319332258136622834363590703726036929774305181819808373418581005667698330327482208790271827057998547199999998
n + 2 = 2^14 × 5^8 × 89^2 × 25944929 × 68136224967806995718792016604249 × 
15712663351871928339625410119099170187526877499160049840325596177644987460018050948804080445886324881353 
n + 6 = 2^2 × 19^4 × 73^2 × 79^2 × 83^2 × 23137291152257624348682247441 × 13304622419747522542973160667251660190698490272728952923 × 38299649490556092026602223404448677843168946572185307627 

[DemISdx]

VAL в сообщении #1703391 писал(а):

Пора бы завершить разминку, идущую параллельно поиска рекорда .

У меня в работе остались пока только не разминочные.
Где 10285..., по состоянию на 18:00 субботы, nfs требовал еще 20 часов работы.
А 170440... , запущенное ранее на сутки (если правильно помню), пока даже не прошло ecm.
Из "рекордных" https://dxdy.ru/post1703286.html#p1703286

[VAL]

В отличие от предыдущего случая уверенности в требуемом результате нет. Но шанс есть.

(2 prime factors wanted)

335467021637015542203063713239394664830759606837240602304368187184044184636395585268811591514264236958244086767398370987467669170886552640776777766410907632680699346922657 (171 digits) = pq?

[Yadryara]

Hi, Hugo.

ozheredov в сообщении #1703354 писал(а):

Догадайтесь, кого не хватает.

21-ки не хватает. Прячется пока.

Нашёл здесь в теме свою старую программу. Начал детально разбираться. С D(4,3) уже разобрался, стал методично по новой вникать в D(6,5).

Сначала вник, посчитал, а затем уже стал по новой читать Марафонскую статью. Помните, я уже сообщал о небольшой ошибке в ней. Cейчас увидел и ещё целую кучу всяческих очепяток.

Написал прогу, которая пока что находит все 19 пятёрок до 1e19. Буду пытаться ускорять.

VAL в сообщении #1703283 писал(а):

Ответ на вопрос из другой темы, который более уместен здесь.

А как увидели тему-то. Сработало упоминание ника или наконец-то начали читать "Активные темы"?

Вот как раз в ту тему и приглашаю: сравнить скорости программ.

[vicvolf]

VAL в сообщении #1703384 писал(а):

[7.350000, 22.64000, 29.67000, 23.38000, 11.93000, 3.840000, 1.190000]

Здесь слева направо процент: $p; pq; pqr; pqrs; pqrst; pqrstu;$ более 6-и простых. Это статистика для цепочек длины 10. Соответственно числа 30-значные

Асимптотическая формула для количества $k$-почти простых чисел $\pi_k(x)$, при фиксированном $x$:

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

показывает, что поведение $\pi_k(x)$ как функции от $k$ (при фиксированном большом $x$) имеет максимум. А именно, отношение последовательных значений:

$\frac{\pi_{k+1}(x)}{\pi_k(x)} \sim \frac{\log \log x}{k}$

Таким образом:
- Если $k < \log \log x$, то отношение больше 1, и $\pi_k(x)$ возрастает с ростом $k$.
- Если $k > \log \log x$, то отношение меньше 1, и $\pi_k(x)$ убывает с ростом $k$.

Максимум достигается при $k \approx \log \log x$, что согласуется с теоремой Харди-Рамануджана о среднем количестве простых делителей числа.

Поэтому при фиксированном $x$ количество $k$-почти простых чисел сначала возрастает с ростом $k$, достигает максимума при $k \approx \log \log x$, а затем убывает.
Ниже приведена таблица для $x$ от $10^{10}$ до $10^{100}$, где вычислено $\log \log x$ и определено $k_{\text{max}}$ — значение $k$, максимизирующее $\pi_k(x)$.

| $x$ | $\log \log x$ (приблизительно) | $k_{\text{max}}$ |
|-------------|----------------------------------|-------------------|
| $10^{10}$ | 3.14 | 4 |
| $10^{20}$ | 3.83 | 4 |
| $10^{30}$ | 4.24 | 5 |
| $10^{40}$ | 4.52 | 5 |
| $10^{50}$ | 4.75 | 5 |
| $10^{60}$ | 4.93 | 5 |
| $10^{70}$ | 5.08 | 6 |
| $10^{80}$ | 5.22 | 6 |
| $10^{90}$ | 5.33 | 6 |
| $10^{100}$| 5.44 | 6 |

Эта таблица показывает, что распределение $k$-почти простых чисел имеет колоколообразную форму с максимумом, сдвигающимся вправо с увеличением $x$.

Для $x = 10^{100}$ рассмотрим относительную долю $P(k)$ — нормированную плотность, которая показывает вклад каждого $k$ в общее количество $k$-почти простых чисел.
Для этого вычисляем $R(k) = \frac{(\log \log x)^{k-1}}{(k-1)!}$ для $k$ от 1 до 15, затем нормируем так, чтобы сумма $R(k)$ равнялась 1.

Таблица плотностей $P(k)$ для $x = 10^{100}$
| $k$ | $R(k)$ | $P(k)$ (нормированная) |
|-------|----------|--------------------------|
| 1 | 1.000 | 0.00435 |
| 2 | 5.438 | 0.02368 |
| 3 | 14.785 | 0.06438 |
| 4 | 26.800 | 0.1167 |
| 5 | 36.425 | 0.1586 |
| 6 | 39.608 | 0.1725 |
| 7 | 35.890 | 0.1563 |
| 8 | 27.880 | 0.1214 |
| 9 | 18.940 | 0.0825 |
| 10 | 11.440 | 0.0498 |
| 11 | 6.220 | 0.0271 |
| 12 | 3.076 | 0.0134 |
| 13 | 1.394 | 0.00607 |
| 14 | 0.583 | 0.00254 |
| 15 | 0.226 | 0.000984 |

Распределение напоминает распределение Пуассона с параметром $\lambda = \log \log x \approx 5.438$. Распределение имеет длинный хвост справа.

[VAL]

vicvolf в сообщении #1703438 писал(а):

VAL в сообщении #1703384 писал(а):

[7.350000, 22.64000, 29.67000, 23.38000, 11.93000, 3.840000, 1.190000]

Здесь слева направо процент: $p; pq; pqr; pqrs; pqrst; pqrstu;$ более 6-и простых. Это статистика для цепочек длины 10. Соответственно числа 30-значные

Асимптотическая формула для количества $k$-почти простых чисел $\pi_k(x)$, при фиксированном $x$:

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

Нас не интересуют именно числа свободные от квадратов. Среди тех, что обозначены у меня, например, через $pqr$ могут встречаться и числа вида $p^2qr$. То есть, по сути, это числа, у которых значение функции $\omega$ равно 3. Просто в виду специфики исследуемых чисел (я еще раз подчеркиваю , что наши числа не подчиняются общей статистике) вероятность наличия квадратов в разложении мала и практически не влияет на интересующие нас оценки.

-- 28 сен 2025, 13:32 --

Yadryara в сообщении #1703435 писал(а):

Сначала вник, посчитал, а затем уже стал по новой читать Марафонскую статью
Помните, я уже сообщал о небольшой ошибке в ней.

К сожалению, не помню. Напомните, пожалуйста.
Вычистить из Марафона все опечатки нереально Но ошибки стараюсь устранять.

[Yadryara]

VAL в сообщении #1703447 писал(а):

К сожалению, не помню. Напомните, пожалуйста.

Если помнить хотя бы одно ключевое слово, найти не проблема:

VAL в сообщении #1566764 писал(а):

Да, похоже, соврал. Спасибо, за бдительность!
Впрочем, более длинным доказательство не станет:

[vicvolf]

VAL в сообщении #1703447 писал(а):

Нас не интересуют именно числа свободные от квадратов. Среди тех, что обозначены у меня, например, через $pqr$ могут встречаться и числа вида $p^2qr$. То есть, по сути, это числа, у которых значение функции $\omega$ равно 3. Просто в виду специфики исследуемых чисел (я еще раз подчеркиваю , что наши числа не подчиняются общей статистике) вероятность наличия квадратов в разложении мала и практически не влияет на интересующие нас оценки.

В этом случае главный член асимптотики совпадает с приведенной асимптотикой для $k$-почти простых чисел. Разница проявляется в членах более низкого порядка.

[VAL]

Yadryara в сообщении #1703452 писал(а):

VAL в сообщении #1703447 писал(а):

К сожалению, не помню. Напомните, пожалуйста.

Если помнить хотя бы одно ключевое слово, найти не проблема:

VAL в сообщении #1566764 писал(а):

Да, похоже, соврал. Спасибо, за бдительность!
Впрочем, более длинным доказательство не станет:

Спасибо!

Наверняка я тогда же исправил эту ошибку. Но позже диск на сервере рухнул и сайт восстанавливали по какой-то резервной копии.

[Yadryara]

VAL в сообщении #1703580 писал(а):

Наверняка я тогда же исправил эту ошибку.

Да. Но ещё есть. Пока не буду их приводить. Мне интересно как быстро Вы найдёте 19 пятёрок до 1e19.

[DemISdx]

VAL в сообщении #1703286 писал(а):

(Идем на рекорд?)

Ответ по первому числу из рекордных

(Результат по 10285...)

NFS elapsed time = 158877.0839 seconds.
Total factoring time = 181713.4213 seconds


***factors found***
P62 = 58607655323880896767199115802857238866607560474028924814863987
P94 = 1754964608586552556722060468597401682061010946878871108280543625070563289871517584899399487613

***factorization:***
102854360885650221107443682427837181590726098865302566597414093088630571352766838563182468345201699890467357797889043949477766057034678611077378794086293031=58607655323880896767199115802857238866607560474028924814863987*1754964608586552556722060468597401682061010946878871108280543625070563289871517584899399487613

33546... пошло в работу.
А 17044... все еще на стадии ecm, на завершение которой нужно 117 часов, крепкий орешек попался...

[Dmitriy40]

DemISdx в сообщении #1703596 писал(а):

А 17044... все еще на стадии ecm, на завершение которой нужно 117 часов, крепкий орешек попался...

Если оказался/окажется свободный комп, запустите это число с дополнительным ключом -noecm - вдруг nfs отработает быстрее чем осталось ecm ... Сомнительно конечно, но насколько знаю темп роста времени для ecm и nfs разный, при этом для больших чисел nfs быстрее, и где в точности проходит граница сказать заранее трудно.

[Huz]

I have this translated as "The chances of squares, as well as the chance of 6 primes, were all less than 0.1%." That sounds messed up: 12.5% of the numbers should be of the form $2^2 x$ for some odd x.

Dmitriy40 в сообщении #1703383 писал(а):

Ради интереса проверил вероятности степеней больших (больше 100) делителей для миллиона случайных чисел в диапазоне 1e19-1.8e19. Получилось следующее:
42% вариант $pq$
28% вариант $pqr$
21% вариант $p$
7.8% вариант $pqrs$
0.9% вариант $pqrst$
Варианты с квадратами, как и вариант с 6-ю простыми, все менее 0.1%.
Варианты с кубами или с 7-ю простыми - штучно, т.е. менее 0.001%.
Варианта $p^2$, как и вариантов со степенью больше 3, вообще не встретилось.

Для 10млн случайных чисел в том же диапазоне картина качественно не изменилась, хотя появились два числа с 4-й степенью и варианты с двумя квадратами и одним-двумя-тремя простыми в первой степени (7шт, 4шт, 2шт).

[Dmitriy40]

Huz в сообщении #1703606 писал(а):

That sounds messed up: 12.5% of the numbers should be of the form $2^2 x$ for some odd x.

$2^2<100$, therefore, there remains only $x$, which means $p$, which is only taken into account. Divisors less than 100 were removed from the factorization before analysis. Because we usually put them in their places ourselves.