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

[EUgeneUS]

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

То-то и оно, что здесь квадратичный перебор не сработает. По той простой причине, что 12 делителей имеют числа вида $3125p$.

Ну и пусть себе имеет.

Там механика другая.
Всё также на примере верхней левой картинки
Цепочка $n_{-4}...n_{4}$
Пятерка должна быть или в $n_1$, или в $n_2$. Там допустимы только первая степень или квадрат пятерки.
Если пятёрка в первой степени в $n_1$, то получаем уравнение $32p+1 = 15 q^2$. Квадратичный перебор (если модули такое допускают).
Если пятёрка в первой степени в $n_2$, то получаем уравнение $32p+2 = 10 q^2$. Квадратичный перебор (если модули такое допускают).
Таким образом, мы обязаны разместить пятёрку в квадрате или в $n_1$, или в $n_2$.

11-ка с краю. Цепочка $n_{-7}...n_{3}$
Там появляется вариант размещения пятерки в $n_{-6}$. Там опять или первая степень или квадрат. И если там первая степень, то получаем уравнение $32 p - 6 = 10 q^2$. Квадратичный перебор (если модули такое допускают).

Таким образом, в любом варианте мы обязаны разместить в цепочке $5^2$, а это исключает в цепочке более высокие степени пятёрки.

-- 30.10.2022, 10:05 --

Вообще говоря, в позициях $n_1, n_2, n_{-6}$ может оказаться пятерка в пятой степени.
Но это проверяется однократными проверками, что числа $2 \cdot 5^5$ и $3 \cdot 5^5$ не порождают вокруг себя длинные цепочки чисел с 12-ю делителями.

[EUgeneUS]

На этом рисунке возможные расположения $2,3,5,7,11$ для цепочек 11+
UPD: поправил размещение 11-к



Заливка:
Оранжевое - запрещено так или иначе (по модулям, однократным или "квадратичным" перебором).
Желтое - могут быть только квадраты.
Светло зеленое - могут быть только первые степени.
Без заливки - могут быть степени $1, 2, 5$. Кубы проверяются "квадратичным" перебором.
Фиолетовое - при некоторых расположениях 5-к и 7-к можно быстро, квадратичным перебором, проверить, что цепочка не растёт до этих клеток.
UPD: темно зеленое - запрещается квадратичными переборами для цепочек 12+, до цепочек длиной 11 нужно проверять (возможен квадрат в одном из двух мест).

[Yadryara]

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

мы обязаны разместить в цепочке $5^2$, а это исключает в цепочке более высокие степени пятёрки.

Ну конечно же! Осталось только доказать, что квадрат пятёрки обязан быть в цепочке.

По квадратам ситуация такая:

Для $10p^2$ по модулю $64$ из диапазона $25-39$ возможен только остаток $26$.

Для $15p^2$ по модулю $64$ из диапазона $25-39$ возможны только остатки $31$ и $39$.

Вдоль и поперёк проверил все возможные паттерны для 11-к. Вот что пока не запрещено.

S-pattern

25  26  27  28  29  30  31  32  33  34  35
     2       4       2      32       2       
         3           9           3           
     5                   5

N-pattern

25  26  27  28  29  30  31  32  33  34  35  36  37  38  39
     2       4       2      32       2       4       2
  9          3           3           9           3
     5                   5                   5

Значит надо проверять разрешимость в простых числах
уравнений:

$10q^2=32p-6$

и

$15q^2=32p-1$

Вплоть до $10^{22}$. И если ни одного решения не найдётся, тогда первая степень пятерки невозможна ни на какой из этих позиций.

Тут ещё есть нюансы проверки.

[EUgeneUS]

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

N-pattern

Пятерки в первой степени в позиции $26$ и $31$ (в Вашей нотации) приводят к уравнению $10 p^2 +5 = 15 q^2$
То есть к нашему любимому уравнению $3 x^2 - 2 y^2 = 1$, которое легко проверяется до сильно больших чисел.

Но это слабо помогает, так как укорачивает цепочку до 13, а нас интересуют цепочки длиной 11 и 12.

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

$10q^2=32p-6$
и
$15q^2=32p-1$
Вплоть до $10^{22}$.

Лучше бы до $1.2 \cdot 10^{23}$, чтобы 12-ки тоже проверить до минимальной, раз уж это возможно.
А может быть и до $5.9 \cdot 10^{26}$, если получится. Чтобы и 13-ки включить в рассмотрение.

[Huz]

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

Hugo поменял обозначения по сравнению со статьёй Иво и Роджера 1989-го года, где использовалось обозначение $D(k,m)$.

Apologies for any confusion I am causing. My notation is driven by my focus on $T(n,k)$ as defined in A292580, except that the artificial halving of $n$ (which is done to fit with the standards of the OEIS) constantly trips me up so I prefer to talk instead of $D(n,k)$.

The names $n$ and $k$ are embedded in my code and my brain (I've been working on related sequences for at least 13 years), and feel so natural to me that it never occurs to me they might need translation - despite VAL's previous request.

[Dmitriy40]

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

А значить в выкладках выше "квадратичный перебор" остаётся только для случаев $32p \pm 1 = 15 q^2$

Только с минусом, $32p+1=15q^2$ неразрешимо по модулю 8.
А с минусом я перебрал все до 6e26, вот программа, кстати проверьте что не ошибся:

Используется синтаксис Text

\\      n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
\\      .       2       .       2^2     .       2       .       2^5     .       2       .       2^2     .       2       .
\\      3^2     .       .       3       .       .       3       .       .       3^2     .       .       3       .       .
\\      .       5^x     .       .       .       .       5       .       .       .       .       5       .       .       .
\\      .       .       .       p       .       .       p2      p       .       p       .       p       .       .       .

q=15; m6=[0,1,0,0,0,5];\\p%6=1,5, 32p%5=1, 32p%18=-2
{forprime(p=17,6.33e12,
                x=p%96; if(x!=7 && x!=25 && x!=71 && x!=89, next);\\Остатки взял из вольфрамальфа
                x=q*p^2; nn=round(x/32); n32=nn*32;
                if(abs(x-n32)>7, next);\\По идее лишняя, но чисто для спокойствия
                if(m6[nn%6+1]==0, next);\\Простое p в 32p
                if(!ispseudoprime(nn), next);\\Точно совсем простое
                if(n32%18!=16 || !ispseudoprime((n32+2)/18), next);\\Центральные 5 чисел
                if(numdiv(n32-2)!=12 || numdiv(n32+1)!=12, next);\\Центральные 5 чисел
                s=vector(15,d,numdiv(n32+d-8)); k=#select(x->(x==12),s);\\Всё, в лог
                w=strprintf("%dp2=%d:%d:",q,p,n32-7);
                foreach(s,d, w=strprintf("%s%3d,",w,d));
                w=strprintf("%s  valids=%d, maxlen=%d", w,k,t=0;maxlen=vecmax(vector(#s,d,if(s[d]==12,t++,t=0))));
                write("zq15p2.log",w);
)}

Максимум найдена 8-ка.

[EUgeneUS]

Dmitriy40
Выше уважаемый Yadryara писал, что ещё нужно проверить

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

$10q^2=32p-6$

[Dmitriy40]

EUgeneUS
У меня остались недоказанными (особенно без вольфрамальфа) случаи $10p^2, 14p^2, 15p^2, 21p^2, 22p^2$. Проверенными, но не доказанными в смысле что не факт что проверка произведена полностью (всех возможных вариантов).
Но проверил ли кто-то мои выкладки? Неясно. А я слишком часто ошибаюсь или опечатываюсь.

-- 30.10.2022, 19:24 --

Вариант $10p^2+6=18r+2$ (S-паттерн по Yadryara) неразрешим по модулю 6.
Вариант $10p^2+6=75r+1$ ($5^2$ на месте $32p-1$) неразрешим по модулю 75.
А вариант $10q^2+6=15r^2+1=32p$ я проверил при проверке варианта $15p^2$.
Так что не нужно.

[Yadryara]

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

Но проверил ли кто-то мои выкладки? Неясно. А я слишком часто ошибаюсь или опечатываюсь.

Кое-что проверяю. На одну ошибку совсем недавно указал, остальное чётко.

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

Вариант $10p^2+6=18r+2$ (S-паттерн по Yadryara) неразрешим по модулю 6.

Отлично! На подобные нюансы и намекал. Сейчас проверяю $15q^2=32p-1$. Другим способом:

write("begin.tmp","is begin");
t0=getwalltime();
start=1;
stop= 1613743000;
m=0; print();
{forstep(i=start,stop,2,
p = 120*i^2 - 345*i + 248;
q = 16*i - 23;
n = 32*p;
if (isprime(q) && isprime(p) && isprime((n+2)/18) && numdiv(n-2)==12 && numdiv(n+1)==12,m=m+1; print(m, "   ",n, "   ",numdiv(n-3), "   ",numdiv(n-2), "   ", numdiv(q), "   ",numdiv(p), "   ",numdiv(n+1), "   ",numdiv(n+2), "   ",numdiv(n+3));print())
)}
tob=getwalltime()-t0;
print();
printf("TIME = %0.2f seconds",tob/1000);
write("end.tmp","is end");
quit;

Есть ещё другая серия решений:

p = 120*i^2 - 615*i + 788;
q = 16*i - 41;

[Dmitriy40]

Если сразу потребовать чтобы $q\bmod 6=\{1,5\}$, то формула для $q$ станет типа $q=96i+d$ и будут 4 разных $d$ (сразу для обеих серий). Т.е. 96:4=24:1 вместо 16:2=8:1, втрое быстрее. Они у меня и использованы в программе выше.
А $16i-41$ смахивает на вольфрамовский глюк, ведь очевидно же что остаток (второе слагаемое) может быть меньше модуля (коэффициента в произведении) и всегда неотрицательным, я в уме всегда пересчитывал (и не использовал формулу для $p$).
Ну и печатать решения без сразу посчитанных valids и maxlen неудобно, я до 6e26 насчитал более 7000 решений с правильными 5-ю центральными числами вокруг 32p.

-- 30.10.2022, 20:46 --

И сравнить наши решения будет трудновато: я выводил n=32p-7 (вдруг нашлась бы 15-ка? ), Вы n=32p.

[Yadryara]

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

Если сразу потребовать чтобы $q\bmod 6=\{1,5\}$, то формула для $q$ станет типа $q=96i+d$ и будут 4 разных $d$ (сразу для обеих серий). Т.е. 96:4=24:1 вместо 16:2=8:1, втрое быстрее.

Вы правы. Можно и нужно потребовать. А то 8 часов считалось.

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

А $16i-41$ смахивает на вольфрамовский глюк,

Ну да, можно и $16i-9$ брать и пересчитать формулу для $p$. Я не стал париться, отрицательные числа-то крошечные.

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

Ну и печатать решения без сразу посчитанных valids и maxlen неудобно, я до 6e26 насчитал более 7000 решений с правильными 5-ю центральными числами вокруг 32p.

Тоже не парился, ибо всего 42 центральных 5-ки и одна 6-ка. Пока всё видно.

Спасибо, Вы опять подсказали как ускорить.

-- 30.10.2022, 21:41 --

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

И сравнить наши решения будет трудновато: я выводил n=32p-7 (вдруг нашлась бы 15-ка? ), Вы n=32p.

Посмотрим. Вот эта 6-ка у Вас есть?

6005974064520431463132; 384 12 12 12 12 12 12 2

[Dmitriy40]

Хм, у меня решений больше (или меньше? не пойму), правда сразу для двух серий (до первой 6-ки и ещё три шестёрки до 1e22):

(Оффтоп)

15p2=58439:51226750809: 32, 8, 16, 48, 4, 12, 12, 12, 12, 12, 4, 48, 8, 8, 8, valids=5, maxlen=5
15p2=34559449:17915332727754009: 32, 8, 8, 96, 16, 12, 12, 12, 12, 12, 16, 96, 32, 16, 4, valids=5, maxlen=5
15p2=145444697:317312398281327129: 24, 64, 8, 48, 2, 12, 12, 12, 12, 12, 8, 48, 32, 8, 4, valids=5, maxlen=5
15p2=263938151:1044950213299482009: 64, 32, 16, 24, 4, 12, 12, 12, 12, 12, 16, 48, 32, 8, 4, valids=5, maxlen=5
15p2=294496217:1300920327409666329: 6, 16, 4, 96, 4, 12, 12, 12, 12, 12, 8, 96,128, 32, 8, valids=5, maxlen=5
15p2=322485127:1559949857043091929: 32, 32, 8, 96, 4, 12, 12, 12, 12, 12, 16, 48, 32, 32, 8, valids=5, maxlen=5
15p2=477139417:3414930348826498329:384, 16, 4, 96, 4, 12, 12, 12, 12, 12, 4,192, 16, 32, 64, valids=5, maxlen=5
15p2=607434631:5534652464071592409: 16, 32, 8, 12, 4, 12, 12, 12, 12, 12, 16,384, 64, 32, 8, valids=6, maxlen=5
15p2=700528249:7361097414705090009: 12,128, 16, 48, 16, 12, 12, 12, 12, 12, 4, 96, 32, 16, 64, valids=6, maxlen=5
15p2=1002785447:15083679790724847129: 40, 32, 2, 24, 16, 12, 12, 12, 12, 12, 2, 12, 16, 16, 8, valids=6, maxlen=5
15p2=1285765561:24797896167804670809: 96, 32, 2, 96, 8, 12, 12, 12, 12, 12, 8, 48, 32, 32, 8, valids=5, maxlen=5
15p2=1466977049:32280324934391226009: 48, 16, 16, 48, 4, 12, 12, 12, 12, 12, 8, 12, 32, 12, 4, valids=7, maxlen=5
15p2=1771527239:47074631377784446809: 12,128, 2, 12, 8, 12, 12, 12, 12, 12, 8, 96, 16, 64, 16, valids=7, maxlen=5
15p2=2545274087:97176302669305253529: 96, 8, 8, 12, 4, 12, 12, 12, 12, 12, 4, 24, 32, 16, 4, valids=6, maxlen=5
15p2=2781707111:116068416770819494809: 48, 64, 8, 24, 8, 12, 12, 12, 12, 12, 16, 48, 32, 8, 4, valids=5, maxlen=5
15p2=3089489831:143174211237786128409: 48, 32, 16, 12, 16, 12, 12, 12, 12, 12, 4, 12, 64, 32, 4, valids=7, maxlen=5
15p2=3391616089:172545895427454838809: 24, 32, 4, 12,192, 12, 12, 12, 12, 12, 32, 24, 32, 8, 8, valids=6, maxlen=5
15p2=3639554521:198695356669973091609: 16, 16, 4,192, 4, 12, 12, 12, 12, 12, 4, 48, 16, 16, 4, valids=5, maxlen=5
15p2=4107059417:253019055821525698329: 40, 64, 16, 24, 4, 12, 12, 12, 12, 12, 8, 48, 32, 8, 4, valids=5, maxlen=5
15p2=4298640793:277174690008655032729: 80, 16, 4, 96, 8, 12, 12, 12, 12, 12, 4, 96, 16, 8, 4, valids=5, maxlen=5
15p2=4494282983:302978692969250674329: 12, 16, 4,192, 12, 12, 12, 12, 12, 12, 8, 48, 32, 32,128, valids=7, maxlen=6
15p2=17360956999:4521042418816906290009: 24, 32, 16, 24, 2, 12, 12, 12, 12, 12, 12, 48,192,256, 4, valids=6, maxlen=6
15p2=20009954297:6005974064520431463129: 16, 32, 4,384, 12, 12, 12, 12, 12, 12, 2, 96, 16, 16, 16, valids=6, maxlen=6
15p2=25266482119:9575926780046200952409: 96, 32, 4, 48, 12, 12, 12, 12, 12, 12, 8,192, 32, 16, 2, valids=6, maxlen=6

Все семёрки:
15p2=370593293767:2060090840776109415754329: 64, 32, 16, 12, 12, 12, 12, 12, 12, 12, 16,768, 4, 16, 4, valids=7, maxlen=7
15p2=1293214992551:25086075254380244782314009: 12, 64, 4, 12, 12, 12, 12, 12, 12, 12, 8, 96,256, 64, 8, valids=8, maxlen=7
15p2=1333936922489:26690815697691365909326809: 24,256, 2, 12, 12, 12, 12, 12, 12, 12, 4, 96, 4, 8, 4, valids=7, maxlen=7
15p2=1426776054841:30535348660014723593029209: 6, 16, 8, 12, 12, 12, 12, 12, 12, 12, 2, 96, 64, 16, 8, valids=7, maxlen=7
15p2=1449845950489:31530799202240277590086809: 24, 24, 8, 12, 12, 12, 12, 12, 12, 12, 8, 48, 64, 16, 32, valids=7, maxlen=7
15p2=3596724995527:194046460401730472550115929: 12, 16, 64, 12, 12, 12, 12, 12, 12, 12, 64, 24, 32, 32, 4, valids=8, maxlen=7
15p2=5835571144057:510808358660260857696288729: 24, 64, 4, 12, 12, 12, 12, 12, 12, 12, 16, 96, 4, 64, 24, valids=7, maxlen=7

Неплохо бы сравнить с Вашими.

-- 30.10.2022, 21:47 --

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

Вот эта 6-ка у Вас есть?
6005974064520431463132; 384 12 12 12 12 12 12 2

Есть, она третья по счёту:
15p2=20009954297:6005974064520431463129: 16, 32, 4,384, 12, 12, 12, 12, 12, 12, 2, 96, 16, 16, 16, valids=6, maxlen=6

[Yadryara]

Да, есть и все первые примерно десять Ваших 5-к тоже. Вторую серию только запустил.

[Dmitriy40]

Можно и ещё ускорить, если потребовать $r\bmod6=\{1,5\}$ из $32p=15q^2+1=18r-2$, будут 4 комбинации остатков для $q,r$ по модулю 6 и в каждой по две серии (для остальных менять два правых знака в скобках), зато модуль перебора не 96, а уже 288, т.е. 288:8=36:1 вместо 24:1, ещё в полтора раза быстрее.
И ещё раза в два можно ускорить увеличив модуль в 7 раз и исключив недопустимые варианты размещения $7^1$. но это совсем уж геморно варианты перебирать, я плюнул и написал программу.

[Dmitriy40]

Да, так о программе, вот какие остатки допустимы для $q$ (в $15q^2+1=32p=18r-2$):

q=15; len=lcm([2^5,3^2/*,7*/]); mm=vector(len);
{for(i=1,len,
   n32=q*i^2+1;
   if(n32%32!=0 || !setsearch([1,5],(n32/32)%6), next);\\32p даёт p%6=1,5
   if(n32%18!=16 || !setsearch([1,5],((n32+2)/18)%6), next);\\18p даёт p%6=1,5
\\   if(!setsearch([2,3,4,6],n32%7), next);\\7 на 32p-2,3,+3,+1
   mm[i]=i;
)}
mm=Vec(select(x->(x>0),mm,1)); print(len,"/",#mm,"=",1.0*len/#mm); print(mm);

Вывод без семёрки:
288/8=36.00000000000000000000000000
[7, 25, 71, 89, 199, 217, 263, 281]
Вывод с семёркой:
2016/32=63.00000000000000000000000000
[25, 71, 199, 263, 281, 295, 377, 487, 505, 601, 647, 839, 857, 871, 935, 953, 1063, 1081, 1145, 1159, 1177, 1369, 1415, 1511, 1529, 1639, 1721, 1735, 1753, 1817, 1945, 1991]

В итоге почти восьмикратное ускорение от 8:1.

А для цепочек 12+ места $32p-3, 32p+3$ недопустимы для семёрки и остаются варианты $32p-2, 32p+1$, т.е. ещё вдвое быстрее:

2016/16=126.0000000000000000000000000
[71, 281, 295, 377, 505, 601, 839, 953, 1063, 1177, 1415, 1511, 1639, 1721, 1735, 1945]

Место $32p+1$ недопустимо для семёрки для цепочек 14+, но это уже никакого выигрыша не даёт, видимо семёрка и так туда никогда не попадает.