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

[Dmitriy40]

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

Правильно ли я понимаю, что в цепочку длиной 11 и более обязательно входят числа:
$n_0 = 32 p$ и $n_2 = n_0+2$ ?

Да, и даже для цепочек 10+. Как и $n_{30}=n_0-2$.

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

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

Это сотые доли секунды даже на медленном PARI, базы не нужны, их качать дольше чем насчитать такие простые.

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

Пусть $N$ - это число $n_2$ в наименьшей известной цепочке длиной 11, тогда проверять надо до $q r^2 < N/2$.
При этом можно проверять только простые, удовлетворяющие условию $q, r < \sqrt[3]{N}$

Нет, это только для нахождения минимального делителя, но надо ведь найти и второе число:

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

б) выполнить $2.1 \cdot 10^{12}$ проверок на простоту.

А вот тут не очень понятно: минимальная известная 11-ка сейчас примерно 1e22, для $r=17$ надо проверить $q<10^{22}/2/r^2\approx1.73\cdot10^{19}$, а это порядка $1.73\cdot10^{19}/\ln(1.73\cdot10^{19})\approx3.9\cdot10^{17}$ простых.
На самом деле несколько меньше так как далеко не любое $q$ подойдёт, надо чтобы оно при умножении хотя бы на один из 4-х возможных остатков $r^2\bmod32$ давало остаток ровно $2\bmod32$, а таких вариантов $q$ всего 3 штуки по модулю 32, т.е. проверять надо примерно 1/10 от указанного количества или 4e16 простых, что всё равно слишком много. PARI проверяет на простоту порядка 1e8/c, т.е. это на 4e8 секунд или 12 лет. Только для одного малого $r$.

Но, если в цепочку входит $n_2=n_0+2$, то в неё же входит и $n_{30}=n_0-2=18x$. Потребовав чтобы все неизвестные числа имели остаток $\pm1\bmod6$ и нужные остатки по модулю 32 можно сократить количество допустимых вариантов ещё в несколько (десятков) раз. Но остаётся всё равно слишком много.

-- 28.10.2022, 14:31 --

При учёте чисел $n_{30},n_0,n_2$, причём $n_2=2qr^2$ и $q\ne3$ получаем 54 варианта $q$ по модулю 288, т.е. в 5.3 раза меньше:

len=lcm([2^5,3^2]); m=vector(len);
{forstep(q=1,len,2,
   n0=2*q*1-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*9-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*17-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*25-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
)}
m=Vec(select(x->(x>0),m,1));
print(len,"/",#m,"=",1.0*len/#m); print(m); quit;

Её вывод:
288/54=5.333333333333333333333333333
[1, 7, 9, 11, 17, 25, 33, 35, 41, 47, 57, 61, 65, 71, 73, 79, 81, 89, 97, 101, 105, 113, 115, 119, 125, 129, 133, 137, 143, 153, 155, 169, 173, 177, 179, 185, 187, 193, 197, 201, 209, 223, 225, 227, 233, 241, 249, 251, 263, 265, 273, 277, 281, 287]

Учёт зеркальности (9 не на 32p-2, а на 32p+2, соответственно q на 32p-2) количество вариантов удваивается, а выигрыш падает вдвое, до 2.7 раза.

-- 28.10.2022, 14:40 --

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

Учёт зеркальности (9 не на 32p-2, а на 32p+2, соответственно q на 32p-2) количество вариантов удваивается, а выигрыш падает вдвое, до 2.7 раза.

Неправ, не вдвое:

len=lcm([2^5,3^2]); m=vector(len);
{forstep(q=1,len,2,
   n0=2*q*1-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*9-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*17-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*25-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*1+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*9+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*17+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   n0=2*q*25+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), m[q]=q);\\32p даёт p%6=1,5
   if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
)}
m=Vec(select(x->(x>0),m,1));
print(len,"/",#m,"=",1.0*len/#m); print(m); quit;

Вывод:
288/91=3.164835164835164835164835165
[1, 7, 9, 11, 15, 17, 19, 23, 25, 29, 33, 35, 37, 39, 41, 43, 47, 55, 57, 61, 63, 65, 71, 73, 79, 81, 83, 87, 89, 91, 95, 97, 101, 103, 105, 111, 113, 115, 119, 125, 127, 129, 133, 135, 137, 143, 145, 151, 153, 155, 159, 169, 173, 175, 177, 179, 181, 183, 185, 187, 191, 193, 197, 199, 201, 205, 207, 209, 215, 223, 225, 227, 231, 233, 235, 241, 245, 247, 249, 251, 253, 255, 259, 263, 265, 271, 273, 277, 279, 281, 287]

-- 28.10.2022, 14:49 --

И снова ошибся, выигрыш намного больше:

len=lcm([2^5,3^2]); m=vector(len);
{forstep(q=1,len,2,
   n0=2*q*1-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*9-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*17-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*25-2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==2 && setsearch([1,5],((n0-2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*1+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*9+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*17+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
   n0=2*q*25+2;
   if(n0%32==0 && setsearch([1,5],(n0/32)%6), \\32p даёт p%6=1,5
      if(n0%18==16 && setsearch([1,5],((n0+2)/18)%6), m[q]=q);\\18p даёт p%6=1,5
   );
)}
m=Vec(select(x->(x>0),m,1));
print(len,"/",#m,"=",1.0*len/#m); print(m); quit;

Вывод:
288/4=72.00000000000000000000000000
[89, 191, 199, 209]

Всего 4 варианта по модулю 288 допустимо для $q$.

[Huz]

@Dmitry, may I get a couple more sets of factors? Assuming they are both semiprime, these should be the last for a while: it will confirm D(92,7).

(Оффтоп)

7391622761940698662746728973350213034032662696649247351095119038886449805300917369378639370896627858127081417819831909241656831
and
7929445499336865865335897617591376843943981042718056846549688058059811473408890070987167192253789745930337347309523

[Dmitriy40]

Да что ж такое то, опять ошибся! Самый-самый правильный код такой:

len=lcm([2^5,3^2]); m=vector(len); rr=vector(len);
forstep(r=1,len,2, rr[r]=(r^2)%len); rr=setminus(Set(rr),[0]);
{forstep(q=1,len,2,
   foreach(rr,r2,
      n0=2*q*r2-2;
      if(n0%32!=0 || !setsearch([1,5],(n0/32)%6) || n0%18!=2 || !setsearch([1,5],((n0-2)/18)%6), next);
      m[q]=q; break;
   );
   foreach(rr,r2,
      n0=2*q*r2+2;
      if(n0%32!=0 || !setsearch([1,5],(n0/32)%6) || n0%18!=16 || !setsearch([1,5],((n0+2)/18)%6), next);
      m[q]=q; break;
   );
)}
m=Vec(select(x->(x>0),m,1));
print(rr); print(len,"/",#m,"=",1.0*len/#m); print(m); quit;

Вывод:
[1, 9, 25, 49, 73, 81, 97, 121, 145, 153, 169, 193, 217, 225, 241, 265]
288/18=16.00000000000000000000000000
[7, 31, 41, 55, 89, 103, 113, 127, 137, 151, 199, 209, 223, 233, 247, 257, 271, 281]

[EUgeneUS]

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

Нет, это только для нахождения минимального делителя, но надо ведь найти и второе число:

Да, что-то меня занесло

Скажите, пожалуйста, а насколько сложно перебрать:
а) первые $3.2$ миллиарда простых чисел
б) первые $11$ миллиардов простых чисел
?
Тут имеется в виду номер простого числа, а не его величина.

[Dmitriy40]

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

Скажите, пожалуйста, а насколько сложно перебрать:
а) первые $3.2$ миллиарда простых чисел
б) первые $11$ миллиардов простых чисел

Первое несложно, это примерно до 77e9, PARI справится минут за 10:

? n=0; forprime(p=1,77e8, if(p%32==1, n++));
time = 47,424 ms.

Второе это примерно до 28e10, грубо вчетверо дольше, за час должен справиться.
Если условие проверки сложнее, то и время пропорционально дольше, так что это лишь порядок величины. Но в общем реально.

-- 28.10.2022, 16:15 --

Оценка primepi(x):

C:\>primecount 77e9
3205474366
C:\>primecount 28e10
11060658751

-- 28.10.2022, 16:53 --

Huz
In progress ...

[EUgeneUS]

Dmitriy40
Спасибо!

Некоторые мысли по поиску минимальных цепочек с 12 делителями.
От $n_{-7}$ до $n_7$ существует ровно один вариант размещения двоек и 6 вариантов размещения троек.
Они изображены на рисунке:


Нижние четыре варианта размещения троек для поиска минимальных цепочек нужно исключить (для поиска цепочек вообще они исключались, как малоперспективные).
Это можно сделать так. Видно, что в этих вариантах есть позиция с неизвестным $p^2$. Это можно записать так:
$16 p_0 \pm 1 = 3 p_2^2$
Или: $p_0 = (3 p_2^2 \pm 1)/16$

При этом $p_2$ нужно перебирать пока $p_2 < \sqrt{N/6}$, где $N$ - величина чисел в известной цепочке. Для известных цепочек длиной 11 и 12 оценка была выше.

[Dmitriy40]

EUgeneUS
Я выше достаточно просто показал что цепочек длиной 10+ с $6x^2$ не бывает вообще. Соответственно остаются только два верхних варианта с картинки.

[EUgeneUS]

Теперь расставляем пятерку (в левом верхнем паттерне на картинке, правый верхний - симметричный)

Числа от $n_{-2}$ до $n_2$ обязательно входят в цепочки длиной 10 и более. Их пять, а значит там есть пятерка.
Варианты расстановки пятерки.
Первая степень.
Позиции $n_0$ и $n_{-2}$ исключаются однократной проверкой.
Позиции $n_1$ и $n_2$ могут быть исключены перебором простых (там опять возникает неизвестный $q^2$).
Итого (после всех проверок) пятерка в первой степени в этих числах может быть только в позиции $n_{-1}$

Вторая степень.
Позиции $n_0$ и $n_{-2}$ невозможны.
Остальные - могут быть. Итого, три варианта.

Третья степень.
Может быть только в позиции $n_{-1}$, то тогда в этой позиции возникает неизвестный $q^2$, что опять же проверяется перебором простых.

Пятая степень.
Может быть в позиции $n_{-1}$

[Dmitriy40]

EUgeneUS
Тут тоже есть хитрости: $15x^2$ на месте $32p-1$ допустимо, а на месте $32p+1$ нет (по модулю 8). Потому будет разница между левой и правой табличкой.
И с семёркой и остальными простыми до 15 такая же байда.

Для цепочек длиной 12+ можно и нужно проверять и места $32p\pm4$, туда как раз попадает пятёрка в некоторых вариантах, причём обязательно в первой степени. И тогда запрещает там быть тройке (ну или тройка запрещает там пятёрку).

-- 28.10.2022, 17:51 --

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

Третья степень.
Может быть только в позиции $n_{-1}$, то тогда в этой позиции возникает неизвестный $q^2$, что опять же проверяется перебором простых.

Не может, $125x^2=32p\pm1$ неразрешимо по модулю 8 (и на $n_1=32p+1$ тоже).

-- 28.10.2022, 17:55 --

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

Пятая степень.
Может быть в позиции $n_{-1}$

Тоже не может: $5^5x=32p-1$ неразрешимо в простых $x,p$ по модулю 6.
А вот для правой таблички $5^5x=32p+1$ по модулю 6 разрешимо.

-- 28.10.2022, 17:57 --

$x=3$ за решение не считаю, оно единственно, даёт слишком малые числа и проверяется прямо.

-- 28.10.2022, 18:13 --

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

Позиции $n_1$ и $n_2$ могут быть исключены перебором простых (там опять возникает неизвестный $q^2$).

Здесь тоже перебирать не нужно: $n_1$ запрещается по модулю 8, а $n_2$ по модулю 32.
А для правой таблицы $n_{-2}$ запрещается по модулю 8. А $n_{-1}=15x^2=32p-1$ остаётся допустимым (для цепочек длиной до 11 включительно) и требует перебора, до 1e22, который я выше уже выполнил.

[EUgeneUS]

Dmitriy40
Несколько зациклился на возможности проверки перебором простых и упускаю проверки по модулям

По расстановкам пятерок. Цепочки 12+
Левая таблица
Если пятерка есть в $n_{-1}$, то она есть в $n_4$, а там осталось только одно простое. Проверяется однократной проверкой.

Аналогично, правая таблица
Если пятерка есть в $n_{1}$, то она есть в $n_{-4}$, а там осталось только одно простое. Проверяется однократной проверкой.

Таким образом, так или иначе (проверкой по модулям, а где осталось - перебором простых) для цепочек 12+ можно исключить наличие пятерки в первой степени в позициях $n_{-2}..n_2$.

Т.е для цепочек 12+ осталось только три варианта для расстановки квадрата пятерок в $n_{-2}..n_2$. Для левой и правой таблиц они будут симметричны.
Если, конечно, можно выполнить перебор простых до (грубо) $\sqrt{N_{15}}$, где $N_{15}$ - величина чисел в известном минимальном пентадекатлоне.

[Dmitriy40]

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

Т.е для цепочек 12+ осталось только три варианта для расстановки квадрата пятерок в $n_{-2}..n_2$. Для левой и правой таблиц они будут симметричны.
Если, конечно, можно выполнить перебор простых до (грубо) $\sqrt{N_{15}}$, где $N_{15}$ - величина чисел в известном минимальном пентадекатлоне.

Вот тут непонятно, по какому квадрату перебирать то? Т.е. чему равно $A$ при $Ax^2=32\pm d$ ($d$ знать не принципиально, всегда можно округлить величину $Ax^2/32=p$ до ближайшего целого)? Вы же тут разместили квадраты пятёрки, значит остались неизвестными лишь первые степени простых, а не их квадраты.

Пентадекатлон пока всё ещё около 8e34, $\sqrt{8\cdot10^{34}}\approx2.8\cdot10^{17}$, при скорости PARI 1e8/с это по порядку величины 3e9 секунд или сотня лет. За счёт учёта допустимых остатков по большому модулю (чтобы все числа 32p-4...32p+4 где осталось найти одно простое давали остаток 1 или 5 по модулю 6 для него) можно сократить чуть более чем на порядок, до нескольких лет. Многовато.
С другой стороны:

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

Кстати при попытке обосновать $22p^2$ выявилось что в двух из подвариантов там нет запрещённых комбинаций и проверять надо до 1e35 (так округлил вверх наименьшую известную 15-ку). Это требует проверки простых до 67.42e16, что на PARI с forprime нереально долго, но вот учёт остатков по $\operatorname{lcm}(2^5,3^2,5^2,11)$ увеличивает скорость перебора простых с 1e8/c до 5e14/с и весь перебор до 1e35 занимает 5-10 минут! Т.е. если аккуратно расписать все допустимые варианты размещений малых простых (это несложно, собственно это уже сделано - есть же списки паттернов с программами их генерации, в том числе и с искомым $p^2$), то перебрать всё до 1e35 даже на медленном PARI выйдет похоже быстрее чем муторно доказывать выше что перебор можно сократить или исключить ... А если всё же сделать это программно для любой величины $A$ при $Ap^2$, то наверное за день-два можно перебрать и все $q^3p^2$ до 1e35 и не париться с математикой про недопустимость вариантов цепочек.

-- 28.10.2022, 19:04 --

Huz

(Оффтоп)

7929445499336865865335897617591376843943981042718056846549688058059811473408890070987167192253789745930337347309523 = 76018718199417416784823896826241261 * 104309118690160111211591000634618662515504131002775997015950379979818468785937343

Took 3.5 hours.

[EUgeneUS]

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

Вот тут непонятно, по какому квадрату перебирать то? Т.е. чему равно $A$ при $Ax^2=32\pm d$ ($d$ знать не принципиально, всегда можно округлить величину $Ax^2/32=p$ до ближайшего целого)? Вы же тут разместили квадраты пятёрки, значит остались неизвестными лишь первые степени простых, а не их квадраты.

Тут возникло недопонимание.
Для цепочек 12+ по модулям или (что осталось) перебором можно исключить пятерки в первой степени в позициях $n_{-2}...n{2}$.
Если перебор для оставшихся вариантов можно выполнить за разумное время, конечно.
А для квадрата пятерки из пяти позиций возможны три (без учета ограничений по модулям).

Для цепочки длиной 11.
Для левой таблицы: пятерка в первой степени в позиции $n_{-1}$ остаётся возможной, но тогда цепочка располагается в позициях $n_{-7}...n_{3}$
Для правой таблицы: пятерка в первой степени в позиции $n_{1}$ остаётся возможной, но тогда цепочка располагается в позициях $n_{-3}...n_{7}$

[Dmitriy40]

Разделение по степеням не слишком удобно в реализации перебора: перебрать $15r^2, 35r^2, 55r^2, 65r^2$ реально, тем более всего лишь до 1e22 (уже выполнил), а вот перебрать $5qr^2$ (скажем при $13<r<10^3$) совершенно другое дело, хотя и там и там степень пятёрки первая.
Так что на мой взгляд удобнее разделять перебор идёт линейно или квадратично (или степень ещё выше). Линейно это наш обычный поиск с ускорителями (для мазохистов без них), остальное относительно реально (за несколько дней, смотря как сильно можно наложить ещё условия).

[Huz]

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

Huz

(Оффтоп)

7929445499336865865335897617591376843943981042718056846549688058059811473408890070987167192253789745930337347309523 = 76018718199417416784823896826241261 * 104309118690160111211591000634618662515504131002775997015950379979818468785937343

Took 3.5 hours.

Thanks, are you also trying the larger number?

[Dmitriy40]

Huz
In process. ECM finished after 4 hours (divisor not found), 2.7 hours took init gnfs, and already 1.5 hours running lasieving, but there is no assessmen for her time, are waiting, sir. Perhaps by the morning, after 7-10 hours, when I wake up, there will already be a result ...