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

[Huz]

@Dmitry sorry, I should have done this last time round; I've now established what would be the minimum $T(38,7)$ if the following number is a semiprime (it would be $2^{18}n - 3$), but a couple of days of ECM have not managed to factor it: 62346848882632273884297483867885246896960541009973850335963647156408538273680779146846714116120376274921

(I've also spent some more time trying to get GGNFS compiled, but as yet without success.)

Please could you have a go at factorizing this one too?

[Dmitriy40]

Huz
62346848882632273884297483867885246896960541009973850335963647156408538273680779146846714116120376274921 = 1654484805281191526877343803497511185126923 * 37683542746127536034618479737287347134502056180722301487976027
Took less one hour.

[Huz]

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

Huz
62346848882632273884297483867885246896960541009973850335963647156408538273680779146846714116120376274921 = 1654484805281191526877343803497511185126923 * 37683542746127536034618479737287347134502056180722301487976027
Took less one hour.

Super, thanks very much - another one bites the dust. :)

$T(46,7)$ is going to be rather harder though, I fear.

[Yadryara]

Как будто на машине времени прокатился. Читал статью уважаемого VAL про ММ77.
Это какого же она года? 2008-го?

Цитата:

Я пробовал обнаружить пятерки, в которых третье число имеет вид $3r^2$ либо пятое имеет вид $5u^2$. Для этого я решил диофантовы уравнения $2p^2 + 1 = 3r^2$ и $2p^2 + 3 = 5u^2$.
Множество натуральных решений первого из этих уравнений задается начальными значениями $p_0 = r_0 = 1$ и рекуррентными соотношениями
$p_{i+1} = 5p_i + 6r_i,\quad r_{i+1} = 4p_i + 5r_i$.

Хочу заметить, что здесь обозначения качественные. Разные числа, как полагается, обозначаются разными буквами.

Но у нас из-за огромного количества переменных с самого начала темы разные числа зачастую обозначаются одними и теми же буквами. И пока мы об этом помним, это не создаёт проблем.

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

$* \quad 2p^2 \quad 9p \quad 4p \quad 25p $

Здесь все $p$ — разные числа.

Есть причина продолжить именно в этих обозначениях. Итак, для 5-ки по 6 делителей VAL рассматривал такой фрагмент паттерна:

$ 2p^2 \quad 3p^2 $

Я нашёл другую рекуррентную формулу, одну и ту же для обеих $p$:

$p_{i+1} = 10p_i - p_{i-1}$

Стартовые числа $p_0 =1; p_1 = 11$ и $p_0 =1; p_1 = 9$ соответственно.

Цитата:

Множество решений второго уравнения является объединением двух серий, задаваемых одними и теми же рекуррентными соотношениями
$p_{i+1} = 19p_i + 30u_i, \quad u_{i+1} = 12p_i + 19u_i$, но с разными парами начальных значений (1, 1) и (11, 7).

А здесь VAL приводит решение в натуральных для такого фрагмента паттерна:

$ 2p^2 \quad * \quad * \quad 5p^2 $

И здесь тоже имеется другая формула для обеих $p$:

$p_{i+1} = 38p_i - p_{i-1}$

Стартовые числа $p_0 =-11; p_1 = 1 и $p_0 =7; p_1 = 1$ соответственно. Или $p_0 =-1; p_1 = 11 и $p_0 =1; p_1 = 7$.

Да, в этих бесконечных сериях решений пары именно простых $p$ почти не встречаются. Что было известно и много лет назад.

[Yadryara]

Меня могут спросить: "Антоха, а зачем ты вообще полез в эти давно изученные цепочки?"

Напомню, что я это сделал с одной стороны для того чтобы показать уважаемому gris, что задача минимизации сложна даже для столь маленьких параметров как у D(6,5).

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

Теперь осталось посмотреть про $p^5$. Смотрю ту же работу VAL :

http://www-old.fizmat.vspu.ru/doku.php?id=marathon:problem_77 писал(а):

Наконец, несложно убедиться, что искомая пятерка не может содержать пятых степеней простых чисел.
В самом деле, соседи чисел 243 и 3125 не дают искомых пятерок (хотя 243 входит в четверку). Если же $n = s^5$, то $2p^2 = (s-1)(s^4+s^3+s^2+s+1)$, что невозможно для простого s, большего 3.

А вот здесь, похоже, ошибка.

$(s-1)(s^4+s^3+s^2+s+1)=s^5-1$

Но ведь $2p^2$ в любом паттерне всегда стоит на 2-м месте, то есть в позиции $n+1$. Так что если $n = s^5$, то $2p^2 = s^5+1$, а не $s^5-1$.

У Иво и Роджера доказательство для 5-й степени более длинное.

[VAL]

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

http://www-old.fizmat.vspu.ru/doku.php?id=marathon:problem_77 писал(а):

Наконец, несложно убедиться, что искомая пятерка не может содержать пятых степеней простых чисел.
В самом деле, соседи чисел 243 и 3125 не дают искомых пятерок (хотя 243 входит в четверку). Если же $n = s^5$, то $2p^2 = (s-1)(s^4+s^3+s^2+s+1)$, что невозможно для простого s, большего 3.

А вот здесь, похоже, ошибка.

$(s-1)(s^4+s^3+s^2+s+1)=s^5-1$

Но ведь $2p^2$ в любом паттерне всегда стоит на 2-м месте, то есть в позиции $n+1$. Так что если $n = s^5$, то $2p^2 = s^5+1$, а не $s^5-1$.

У Иво и Роджера доказательство для 5-й степени более длинное.

Да, похоже, соврал. Спасибо, за бдительность!
Впрочем, более длинным доказательство не станет: $2p^2 = (s+1)(s^4-s^3+s^2-s+1)$ тоже невозможное равенство.

[Yadryara]

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

$2p^2 = (s+1)(s^4-s^3+s^2-s+1)$ тоже невозможное равенство.

Но невозможное оно уже по другой причине.

Huz, занимаетесь ли Вы сейчас 12-ю делителями? Не нужна ли Вам помощь с вычислительными мощностями... Вдруг временно освободившиеся Софокл и\или Архимед захотят Вам помочь.

[Huz]

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

Huz, занимаетесь ли Вы сейчас 12-ю делителями? Не нужна ли Вам помощь с вычислительными мощностями... Вдруг временно освободившиеся Софокл и\или Архимед захотят Вам помочь.

I'm doing various things in parallel, including trying to see how long T(6,11) would take to prove.

I'm very happy if you want to take part - you'll need access to git and a C compiler, and to have gmplib installed.

First step would be to fetch the git repository at https://github.com/hvds/seq, go to its 'divrep' directory, and read the README file there. (Or go directly to https://github.com/hvds/seq/blob/master/divrep/README to read it.)

If anything is not obvious, it is probably best to continue by email: send me some details of your operating system and C compiler, along with any problems you found. If the intent is to run it on Windows, I may need to adapt the code somewhat to cater for differences from Unix-like systems.

[Yadryara]

Huz, это я не про свои компьютеры. Это компы одного нашего общего знакомого. Так что не торопитесь радоваться. Ну и неплохо бы по времени счёта сориентироваться.

Вот сейчас Софокл и Архимед вдвоём почти 15 дней считали один комплект и нашлась только одна непрерывная 14-ка на высоте 19 тысяч е30.

[Dmitriy40]

Возможно будет проще просить Hugo самому сделать готовый exe (или elf под юникс) для запуска на конкретном компьютере (CPU & RAM & OS), чем разбираться как оно должно компилиться с git IMHO.

[Yadryara]

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

If anything is not obvious, it is probably best to continue by email:

Да, уже предложил обсудить это в квартете по email: Вы, Демис, Дмитрий и я.

[Yadryara]

Dmitriy40, поскольку Архимед сегодня заканчивает счёт в комплекте 012358 неплохо бы обновить табличку. Знаю что Вы ещё кое-где считали. Для комплекта 001234 поставил вопросительный знак, потому что в нём были найдены дополнительные цепочки и по-хорошему его надо бы пересчитать.

Попробуйте внести изменения, если посчитаете нужным.

Комплект  1/шаг  Счёт до(е30)

001234  1315609       60 ?
001235  1151329       76
001236   808201        1.6
001245   724201        1.6
001246   508369        1.6
001345   494209        1.6
001256   444889        1.6
002345   395641        1.6
001346   346921        1.6
001356   303601        1.6
002346   277729        1.6
002356   243049        1.6
001456   190969        1.6
002456   152881        1.6
003456   104329      300

012345     1369        Еnd
012346      961        Еnd 
012356      841        Еnd  
012347      783    23000
012348      712    20000
012357      685    12000
012358      623        Еnd  ?
012349      586    12000
012456      529        Еnd
012359      521
012367      481
01234A      468
012368      437
012457      431
01235A      410
012458      392
01234B      378
012369      366
013456      361        Еnd
01234C      354
01235B      331
012459      328
01235C      309
012467      302
013457      294
01234D      293
023456      289        Еnd

123456        1  100000000

[Dmitriy40]

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

Знаю что Вы ещё кое-где считали. Для комплекта 001234 поставил вопросительный знак, потому что в нём были найдены дополнительные цепочки и по-хорошему его надо бы пересчитать.

Комплект 001234 я пересчитал другим способом до 200e30. Ни 15 ни 14 не нашёл. Нашёл одну новую 13 (в том же диапазоне до 60e30), но похоже в прошлый раз её найти и не должен был. 12 много и пока не сравнивал. Так что для длинных цепочек (13 и более) оба мои результата можно считать совпадают и пересчитывать ещё раз не нужно (если не искать 12-ки и менее), хотя насколько понимаю Демис уже перепроверил это до 76e30 на Марии.
Так же до 200e30 проверен комплект 001256. Ни 15 ни 14 не найдено.

Комплекты 0123xx с xx=45,46,47,48,49,56,57,58,59,67,68,69,78,79,89 (все варианты по 9-е простое) проверены до 6e33 (прошлой 14-ки). 15-ки не найдено, 14-ки:
N2-31-327910:1966089440441196672524986345512345: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, valids=14, maxlen=14, ALL - новая минимальная 14-ка, показывал выше
S9-51-021893:3051183708749776744662169818575641: 16, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14, maxlen=14, ALL
S9-54-013829:5536971777226727622137176815138841: 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=14, maxlen=14, ALL
Комплекты 0124xx с xx=56,57,58,59,67,68,69,78,79,89 (тоже все варианты по 9-е простое) проверены до 2e33 (новой 14-ки). Ни 15, ни 14.

[Yadryara]

Dmitriy40
Поздравляю с находками! В таблицу внёс.

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

Комплект 001234 я пересчитал другим способом до 200e30.
[..]
, хотя насколько понимаю Демис уже перепроверил это до 76e30 на Марии.

Как это? Маруся обсчитала до 76e30 другой комплект: 001235. В таблице это есть.

Комплект  1/шаг  Счёт до(е30)

001234  1315609      200
001235  1151329       76
001236   808201        1.6
001245   724201        1.6
001246   508369        1.6
001345   494209        1.6
001256   444889      200
002345   395641        1.6
001346   346921        1.6
001356   303601        1.6
002346   277729        1.6
002356   243049        1.6
001456   190969        1.6
002456   152881        1.6
003456   104329      300

012345     1369        Еnd
012346      961        Еnd 
012356      841        Еnd  
012347      783    23000
012348      712    20000
012357      685    12000
012358      623        Еnd  ?
012349      596    12000
012456      529        Еnd
012359      521     6000
012367      481     6000
01234A      468      200
012368      437     6000
012457      431     2000
01235A      410       76
012458      392     2000
01234B      378      200
012369      366     6000
013456      361        Еnd
012378      356     6000
01234C      354      200
01235B      331       76
012459      328     2000
01235C      309       76
012467      302     2000
012379      298     6000
013457      294
01234D      293      200
023456      289        Еnd
012468      275     2000
012389      271     6000
012469      230     2000
012478      224     2000
012479      187     2000
012489      170     2000

123456        1  100000000

[Dmitriy40]

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

Как это? Маруся обсчитала до 76e30 другой комплект: 001235.

Да, был не прав. Последний архив с данными был про N31N37, вот и думал что она его продолжает считать, в статистике же комплект не указывается, ну не слежу ведь кто что считает.
Сейчас тогда сравню найденные 12-ки в обоих методах у себя.

-- 17.10.2022, 11:25 --

Что-то разница лишь возросла: из 263 цепочек ALL длиной (maxlen) 12 в комплекте N31N37 в комплекте 001234 не найдены 148, и почти все они ALL. С другой стороны до 60e30 в комплекте 001234 найдены 27 цепочек длиной 12, в том числе три ALL, которых нет в комплекте N31N37.
Либо я как-то не так сравниваю, либо причина в разных if-ах (хотя они и не должны влиять на ALL цепочки), либо методы поиска совсем разные и не должны находить строго одинаковые цепочки (тем более заметно короче номинальных), либо где-то у меня очень неприятная ошибка.
Сравню ещё раз 13-ки.
И вообще буду думать что за фигня.