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

[VAL]

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

$M(184)=7$:

(Оффтоп)

1631181288692726201588541373453362702859716990031391523347571165569745384002026410080172929831511370380897830042176768779754638671869

Так не честно! Я же предупреждал
Эту цепочку у меня комп на работе ищет (возможно, уже нашел: я сегодня там не был).
Кроме этой, ни одной семерки сейчас не ищу. Только пятерки.
Кстати, вот очередная:
$M(558)=5$

(Оффтоп)

40125042392435273668755454337610162218194632066066451449035593602748302900704585044284410239067662480987100319231257102669126891335905911707171738819190444270877155181396826228145236002479372352876992785486809558752362913740735599400436587921511749334016281980214359220561571419239044189453121

[Dmitriy40]

Найденное то я у себя в файлике пометил, а вот запущенное в поиск нет ... вот и коллизия.
А 184 мне глаза мозолила, ну и запустил её поиск раз уж 272 нашлось. И кстати хватило всего 4.5млн шагов (правда под 200млн попыток), странно что у Вас за неделю не нашлось. Это был 32-й кандидат на ручную допроверку, из которых реально проверил 2/3 и из которых почти половину отбросил (остальные остались под вопросом, за несколько минут числа не разложились). А у этого кандидата недопроверенным осталось всего одно число из семи, такие проверял в первую очередь, вот и повезло.

PS. Кстати насчёт пятёрок, мне кажется не найдена с 270 делителями, хотя найдены несколько следующих ...

[VAL]

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

Найденное то я у себя в файлике пометил, а вот запущенное в поиск нет ... вот и коллизия.
А 184 мне глаза мозолила, ну и запустил её поиск раз уж 272 нашлось. И кстати хватило всего 4.5млн шагов (правда под 200млн попыток), странно что у Вас за неделю не нашлось.

Тут 3 момента.
Мне не понравилось, что программа надолго зависает на факторизации. Поэтому искусственно добавил множителей до 7 проверок на простоту, естественно понизив при этом вероятность успеха.
Эту 7-ку ищет комп на работе, который гораздо слабее моего домашнего (правда, 20-ку найдена именно на нем).
Наконец, не исключено, что он уже все нашел: я на работе 2 дня не был, а комп не в сети.

Цитата:

Это был 32-й кандидат на ручную допроверку, из которых реально проверил 2/3 и из которых почти половину отбросил (остальные остались под вопросом, за несколько минут числа не разложились). А у этого кандидата недопроверенным осталось всего одно число из семи, такие проверял в первую очередь, вот и повезло.

Да факторизация тормозит всего раз.

Цитата:

PS. Кстати насчёт пятёрок, мне кажется не найдена с 270 делителями, хотя найдены несколько следующих ...

Эта пятерка найдена лет 5 назад. Ту дело в другом. Для нее пока не доказана оценка $M(k)\le 5$.
Или я чего-то упустил в бурном потоке нашей темы?! Если так, надеюсь, Денис с Евгением меня поправят.

Найдена еще одна пятерка: $M(870)=5$

(Оффтоп)

41231627524245461835215932224946829014450017387879533293769357137967820684938594661496330387834015334540611962987148542893104734118826813905628190070795475094384058108584133732272416658207616570263810876198208935903587733116779397801127017271987442350728626026876848650409033112820573151111602783203121

С опасением ожидаю одной из следующих пятерок.
Вопрос для Антона: почему?

[Yadryara]

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

С опасением ожидаю одной из следующих пятерок.
Вопрос для Антона: почему?

А чё сразу я. Только решил чуток отдохнуть от загадок.

Предположу, что это опасение может быть связано с величиной числа. Для 870 делителей это уже 303 десятичных знака. Если речь о трудностях с факторизацией, я тоже не виноват, ибо сам-то как раз занимаюсь от силы 37-значными числами, с которыми вроде никаких проблем нет.

Есть ещё форумное ограничение в 2000 символов на пост. Ну так можно записывать числа в 16-ричной, 32-ричной и других многоричных системах счисления.

[EUgeneUS]

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

Эта пятерка найдена лет 5 назад. Ту дело в другом. Для нее пока не доказана оценка $M(k)\le 5$.
Или я чего-то упустил в бурном потоке нашей темы?! Если так, надеюсь, Денис с Евгением меня поправят.

Доказательство $M(k) \le 5$, где $k \equiv 6 \pmod{12}$ свелось к доказательству отсутствия нетривиальных решений диофантового уравнеия 4-й степени. И на этом некоторый ступор. Часть вариантов удалось отсеять, но не все. Надо бы тоже собраться и собрать в одну кучу, что имеем по этому вопросу...

По 21-ке на 48 делителей.
1. Вышел из строя вентилятор на одном из двух компов. Починить планирую до (или на) выходных.
2. Кандидаты, прошедшие две проверки (два раза 21 в логах), появляются довольно регулярно, что радует. Хотя и не в каждом круге 1e51.
3. Что не радует - на следующем круге проверки эти кадидаты "бракуются" по несовпадению чисел в первой половине цепочки. То есть вероятность попадания многих непрверяемых чисел довольно мала, и кандидатов надо будет наработать весьма много...

-- 23.06.2022, 08:05 --

Huz
Hugo, how are you doing with proof ($M(2pq) \le 3$) checking? Maybe you have some questions?

[VAL]

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

А чё сразу я. Только решил чуток отдохнуть от загадок.

(Разгадка)

$M(666)=5$
772521126221702813085956014308393171956104314363683439353636163300130944098718050347982603365978255246056022389259208492264512909550641865649075682176815044248710183364002315121657753719209369621339288665759240494483976857808469521190786604642219870605728493137898058470895584053210424057131789653014004365068856699508614838123321533203121

-- 23 июн 2022, 11:05 --

EUgeneUS в сообщении #1558236 писал(а):

Hugo, how are you doing with proof ($M(2pq) \le 3$) checking? Maybe you have some questions?

А можете мне pdf и исходник последней версии выслать?
На Papeeria меня забанили окончательно
А версия на OverLeaf (туда пока удается зайти с ноута), как я понял, старая.

[EUgeneUS]

VAL

(Оффтоп)

Ответил в е-мейле. В том числе выслал полный русский вариант pdf-ки.

[VAL]

$M(438)=5$

(Оффтоп)

64662112041748728921668112239233096820233272048929312730428926197558429752253261324237814691638666109069706739010531232918144611046870694859173703146782446306633803386543199034554075776235218989462923344453094583524102808528888286936410261286068277470171348001194161600471699780146901812465868473168893337113496942958096383741304123554041661919459219744893583946294017547607578687613558493078261116705255042317968362137675944498682521488359045658538245875641931338192962435328814405162145382168401093621704630563806499160550700366911769378930330276489257812497

$M(930)=5$

(Оффтоп)

149492003042873185509623704104306564645161595069191633275609654118591732663850229161100508596217596330862415678925764728891144364435932210392477014661372848445994249420102340809660671329214102151805069414372380799771196947476049349141456133923493610301662805415847039379743637425388122311637099605984985828399658203121

[Dmitriy40]

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

Эта пятерка найдена лет 5 назад. Ту дело в другом. Для нее пока не доказана оценка $M(k)\le 5$.

Спасибо. Я ориентировался на её отсутствие в списке в первом сообщении темы, ведь она отвечает формуле $k=12t+6$, а что не для всех доказана теоретическая максимальность как-то не соотнёс с $k=270$ ...

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

Мне не понравилось, что программа надолго зависает на факторизации. Поэтому искусственно добавил множителей до 7 проверок на простоту, естественно понизив при этом вероятность успеха.

Понимаю, так же делал и с 164 делителями, и с 172. Ни та ни другая семёрка так и не нашлись этим методом, за три недели. На шестёрках понижение вероятности было порядка нескольких раз (скажем с полчаса до тройки часов время нахождения). Семёрка вероятно будет искаться пару месяцев ... А с 5-ю проверяемыми хватит и недели, даже не факторизуя сложные случаи до конца, хватит и относительно лёгких случаев (полчаса-час на каждое трудное место, не разложившееся за минуту-две).

Ищу семёрку $k=232$, из 52-х найденных кандидатов (последняя проверка по минуте на место) легко отбрасываются 18шт (хватает пары минут проверки сотни curves на альпетроне, кстати там оказывается можно продолжать факторизацию не с начала), остальные под вопросом. Причём под вопросом даже найденная вчера шестёрка, седьмое место так и не разложилось и за 9ч.
Где бы найти готовую программу разложения методом общего решета числового поля ... Для таких длинных чисел он должен быть побыстрее ECM.

[Huz]

EUgeneUS в сообщении #1558236 писал(а):

Huz
Hugo, how are you doing with proof ($M(2pq) \le 3$) checking? Maybe you have some questions?

Sorry, I got a bit diverted, then I got distracted. I had been attempting to transcribe the proof into a terser form as I understood each part, but while the elements up to Lemma 1 are each clearly motivated by what went before, from Lemma 2 nothing has clear motivation until deep into Theorem 1 - I guess I suffered a stack overflow trying to look forward to see how they would be used.

So I need to decide where to continue from: I will probably chose to start from Theorem 1, and refer back to the Lemmas and their proofs only when I need them.

I think it can still be made clearer, but here's the "terser" version as I have it so far:

(Оффтоп)

(1) We require both $n_0$ and $n_2$ in any chain.
(2) 3 must divide either $n_0$ or $n_2$.
(3) When $x$ has values $0, 1, 2, 3, 4, 5 \pmod{6}$, $2^x$ has values $1, 2, 4, 8, 7, 5 \pmod{9}$ respectively.
(4) $n_2$ must be of one of the forms $F_1: 2v^{pq-1}$ or $F_2: 2v^{p-1}w^{q-1}$; in either case it is of the form $2B^2$, with $B \ge 3^2 \cdot 5^2$ odd.
(5) So $n_0 = n_2-2 = 2(B+1)(B-1)$ with $(B+1)/2, (B-1)/2$ coprime.
(6) $n_0$ must be of one of the following forms:
(6.1) "Great powers of 2": $F_3: 2^{2pq-1}, F_4: 2^{2p-1}t^{q-1}, F_5: 2^{2q-1}t^{p-1}$;
These are each of the form $2C^2$ which would require that $C^2, B^2$ are consecutive integers.
So $F_3, F_4, F_5$ are not possible.
(6.2) "Exotics":
(6.2.1) $F_6: 2^{pq-1}t$;
We cannot have $\{ B+1, B-1 \} = \{ 2^{pq-3}t, 2 \}$, so we must have $\{ B+1, B-1 \} = \{ 2^{pq-3}, 2t \}$ implying $t \ge 2^{21} - 1 > 3$.
Thus by (2) we have $3 \mid n_0$ and by (4) we must have $9 \mid B$. So we need $2^{pq-3} \in {1, 8} \pmod{9}$.
But by (3) that implies we need $pq-3 \in {0, 3} \pmod{6}$, and $3 \not \mid pq$.
So $F_6$ is not possible.
(6.2.2) $F_7: 2^{p-1}t^{2q-1}$ and symmetry $F_{7'}: 2^{q-1}t^{2p-1}$;
We cannot have $\{ B+1, B-1 \} = \{ 2^{p-3}t^{2q-1}, 2 \}$, so we must have $\{ B+1, B-1 \} = \{ 2^{p-3}, 2t^{2q-1} \}$ implying $t^{2q-1} = 2^{p-4} \pm 1$.
By Mihailescu's theorem, this has no solution satisfying the constraints on $p, q, t$, so $F_7$ and by symmetry $F_{7'}$ are not possible.
(6.3) "Canonical": $F_8: 2^{p-1}t^{q-1}u$ and symmetry $F_{8'}: 2^{q-1}t^{p-1}u$;
(7) So the remaining possibilities are the symmetrical $n_0 = F_8, n_2 = F_1$, or the asymmetrical $n_0 \in \{ F_8, F_{8'} \}, n_2 = F_2$.
(8) If $n_2 = F_1 = 2v^{pq-1}$, we have $B = v^{(pq-1)/2}$ and $n_0 = F_8 = 2^{p-1}t^{q-1}u$.

[EUgeneUS]

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

but while the elements up to Lemma 1 are each clearly motivated by what went before, from Lemma 2 nothing has clear motivation until deep into Theorem 1

I have arranged the lemmas prior to their use. Maybe it was wrong

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

I will probably chose to start from Theorem 1, and refer back to the Lemmas and their proofs only when I need them.

I recommend the following order
1. Lemma 1. It eliminates "exotic factorizations $n_0$" and describes the power-of-two reduction technique used in Theorem 1
2. Theorem 1
3. Lemmas 2-7 - as they are using

Now I will describe the proof scheme in Theorem 1:
1. Applying the power-of-two reduction technique leads to four cases for the auxiliary number $m$
2. Each of these leads to two cases for the equation relating $u$ and $t$, since the equation contains $\pm 1$
3. We consider them sequentially and exclude them
a) Some of them are simple
b) The case $u = 2^{p-4} t^{q-1} - 1$ is hard
c) The case $u = \frac{t^{q-1} + 1}{2^{p-4}}$ and $p = 5$ is very hard. For $p > 5$ it's very simple otherwise.

[Dmitriy40]

EUgeneUS в сообщении #1558128 писал(а):

Чем больше степень двойки в количестве делителей, тем больше "избыток" простых. Вероятно, в паттернах для ближайших цепочек на 96 делителей $p$ может просто не оказаться. Везде будут $pq$ и длиннее.

Это наблюдается уже для цепочек длиной 7 для $k=16,32,64,80,112,128,160,176,...$ и для всех $k=2^{t>3}$, однако многие из них были успешно найдены. Для снижения количества простых в первой степени есть три пути:
1) Насильно расставить по малому простому в первой степени.
2) Повысить степень малого простого примерно вдвое (точнее $x\to2(x+1)-1$), это не очень хорошо, особенно если это малое простое уже и так в большой степени.
3) Добавить ещё одно простое и заменить $pqr$ на $pq^3$, в кубе совсем не обязательно новое наибольшее простое. Для $pq$ это не сработает, а для $pqr$ вполне.
Шаг конечно вырастет, но возможно уменьшение вероятностей простых из-за этого будет нивелировано ускорением поиска за счёт лучшей фильтрации в ускорителях (или даже без них, за счёт замены факторизации на isprime). Хорошо это работает для чисел до сотни (полутора) цифр, потом урежение простых похоже пересиливает ускорение проверки (с частичной факторизацией, не полной конечно).

[VAL]

$M(690)=5$

(Оффтоп)

6074653286664987335336341101144221380194243043984647103582598507246448690593992878322126567743221369388675638319168318564673624140717459069642460543766772419598714658493441283435185674962310301149712135345575455077336443884942951453344555695056915283203121

Неожиданно долго не хотела находиться пятерка. Поиск стартовал одновременно для 690 и 930. По всем раскладам пятерка для 690 должна была найтись быстрее. Однако все вышло наоборот.

[EUgeneUS]

Dmitriy40
Можно ли Вас попросить проверить следующее
Пусть
1. $x_0 = 1$, $y_0 = 1$
2. $x_{i+1} = 5 x_i + 4 y_i$, $y_{i+1} = 6 x_i + 5 y_i$

Вопрос: являются полными квадратами числа вида $y_j$, где $j$ кратно $48$. Несколько первых, сколько получится.
Я проверил в Екселе некоторый набор модулей и всё указывает, что они могут быть полными квадратами.

[Dmitriy40]

EUgeneUS
Если и могут, то не первый миллион (и почти миллион цифр):

? x=1;y=1; for(i=1,10^6, xx=5*x+4*y; yy=6*x+5*y; x=xx; y=yy; y2=0; if(i%48==0 && issquare(y,&y2), print("x=",x,", y=",y,"=",y2,"^2")))
time = 5min, 6,340 ms.
? logint(x,10)
995590
?