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

[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$ ступеньку, и пока ничего. Или выше забираться, или это вообще не так работает

[waxtep]

Задумался над попыткой аналитического штурма задачи по поиску пятерки. Пока на кошечках, для тройки: возьмем три простых числа $p_1=p,p_2=f(p),p_3=f(f(p))$, где $f(x)=x^2-3x+3$. В этом варианте у нас сразу "в кармане" $p_1p_2-1=(p-1)^3$ и $p_2p_3-1=(p-1)^3\cdot(p-2)^3$, и остается разобраться только с бегемотом

$$p_1p_3-1=(p-1)\cdot(p^4-5p^3+7p^2-2p+1)$$

Второй множитель чуть больше $p_2^2$, и тут уже видимо как повезет. Такие тройки действительно существуют, и обе младших (по величине $p_1$) являются подходящими: $[29,757,570781],[79,6007,36066031]$. При этом $f(36066031)=1300758483894871$ - тоже простое, но $[6007,36066031,f(36066031)]$ подходящей тройкой не является, чуть-чуть не везет с $p_1p_3-1$.
Для пятерки... в таком виде это скорее курьез, но, может быть можно более аккуратно подобрать функцию (или набор функций).

[worm2]

waxtep, о, я тоже в эту сторону копал:
Если $A = 2x^2+2x+1$, $B = 2x^2-2x+1$, то $AB-1 = 4x^4$.
Если вдруг при этом окажется, что каждое из чисел $A$ и $B$ раскладывается в произведение двух простых чисел (как оказалось, это не редкость), желательно, не сильно отличающихся по порядку (с этим уже похуже), то у нас получается четвёрка простых чисел, произведение которых, уменьшенное на 1, не имеет больших простых делителей, а может быть даже, все его простые делители гораздо меньше, чем каждое из этой четвёрки. Перебор $x$ действительно даёт несколько "хороших" четвёрок, однако их катастрофически мало, чтобы "набрать статистику" и тупо массой задавить оставшиеся неравенства.
Однако меня воодушевил тот факт, что взяв на пробу первую попавшуюся такую четвёрку (не сохранилась), я сразу для неё обнаружил такое пятое простое, которое (случайно или закономерно?) даёт сразу два подходящих разложения. То есть всего получается три из необходимых пяти, осталось чуть-чуть!
Удалось обобщить это на трёхпараметрическое семейство: $A = n(n-k)x^2+nx+1$, $B = nkx^2-nx+1$, $AB-1 = n^2x^3(k(n-k)x+2k-n)$. Тут нужно, чтобы нам дополнительно повезло, и сомножитель $k(n-k)x+2k-n$ имел малые простые делители. Четвёрок по такой схеме нашлось ощутимо больше, но всё равно слишком мало. Четырёхпараметрическое семейство не осилил.

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

я в сообщении #1728540 писал(а):

первую попавшуюся такую четвёрку (не сохранилась)

Восстановил. $x=4100$, $A = 2x^2+2x+1=5113\cdot 6577$, $B = 2x^2-2x+1=4801\cdot 7001$. $AB-1=4\cdot 4100^4$ имеет максимальный простой делитель 41. Перебирая простые от 41 до 4801, обнаруживаем целых два "дважды подходящих": 131 и 193:
$131\cdot 6577\cdot 4801\cdot 7001-1=2\cdot 3\cdot 7\cdot 19\cdot 61\cdot 283\cdot 757\cdot 2777$,
$131\cdot 5113\cdot 4801\cdot 7001-1=2\cdot 3\cdot 23\cdot 61\cdot 103\cdot 4703\cdot 5521$,
$193\cdot 6577\cdot 4801\cdot 7001-1=2^3\cdot 5\cdot 41\cdot 1361\cdot 4283\cdot 4463$,
$193\cdot 5113\cdot 6577\cdot 7001-1=2^9\cdot 37\cdot 239\cdot 2269\cdot 4423$.

[worm2]

Откатился к тупому перебору. Но с идеей, что нужно сначала искать четвёрку самых больших чисел $p_2 < p_3 < p_4 < p_5$, таких, что максимальный простой делитель $p_2p_3p_4p_5-1$ был бы по возможности намного меньше $p_2$, тем самым оставляя больше пространства для поиска $p_1$.

Сначала искал в диапазоне $p_5 < 5000$ с критерием "подходящей" четвёрки: максимальный множитель меньше, чем $p_2/10$.
По таким критериям нашлось 123 тыс. подходящих четвёрок. На втором этапе получилось 18 тыс. "дважды подходящих" пятёрок, 111 "трижды подходящих" и 0 "четырежды подходящих" (искомых). Не прокатило. Но было ощущение, что не хватает совсем немного.

Расширил диапазон до $p_5 < 7000$ и ослабил критерий: максимальный множитель $p_2p_3p_4p_5-1$ должен быть меньше, чем $p_2/2$.
Нашлось 16.8 млн четвёрок. Из них получилось 1.6 млн (т.е. с вероятностью 10%) "дважды подходящих", 8618 (одна из 187) "трижды подходящих" и, наконец, 16 (одна из 539) искомых пятёрок:

$$ \begin{array}{rrrrrrrrrrr} 383&\times& 761&\times&1601&\times&4451&\times&5927 &=& 12310261660887251\\ 1429&\times&1447&\times&2459&\times&3271&\times&4523 &=& 75225731669514061\\ 509&\times&1801&\times&3109&\times&4259&\times&6871 &=& 83402641525340509\\ 691&\times&3001&\times&3229&\times&3659&\times&4271 &=& 104641527044365771\\ 277&\times&2213&\times&5167&\times&6361&\times&6911 &=& 139240615085961457\\ 877&\times&1877&\times&3469&\times&4021&\times&6637 &=& 152396171426092877\\ 827&\times&2081&\times&3187&\times&4517&\times&6529 &=& 161754515214664517\\ 929&\times&2879&\times&4073&\times&4079&\times&4789 &=& 212799366783988333\\ 2069&\times&2753&\times&2861&\times&4877&\times&5813 &=& 461995386194082977\\ 2293&\times&2741&\times&3229&\times&4909&\times&4973 &=& 495441779203177789\\ 2377&\times&2797&\times&3191&\times&4519&\times&5813 &=& 557302660816728313\\ 769&\times&4639&\times&6089&\times&6199&\times&6203 &=& 835256961331136203\\ 2459&\times&3989&\times&4019&\times&4363&\times&4987 &=& 857758741024215389\\ 2351&\times&3851&\times&4831&\times&5749&\times&5779 &=& 1453142445108722101\\ 2269&\times&3769&\times&5521&\times&5653&\times&6733 &=& 1797074080798594069\\ 2027&\times&4871&\times&5099&\times&5903&\times&6101 &=& 1813137325520388149\\ \end{array} $$

[waxtep]

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

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

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

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