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

[Huz]

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

И вновь нужна оценка сверху.

I find only $M(300) \le 29$.

[VAL]

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

I find only $M(300) \le 29$

Thanks!

[mathematician123]

Мне кажется, я близок к доказательству $M(60) \le 17$. Но пока не получается до конца довести.

Предположим, что существует цепочка из 18 чисел. Тогда числа $n_6, n_7, n_8, n_9, n_{10} $ входят в эту цепочку. Как и в случае $k = 84$, можно получить, что $n_8 = 8x^2$, $2x = z^2+1$, $3 \mid n_6$.

Предположим, что $n_0$ входит в цепочку. Тогда из $n_0 = 8x^2-8$ получаем, что $64 \cdot 3 \mid n_0$. Если $n_0$ имеет 4 различных простых делителя, то $n_0 = p_1 p_2 p_3^2 p_4^4$, что противоречит делимости на 64. Если $n_0$ имеет 3 или меньше простых делителей, то можно применить ту же технику, что и в случае $k = 84$.

Таким образом, $n_0$ не входит в цепочку. Тогда в цепочку обязаны входить все числа от $n_6$ до $n_{18} $. Из $n_8 = 2(z^2+1)^2$ следует, что $5 \mid n_6 n_8 n_{10}$. Если $5 \mid n_6$, то $n_6$ помимо 2, 3 и 5 имеет максимум один простой делитель. Тогда, используя $n_6 = 2z^2(z^2+2)$ этот случай сводится к конечному перебору. Если $5 \mid n_8$, то $25 \mid n_8$. Тогда $n_{18} = 10y^2$ и получаем неразрешимое сравнение $10y^2 \equiv 18 \pmod{32}$. Заметим также, что $9 \mid n_{18}$, так как в противном случае $n_{18} = 6y^2$ и получается неразрешимое сравнение $6y^2 \equiv 18 \pmod{32}$.

Таким образом, $5 \mid n_{10} $. Тогда $n_{10} = 10y^2$ или $n_{15} = 15y^2$. Учитывая $n_8 = 8x^2$, получаем уравнение Пелля. Дальше пока не получается.

[Huz]

mathematician123 в сообщении #1560826 писал(а):

Мне кажется, я близок к доказательству $M(60) \le 17$. Но пока не получается до конца довести.

Предположим, что существует цепочка из 18 чисел. Тогда числа $n_6, n_7, n_8, n_9, n_{10} $ входят в эту цепочку. Как и в случае $k = 84$, можно получить, что $n_8 = 8x^2$, $2x = z^2+1$, $3 \mid n_6$.

I think your proof of $3 \mid n_6$ relies on $n_2$ being in the chain, and that for $2x=z^2+1$ relies on $n_0$ being so, at least in the $M(84)$ proof you kindly translated for me.

[mathematician123]

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

I think your proof of $3 \mid n_6$ relies on $n_2$ being in the chain, and that for $2x=z^2+1$ relies on $n_0$ being so, at least in the $M(84)$ proof you kindly translated for me.

I forgot to mention this. We only need $n_6$ and $n_8$ in the chain to prove $2x = z^2+1$. $\tau(n_6) \equiv \tau(n_8) \equiv 4 \pmod{8}$ implies $n_8 = 8x^2$ and $n_6 = 2py^2$. Then $py^2 = (2x+1)(2x-1)$.

Since $z^2+1$ cannot be divisible by 3, it also implies $3 \mid n_6$

[EUgeneUS]

mathematician123 в сообщении #1560842 писал(а):

Then $py^2 = (2x+1)(2x-1)$.

Я не очень разобрался, как исключился случай $2x = z^2-1$.
Если выше всё верно, то тут

mathematician123 в сообщении #1560826 писал(а):

Тогда $n_{10} = 10y^2$ или $n_{15} = 15y^2$. Учитывая $n_8 = 8x^2$, получаем уравнение Пелля. Дальше пока не получается.

легко повысить степень уравнения (степень одной переменной из двух), подстановкой $2x = z^2+1$
Тогда, например, WolframAlpha находит бесконечную серию решений Пелль-подобных уравнений, а после повышения степени находит только тривиальные решения с единицами.

[Huz]

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

Я не очень разобрался, как исключился случай $2x = z^2-1$.

We have $x$ odd, so this case would imply $z^2 \equiv 3 \pmod{4}$.

[mathematician123]

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

Я не очень разобрался, как исключился случай $2x = z^2-1$.
Если выше всё верно, то тут

Этот случай невозможен по модулю 4, так как $x$ нечётное.

mathematician123 в сообщении #1560826 писал(а):

Таким образом, $5 \mid n_{10} $. Тогда $n_{10} = 10y^2$ или $n_{15} = 15y^2$. Учитывая $n_8 = 8x^2$, получаем уравнение Пелля. Дальше пока не получается.

Ещё кое-что удалось обнаружить. Если $25 \mid n_{10}$, то $n_{15} = 15y^2 \equiv 5 \pmod{25}$, что невозможно. Если $25 \mid n_{15}$, то $n_{10} = 10y^2 \equiv 20 \pmod{25}$, что невозможно. Тогда получается, что $n_{10} = 10y_1^2$ и $n_{15} = 15 y_2^2$.

[Huz]

mathematician123 в сообщении #1560842 писал(а):

I forgot to mention this. We only need $n_6$ and $n_8$ in the chain to prove $2x = z^2+1$. $\tau(n_6) \equiv \tau(n_8) \equiv 4 \pmod{8}$ implies $n_8 = 8x^2$ and $n_6 = 2py^2$. Then $py^2 = (2x+1)(2x-1)$.

Since $z^2+1$ cannot be divisible by 3, it also implies $3 \mid n_6$

Ah good, makes more sense now. Time to read the next paragraph. :)

(I note also that none of the $n_0$ factorizations can supply both $w$ and $w+1$ factors, so $n_0$ can be ruled out without needing any trials.)

(Later) the rest looks good to me too, so as I understand it we now have $M(60) \ge 18$ forcing that $n_8/8, n_{10}/10, n_{15}/15$ are all odd squares with 15 factors.

[mathematician123]

Из $n_6 = n_{15} - 9 = 15y_2^2 - 9$ следует, что $n_6 = 6y_3^2$. Тогда $n_6 = 6y_3^2, n_8 = 8x^2, n_{10} = 10y_1^2, n_{15} = 15y_2^2$.

[Dmitriy40]

С такими ограничениями вольфрамальфа не находит решений уже даже для трёх переменных кроме тривиального с единицами.
Есть ли они вообще? И если нет, стоит ли развивать дальше эту ветвь с кучей (больше двух во всей цепочке) квадратов?

[Dmitriy40]

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

Что дальше-то делать, если ещё одна непрерывная 14-ка найдётся существенно ниже...

Если Вы боретесь за каждый процент скорости, то проведите тест какой именно вариант разворачивания цикла будет быстрее именно на вашем компьютере. Я конечно уже просил Вас это сделать и даже были результаты, но их мало, да и не помню, включали ли те тесты проверку по индексам. Вполне вероятно что вариант с 4096 простыми и разворачиванием bb=[5,37] (для примера, точную информацию можно взять в конце .inc файла в строке "Decycle: 2 3 5 37 - repeats=1110") не оптимальный по скорости для вашего компа.
Конкретно, надо менять массив bb[] и параметр pr_max и смотреть какой вариант будет быстрее, либо на одном паттерне, либо, что лучше, на некотором подмножестве всех 46080 паттернов, лучше из всех групп, например по маске M12-??-??-?125??.exe, это 1/120 часть всех паттернов, 384шт, или тупо оставить в M12mods1.patterns по паре любых (лучше даже везде разных) паттернов от каждой группы. Разумеется всё это лучше делать в отдельной папке чтобы не испортить основной процесс.

Hints по заполнению массива bb[]:
1. Желательно заполнять не теми простыми, которые можно проверить по индексу (т.е. те что и так используются), проверка по индексу намного быстрее обычной, а разворачиваемые простые вообще не проверяются, они исключаются на этапе компиляции при разворачивании цикла.
2. Желательно чтобы коэффициент разворачивания (он показывается после запуска Yadryara5.gen.gp в Blocks=1110/104=10.673x) был побольше, чем он больше, тем по идее быстрее счёт. Для каждого простого его показ в файле Yadryara5.gen.gp закомментирован в 16-й строке (начинается с printf("%2d:", m);), но можно вычислить самому: для использованных простых $p_i$ (кроме $p_i=3$) он равен $p_i/(p_i-1)$, для прочих равен $p_i/(p_i-11)$ (11 - количество проверяемых мест). Для всех разворачиваемых простых коэффициенты перемножаются. Простые 2 и 3 разворачиваются всегда (потому что там всего один допустимый вариант в каждом), их в bb[] можно не указывать (но и указание ничему не помешает).
3. Желательно чтобы второе число в нём было больше сотни или двух, тоже чем больше, тем быстрее.
4. При этом надо смотреть за размером используемой памяти, она выводится сразу после Blocks, параметр size=1233.4K, лучше бы он не сильно превышал размер самого большого кэша в процессоре (если не ошибаюсь у Вас он 1М).
5. Либо, пусть превышает, но тогда надо развернуть ещё гораздо сильнее, чтобы выигрыш от разворачивания пересилил тормоза памяти.

Плюс можно играться pr_max для достижения баланса затрат времени между ускорителями и PARI — чем больше pr-max, тем выше коэффициент фильтрации и меньше работы остаётся PARI, но тем дольше работают ускорители и требуют больше памяти и для получения хорошей скорости придётся увеличивать коэффициент разворачивания (что ещё в разы повысит требования к памяти).

Величина pr_max напрямую влияет на время в PARI (через коэффициент фильтрации, сколько кандидатов выдадут ускорители), а массив bb[] на коэффициент фильтрации и время в PARI не влияет, зато влияет на время в ускорителях (и общее конечно).
Напомню, для Yadryara5.asm нельзя ставить pr_max>16384 (это мой давно исправленный глюк в x32 SSE версии), а для Yadryara6.asm нельзя pr_max>32768.

Ещё можно чуть поточнее ограничить диапазон для ускорителей, не +0.1%, а буквально до сотен, заодно и вообще убрать цикл по ii: фактически надо формулу для ii= перенести на место ii в коде дальше, а из формулы для конца из цикла вычесть формулу для ii= и поставить на место 227e6 в вызове ускорителя, примерно так (исходник взял не именно ваш, от своего последнего запуска счёта):

\\Было:
      forstep(ii=floor(h/pp_mod),ceil((h+step-1)/pp_mod),227*10^6, \\ВАЖНО: чтобы не считать лишнего эта величина не должна сильно превышать ceil(step/440538835723387181869888800)!
         printf("%s: %0.3fe35\t\t%c", ff[g],(p[g]+pp_mod*ii)/1e35,13);
         vi=extern(strexpand("\"",pat[g],".exe\" ",ii," ",227*10^6)); q+=#vi;
\\Надо:
   \\Убрать   forstep(ii=floor(h/pp_mod),ceil((h+step-1)/pp_mod),227*10^6, \\ВАЖНО: чтобы не считать лишнего эта величина не должна сильно превышать ceil(step/440538835723387181869888800)!
         printf("%s: %0.3fe35\t\t%c", ff[g],(p[g]+pp_mod*floor(h/pp_mod))/1e35,13);
         vi=extern(strexpand("\"",pat[g],".exe\" ",floor(h/pp_mod)," ",ceil((h+step-1)/pp_mod)-floor(h/pp_mod)+1)); q+=#vi;

Плюс-минус единицы тут важны. Если pp_mod не была определена выше, то это просто pp_mod=pp.mod — мелкая оптимизация чтобы не лазить каждый раз в структуру, польза под вопросом.
Реальное ограничение будет не точно до единиц потому что ускоритель дополнительно сам расширит диапазон до границ разворачивания цикла (1110 для примера выше), правда реально считать будет лишь нижнее дополнение (без выдачи результатов, они выдаются строго лишь в запрошенном диапазоне), верхнее считаться не будет.

PS. В принципе это занятие на денёк, зато есть некоторая надежда что получится ускорить счёт на несколько процентов, может даже на десяток.

[EUgeneUS]

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

С такими ограничениями вольфрамальфа не находит решений уже даже для трёх переменных кроме тривиального с единицами.
Есть ли они вообще? И если нет, стоит ли развивать дальше эту ветвь с кучей (больше двух во всей цепочке) квадратов?

А Вы какой запрос делали Вольфраму? Можно посмотреть?
Меня уже давно гложут смутные сомнения, что у двух Пелль-подобных уравнений не может быть одинаковых решений, кроме первого $(1,1)$.
Но как это доказать - вопрос Может быть это известный факт?
Предыдущий раз, когда с этим столкнулись, в Пелль-подобных уравнениях удалось повысить степени обоих переменных, после чего удалось доказать отсутствие решений уже уравнения 4-й степени. Здесь получается повысить степень только одной переменной из двух.

-- 24.07.2022, 07:56 --

Новости по поиску 14-ки на 72 делителя.
Наконец-то запустил счет (4 потока, на втором компьютере опять вышел из строя БП).

За сутки посчиталось до 200e76 и нашлось:
1. Две цепочки с

valids=9

2. Заметное количество (10-20) цепочек с

valids=8

Ручная выборочная до-проверка цепочек показала, что есть некоторое количество (единицы) цепочек с 12-ю подходящими числами из 14.
Это внушает осторожный оптимизм, что 14-ку можно найти в обозримое время.
Приглашаются желающие сократить это "обозримое врем" и подключиться к счету

[Yadryara]

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

Если Вы боретесь за каждый процент скорости,

Да нет, не борюсь за каждый. Даже думаю вернуть назад прежнюю проверку, а то находок очень уж мало.

Основная засада ведь именно в уменьшении удельного времени счёта. Если раньше уходило 10 часов на компиляцию и 15-25 суток на счёт, то сейчас на счёт уже тратится меньше двух суток.

Но я постараюсь внимательно изучить Ваши рекомендации.

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

Приглашаются желающие сократить это "обозримое врем" и подключиться к счету

К вопросу о том, кто больше нуждается в помощи Тот у кого 4 потока или тот у кого 1 на тех же 32 разрядах...

[EUgeneUS]

Очередные новости
$M(72) \ge 14$

(Оффтоп)

R1-41:4403703123956663452504336854458131461590660820252225726746666546884499437758712: 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72,  valids=14, maxlen=14/14/14/14/14/14, ALL, FOUND!

Я починил БП на втором компьютере, поэтому вторую половину дня считалось в 8 потоков.
Фактически считалось около 2-х суток, в расчете на 4-ре потока.
Думаю, можно и 15-ку тут попробовать поискать...