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

[gipokrat]

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

б) Существует ли 5 таких чисел?

[worm2]

a) Понятно, что "один и тот же результат" нужно в первую очередь искать в виде $p_1 \cdot p_2 \cdot p_3 \cdot p_4$, где $p_i$ — различные простые числа.
Хотя подошло бы и $p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot q$, где $q$ — произвольное натуральное, но перебирать четвёрки чисел быстрее, чем пятёрки.
Руками такое найти совершенно нереально (у меня даже для трёх не получилось, хотя там сильно далеко ходить не надо). Компьютер с некоторым трудом нашёл, например: $19 \cdot 67 \cdot 103 \cdot 349$.

[Dmitriy40]

Единственное меньшее (и оно же наименьшее) решение с 4 числами: $7\cdot53\cdot131\cdot223=10838023$.
Хватило минуты компьютерного перебора. И 4 минуты до второго показанного выше.

-- добавлено через 36 минут --

Следующие значения: 83253767, 88068811, 130069097.

-- добавлено через 42 минуты --

Ещё несколько значений (не все): 174004531, 174309757, 264710257, 279752017, 506992139, 702187379, 827337157, 848000053, 903577979, 935041579, 936973537, 995507987.

[gipokrat]

worm2
Спасибо! Очень интересная идея — искать общий результат в виде произведения различных простых чисел. Я до такого способа организации перебора не додумался.

А для пункта б) Вы не пробовали аналогичный перебор по пяти простым? Интересно, пятёрка просто находится очень далеко или здесь возникает какое-то принципиальное препятствие?

-- добавлено через 1 минуту --

Dmitriy40
Большое спасибо! Очень приятно, что найденное значение (10838023) оказалось не только подходящим, но и наименьшим.

А не попадалось ли при переборе значение, которому соответствуют сразу пять чисел? И до какой границы Вы успели проверить пункт б)?

[Dmitriy40]

gipokrat в сообщении #1727840 писал(а):

И до какой границы Вы успели проверить пункт б)?

gipokrat в сообщении #1727840 писал(а):

пятёрка просто находится очень далеко

Во всяком случае никакое произведение 5 простых меньших 1000 пятёрку не даёт.
И до 130млн пятёрки тоже точно нет, независимо от разложения на простые.

-- добавлено через 15 минут --

gipokrat в сообщении #1727840 писал(а):

или здесь возникает какое-то принципиальное препятствие?

Да нет никакого препятствия, но Вы же видите как растут числа: 4, 6, 130, 10838023.

[waxtep]

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

Руками такое найти совершенно нереально (у меня даже для трёх не получилось, хотя там сильно далеко ходить не надо)

Кажется, если отойти чуть подальше, становится легче, для трех, по крайней мере, легко находится руками (ну конечно для скорости вооруженными калькулятором и раскладывателем на простые) $101\cdot109\cdot131$

[Dmitriy40]

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

Да нет никакого препятствия,

Что-то уже не уверен: почему-то среди 5000+ четвёрок нет ни одной чётной или оканчивающейся на 5. Хотя тройки такие были. Так что и для пятёрок может неожиданно проявиться какой-то запрет ...

[waxtep]

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

Во всяком случае никакое произведение 5 простых меньших 1000 пятёрку не даёт.
И до 130млн пятёрки тоже точно нет, независимо от разложения на простые.

У меня такая гипотеза теплится (пока не проверил): "легко находимая" $n$-ка с $p_n-p_1\ll p_n$ лежит в области $p_1>B^{n-1}$. Если экстраполировать по одной точке для легко находимой тройки $B=10$, то результат для пятерки следует искать как произведение пяти простых, меньшее из которых превышает $10^4$, т.е. в районе $10^{20}$. Это конечно может быть и ерундой/совпадением, попробую на досуге

[Dmitriy40]

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

то результат для пятерки следует искать как произведение пяти простых, меньшее из которых превышает $10^4$, т.е. в районе $10^{20}$.

Да, посмотрев как активно сыпятся четвёрки, причём не с малыми простыми, а чаще с большими (почти каждая комбинация двух наибольших простых даёт решение), тоже подумал и запустил поиск пятёрки с наибольшим простым около 9000, пара часов ничего не дало, перезапустил с наибольшими четырьмя простыми из пяти начиная с 99000, 49000, 25000, 13000, пятое с 2. Пока тоже глухо.
Тотально были проверены все произведения пяти простых до 1200 каждое.

[waxtep]

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

Пока тоже глухо.

Да, тоже взял в руки шашки, и тоже пока глухо. Для пятерок уже факторизация похоже медленно работает, ну и на один вложенный цикл больше. Заодно посмотрел на "легко находимые" четверки (с минимальным наименьшим числом, далее с минимальным третьим по величине числом и т.д.), эти-то быстро считаются, и картинка, кажется, выглядит сложнее, чем я предположил:
- в диапазоне $[100;500]: [193, 251, 269, 359]$
- в диапазоне $[1000;1500]: [1009, 1091, 1109, 1499]$ (глаз-алмаз)
- в диапазоне $[10000;15000]: [10007, 10009, 12043, 12539]$
Не так уж "легко находимы" четверки, довольно много простых пропускается. Хотя конечно это не показательно, я же не все подряд смотрю, а только "самую младшую" для диапазона

-- добавлено через 11 минут --

Вообще, глядя на четверки с большим $p_1$ (считаю $p_1<p_2<\ldots$), дофига четверок с очень близкими $p_1,p_2,p_3$ и отдельно стоящим $p_4$, типа $[50021, 50023, 50129, 56039], [100003, 100019, 100043, 108649]$

[gris]

чисто насчёт чётных четвёрок. Вот примеры:
2820783278 [2,53,181,233,631] : [2820782647 2820783045 2820783097 2820783225 ]
3083369158 [2,83,157,193,613] : [3083368545 3083368965 3083369001 3083369075 ]
Или я опять заблудился? :(

[Dmitriy40]

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

чисто насчёт чётных четвёрок. Вот примеры:

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

[gris]

Спасибо. У меня только получилось наспех написать примитивный код на PARI и попробовать несколько пятимиллионных интервалов. Считаю вектор сумм, сортирую, нахожу куски одинаковых сумм и возвращаю числа. Об эффективности и не говорю. В теорию пока не вдавался.
M=12 000 000 000; N=M+5 000000;
v=vector(N-M+1);
for(n=M,N,
d=factor(n);
v[n-M+1]=n+d[matsize(d)[1],1];
);
vs=vecsort(v); ...

[Dmitriy40]

Можно чуть упростить код:
vs=vecsort(vector(5000000,i, M+i+factor(M+i)[-1..-1,1][1]))
Но быстрее не станет.
При этом Вы теряете решения, разложение которых попадает в разные интервалы (с разным M).

-- добавлено через 5 минут --

Для проверки решения x можно использовать код:
n=0; foreach(factor(x)[,1],p, if(factor(x-p)[-1..-1,1]==p, n++); ); n
Покажет количество разложений (длину решения).

[gris]

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