Числа с одинаковой суммой с наибольшим простым делителем

[worm2]

waxtep в сообщении #1728646 писал(а):

worm2, поздравляю, класс! Все таки Разум в очередной раз победил коварство Природы четыре старших и отдельно стоящий младший член пятерки, логичная же конструкция.

Спасибо!

Цитата:

А интересно, оценка вероятности похожа на ту, что Вы приводили выше или отличается заметно?

worm2 в сообщении #1727968 писал(а):

Если эти рассуждения верны, то вероятность найти пятёрку простых чисел с нужным свойством оценивается в $\rho(4)^5 \approx 2.9 \cdot 10^{-12}$. То есть нужно в среднем перебрать какие-то жалкие 350 миллиардов пятёрок простых чисел, чтобы наткнуться на подходящую.

Вот это имею в виду

Первый этап, перебор четвёрок простых чисел, оценивается легко: около 900 простых чисел, примерно $900^4/4! \approx 27\cdot 10^9$ вариантов.
Второй этап сложнее оценить, я не вёл учёт, сколько для каждой четвёрки пришлось перебирать $p_1$. Если судить по времени работы, то он занял в 2 раза больше времени. Если бы каждая пятёрка проверялась столько же времени, что и четвёрка на первом этапе, то получается нелогичный результат, что я для каждой четвёрки перебрал в среднем $27\cdot 10^9\cdot 2/(16.8\cdot 10^6) \approx 3400$ простых чисел, а там их где-то на порядок меньше. Пятёрка проверялась дольше, потому что планка максимального делителя для второго этапа минимум в два раза выше, кроме того, в среднем проверялось более одного числа, ведь 10% проходили первую проверку. Это не делает очевидным такой большой разрыв в скорости, но если всё-таки отталкиваться от (субъективной) оценки в 340 простых на каждую пятёрку в среднем, то получается, что на втором этапе около 5 миллиардов пятёрок было проверено. Всего получается 27 млрд. четвёрок + 5 млрд. пятёрок = 32 млрд операций разложения на небольшие простые (с ранним выходом, если обнаружено, что существует множитель, больший порога). Если бы по-честному перебирались все пятёрки, их вышло бы $900^5/5! \approx 5\cdot 10^{12}$. Для такого количества, исходя из моей оценки через функцию Дикмана, нашлось бы как раз в среднем 14 пятёрок. Но тут нужно учитывать два момента:
1) Моя оценка делалась в предположении, что все простые одинакового порядка, а тут это не так. По-хорошему, тут от произведений функции Дикмана нужно брать многомерный интеграл по области $p_1<p_2<p_3<p_4<p_5<7000$, что для меня как-то сложно. Вероятно, получится оценка вероятности выше, может быть, даже на порядок.
2) На первом этапе я отсёк числа с максимальными простыми делителями, меньшими $p_2$, но большими $p_2/2$. Кто знает, сколько пятёрок при этом остались неоценёнными? Возможно, их нашлось бы больше на порядок (но время расчёта увеличилось бы сильно больше, чем на порядок).
1) и 2) как будто взаимно компенсируют друг друга. То есть, резюмируя, нельзя утверждать, что результаты численного эксперимента сильно расходятся с предсказаниями вероятностной теории. Вообще, по ощущениям, в таких задачах вероятностный подход хорошо работает, простые числа часто "ведут себя" как случайные величины.

[waxtep]

worm2, спасибо! Что же, пора ставить ребром вопрос о шестерке? у меня, правда, и пятёрки считаются довольно долго: воспроизвел Ваш алгоритм в лоб на pari/gp, пять вложенных циклов с фильтрацией в четвёртом. Хочется каких-то магических условий отсечения во внешних циклах, но их не видно

[worm2]

waxtep в сообщении #1728678 писал(а):

пора ставить ребром вопрос о шестерке? у меня, правда, и пятёрки считаются довольно долго: воспроизвел Ваш алгоритм в лоб на pari/gp, пять вложенных циклов с фильтрацией в четвёртом.

Я пас
У меня 64-битное нативное деление (на Delphi писал), а для шестёрки 64 бит уже не хватит, нужна длинная арифметика, что выглядит совсем уж безнадёжно.