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

[Dmitriy40]

gris в сообщении #1727937 писал(а):

Может ли в четверку попасть простое число или удвоенное простое?

Нет, простое может встретиться только в двойках. Потому что общее число должно быть кратно всем наибольшим простым делителям, а если число простое, то оно же является и своим наибольшим простым делителем и значит сумма его с делителем будет удвоенным простым. Т.е. общее число должно быть удвоенным простым. А значит оно имеет делителями только простое и двойку. Т.е. это лишь двойка и не длиннее. И все такие числа имеют вид $2^k+2$, при этом $2^{k-1}+1$ должно быть простым. Т.е. подходят все простые числа $2^k+1$.
Чтобы решение стало тройкой нужен ещё один простой делитель общего числа, а тогда оно не будет удвоенным простым и соответственно не будет иметь одним из вариантов разложения сумму простого с наибольшим простым делителем.

gris в сообщении #1727937 писал(а):

интересно, а какие диаметры у решений как векторов чисел (к которым добавляется максимальный делитель)?

Не понимаю.

[gris]

Вот например четвёрка:
$10846541063=43\cdot 239\cdot 263\cdot 4013 : [10846537050, 10846540800, 10846540824, 10846541020 ]$
Факторизация всех элементов четвёрки:
$10846537050 [2, 1; 3, 1; 5, 2; 37, 1; 487, 1; 4013, 1]$
$10846540800 [2, 10; 3, 2; 5, 2; 179, 1; 263, 1]$
$10846540824 [2, 3; 3, 1; 7, 3; 37, 1; 149, 1; 239, 1]$
$10846541020 [2, 2; 5, 1; 7, 2; 19, 2; 23, 1; 31, 1; 43, 1]$
Расстояние от первого до последнего элемента вектора
$10846541020-10846537050 = 3970$
Для известных четвёрок каково максимальное расстояние ака диаметр? Как оно зависит от диапазона для суммы? Это я про потерю решений. Попробую на досуге собрать статистику.

[Dmitriy40]

gris в сообщении #1727950 писал(а):

Расстояние от первого до последнего элемента вектора
$10846541020-10846537050 = 3970$

Очевидно оно легко получается из разложения общего числа (если оно без лишних простых делителей! у меня все четвёрки такие):

gris в сообщении #1727950 писал(а):

$10846541063=43\cdot 239\cdot 263\cdot 4013$

$4013-43=3970$
Код для вычисления по такому общему числу: f=factor(x); f[-1..-1,1][1]-f[1,1].
Код для вычисления по любому общему числу:

? x=3083369158; a=oo; b=0; foreach(factor(x)[,1],p, if(factor(x-p)[-1..-1,1]==p, a=min(a,p); b=max(b,p); ); ); b-a
%1 = 530

$530=613-83$

gris в сообщении #1727950 писал(а):

Для известных четвёрок каково максимальное расстояние ака диаметр?

Для найденных мною почти 35000шт минимальный диаметр 60, максимальный 4176, оба встретились лишь однажды.
Диаметры 70 и 4160 встретились по два раза.
Диаметры 180 и 4080 встретились по 4 раза.
Больше всего, 86 раз, встретился диаметр 2520.
Реже, 81 раз, встретился диаметр 2640.


На удивление среди почти 35000 четвёрок нет ни одной с простым делителем 11. 7 и 13+ есть, 11 нет.

[worm2]

Я тут подумал о теории.
Есть такая функция Дикмана $\rho(u)$. Она показывает асимптотическую плотность чисел, чьи простые множители не превышают $B$ ($B \to \infty$), среди всех чисел от 1 до $B^u$. То есть если мы возьмём четыре простых числа $p_i$ одного порядка $M$ (для простоты пусть $M$ немного поменьше любого из $p_i$), то каждое из "произведений" $p_1p_2p_3-1, p_1p_2p_4-1, p_1p_3p_4-1, p_2p_3p_4-1$ будет иметь порядок $M^3$. Вероятность, что одно из этих "произведений" не будет иметь простой множитель, больший $M$, примерно равна $\rho(3) \approx 0.0486$. Вероятность, что одновременно все четыре "произведения" не будут иметь простого множителя, превышающего $M$, оценивается в $\rho(3)^4 \approx 5.6 \cdot 10^{-6}$. То есть примерно каждая из 180 тысяч случайно выбранных четвёрок простых чисел (одного порядка) даст положительный результат по этой задаче. Кажется, это согласуется с вычислительным экспериментом?
Если эти рассуждения верны, то вероятность найти пятёрку простых чисел с нужным свойством оценивается в $\rho(4)^5 \approx 2.9 \cdot 10^{-12}$. То есть нужно в среднем перебрать какие-то жалкие 350 миллиардов пятёрок простых чисел, чтобы наткнуться на подходящую.

[Dmitriy40]

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

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

В принципе подъёмно, хотя и грустно: у меня PARI при выбранных условиях перебирает 65000 пятёрок в секунду, значит хватит типа 2 месяца в один поток.

[gris]

А вот плодотворная идея: что если к числу прибавлять его не наибольший, а наименьший простой делитель?
В программку всего пара изменений, зато какой результат!
Любой размер по вашему выбору. Например,
510510 [2,3,5,7,11,13,17] : [510493 510497 510499 510503 510505 510507 510508 ]
Да и программка не нужна. Жаль, что решение очевидно и не представляет исследовательского интереса:(
Это была шутка такая.

[worm2]

Идея: факторизацию не обязательно доводить до конца. Например, у нас пятёрка чисел $p_1, p_2, p_3, p_4, p_5$ и мы факторизуем $M = p_1p_3p_4p_5-1$. Нам достаточно проверить делимость на простые, не превосходящие $p_2$, что гораздо меньше, чем $\sqrt{M}$. Ну, это если для простейшего метода. Что там с продвинутыми, всякими решетами числовых полей, я не знаю (P.S. Искусственный интеллект утверждает, что для методов типа решета числового поля не прокатит).

[Dmitriy40]

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

факторизацию не обязательно доводить до конца.

Обязательно: нам надо убедиться что нет простых делителей больше.
Только мне кажется Вы чуть спутали факторизацию и проверку простоты, это вторую надо доводить до корня из числа, а первая для составных чисел свалится к 1 (т.е. завершится) задолго до корня.

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

Нам достаточно проверить делимость на простые, не превосходящие $p_2$, что гораздо меньше, чем $\sqrt{M}$. Ну, это если для простейшего метода.

До корня факторизация и не пойдёт, это ж только для простых чисел, а так до полного разложения и всё.
Вопрос проверки на простоту - несколько другой, да, для чисел до миллиардов быстрее проверка делением (на несколько тысяч простых), а вот для бОльших чисел быстрее уже нормальный тест (типа BPSW как в PARI).

У меня сейчас кстати так и сделано, факторизация выполняется пробным делением на простые до проверяемого делителя. Пока все простые в разложении невелики (не более десятков тысяч) это в среднем быстрее.

[lel0lel]

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

Обязательно: нам надо убедиться что нет простых делителей больше.

Если вы убедитесь, что все простые делители меньше данного предела, то это будет означать, что больших простых нет. Можно отцеплять маленькие простые с учётом кратности, если по итогу осталась единица, то проверка пройдена, иначе -- нет. Можно, конечно, по-разному это реализовать. Выглядит разумным через GCD (если граница не слишком большая). Полагаю, что worm2 говорит об этом.

[waxtep]

В диапазоне $[2;1000]$ изрядно подходящих троек $p_1<p_2<p_3$, где $[p_2,p_3]$ - тоже подходящая двойка (далее слово "подходящая" опускаю). В этом же диапазоне есть девять четверок, где $[p_2,p_3,p_4]$ - тройка, и $[p_3,p_4]$ - двойка; если нигде не ошибся, вот они все:

1. [151, 641, 673, 947] 
2. [83, 373, 757, 911] 
3. [631, 683, 797, 839] 
4. [31, 373, 571, 787] 
5. [509, 523, 587, 751] 
6. [229, 571, 709, 739] 
7. [283, 331, 571, 601] 
8. [113, 239, 271, 479] 
9. [149, 197, 233, 389] 

Почему бы в диапазоне $[2;20000]$ не быть хотя бы одной пятерке, где старшие четверка, тройка, двойка тоже хороши? Компьютер похоже будет искать ответ на этот вопрос трое суток

[waxtep]

Вообще, прогноз так себе: в диапазоне $[2,2000]$ четверок с таким свойством дофигищи, и идут они очень плотно (есть для практически каждого $p_4$):

1. [41, 383, 863, 1999] 
2. [1031, 1733, 1753, 1997] 
3. [557, 1033, 1301, 1997] 
4. [251, 937, 1193, 1997] 
5. [223, 1009, 1723, 1987] 
6. [127, 1693, 1741, 1951] 
7. [293, 607, 1459, 1951] 
8. [379, 691, 1709, 1949] 
9. ... 

а для пятерки я уже спустился от $19997$ к $17401$, на $261$ ступеньку, и пока ничего. Или выше забираться, или это вообще не так работает