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

[Huz]

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

Huz, hint:
For sample pattern
2^2.3 7^5 2.5^2 3 2^5 11.31^2 2.3^2 5 2^2.7 3 2
you are checking $i$ from $n=n_0+im$ up to $3864659918=\lfloor 9887353188984012120346/2^5/3^2/5^2/7^5/11/31^2/2\rfloor$, where the last $2$ are obvious from the odd $p$ criterion, but you absolutely know the remainder of $32p$ (and, accordingly, $p$ and $n$) by modulo $3$, which makes it possible to reduce the upper limit by three times and speed up the work by the same number of times.
Accounting for remainders modulo 5 can give another 20% acceleration (only 4 remainders out of 5 are acceptable), but this is a complication of the code.

If I correctly understand what you're talking about here, I check for these in the core loop with this:

        for (uint ii = 0; ii < inv_count; ++ii) {
            t_mod *ip = &inv[ii];
            if (ati % ip->m == ip->v)
                goto next_ati;
        }

The inv[] array used there is set up before the loop to contain the disallowed values mod each allocated prime, like this:

            ulong inverse = small_divmod(wv_o[vi], wv_qq[vi], ap->p);
            if (inverse < ap->p) {
                t_mod *ip = &inv[inv_count++];
                ip->v = (inverse) ? ap->p - inverse : 0;
                ip->m = ap->p;
            }

But I may not be understanding you correctly: this check ensures, for the above pattern, that the $2 \cdot 3^2$ in the seventh position does not become $2 \cdot 3^3$, so it rejects one of the possible values $\pmod{3}$. But you appear to be saying that I can reject two of the possible values $\pmod{3}$, and I don't see where that is coming from.

[Dmitriy40]

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

But you appear to be saying that I can reject two of the possible values $\pmod{3}$, and I don't see where that is coming from.

In the pattern, $3^1$ stands in place of 32p-1, i.e. $(32p-1)\bmod3=0$ (the number $32p-1$ must be divisible by $3$). Hence $(32p-1)\bmod 3=0 \to 32p \bmod 3 =1\to p\bmod 3 = 2$, only!
Similarly for $3^1$ in place of 32p+1: $(32p+1) \bmod 3 =0 \to p \bmod 3=1$, only!
Both of these values cannot be together in any way: $3^1$ either in one place or in another, but never at the same time.
If you are already checking for divisibility by 3, then the acceleration will only be double, not triple.

-- 23.10.2022, 16:39 --

Even if you explicitly check the remainder of the division by a prime in the main loop, then excluding the check by 3 will reduce the number of division operations by one for half ii, and for the other half it will exclude it altogether. Yes, in this case, the acceleration is not so significant...

[Huz]

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

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

But you appear to be saying that I can reject two of the possible values $\pmod{3}$, and I don't see where that is coming from.

In the pattern, $3^1$ stands in place of 32p-1, i.e. $(32p-1)\bmod3=0$ (the number $32p-1$ must be divisible by $3$). Hence $(32p-1)\bmod 3=0 \to 32p \bmod 3 =1\to p\bmod 3 = 2$, only!
Similarly for $3^1$ in place of 32p+1: $(32p+1) \bmod 3 =0 \to p \bmod 3=1$, only!
Both of these values cannot be together in any way: $3^1$ either in one place or in another, but never at the same time.
If you are already checking for divisibility by 3, then the acceleration will only be double, not triple.

No, sorry, I don't think that is correct: the value of $p$ for $32p$ is already constrained not to be a multiple of 3 by the CRT calculation.

Let $v_j$ represent the number in the j'th position ($0 \le j < 11$), and let $q_j$ represent the allocation at that position. The actual calculation of $p = v_4/q_4$ for a given value of the loop variable $i$ is done via $p = o_j + i \cdot Q_j$. Where the initial CRT calculation tells us that $v_0 \equiv m \pmod{a_q}$, for each $j$ we calculate $Q_j = a_q/q_j$ and $o_j = (m + j)/q_j$. In this case, we will have $Q_4 = 2^5 \cdot 3^2 \cdot 5^2 \cdot 7^5 \cdot 11 \cdot 31^2 \cdot 2 / 2^5$, a multiple of 3; and $o_4 \equiv 1 \pmod{3}$, so we will automatically generate $p \equiv 1 \pmod{3}$ in every case.

In fact, this set of calculations fixes $v_j \pmod{a_q}$ for all $j$; the additional checks are checking for disallowed values $\pmod{3^3}, \pmod{5^3}, \pmod{7^6}$, etc.

[Dmitriy40]

Yadryara
Итак, завершилась проверка и $15p^2$ до 6e26. А выше их быть и не может. Найдены 7 цепочек длиной 7 и одна длиной 8:
15p2=4286485300007:275609343407641511913000729: 16,128, 2, 24, 12, 12, 12, 12, 12, 12, 12, 12,128, 8, 8, valids=8, maxlen=8
Более длинных не найдено.

Выходит цепочек длиной 10+ с числами вида $p^2qr$ с условиями $r<q<15<p$ вообще нет в природе. Если я нигде не ошибся!
Как и цепочек длиной 10+ с числами вида $p^2q^3$.

To All. Повторю просьбу/предложение проверить мои выкладки, вдруг я всё же в чём-то не прав и что-то упустил. Хотелось бы хоть какой-то реакции прежде чем оформлять и выкладывать кучу рассуждений (это на несколько часов занятие, а со временем и так туго).

[Dmitriy40]

Huz
OK, you know best.

[Dmitriy40]

Итак, выкладки по недопустимости чисел вида $p^2qr, r<q<15<p$ в цепочках длиной 10+.
Предварительно:
1) Все простые $x\ne3\mod6$, тройка проверяется отдельно и не интересна.
2) В цепочке всегда есть число $32p$, причём $p\bmod6=\pm1 \to 32p \bmod 192=\{32,160\}$.
3) Число $p^2qr$ должно попадать в цепочку, т.е. давать остаток по модулю $192$ или $(32-7 \ldots 32+7)$ или $(160-7 \ldots 160+7)$.
4) Условию $r<q<15$ удовлетворяют 15 комбинаций $r,q$: $(2,3),(2,5),(2,7),(2,11),(2,13),(3,5),(3,7),(3,11),(3,13),(5,7),(5,11),(5,13),(7,11),(7,13),(11,13)$.
5) $p^2 \bmod 6 = 1, p^2 \bmod 8 = 1, p^2 \bmod 32 = \{1,9,17,25}, p^2\bmod192=\{1,25,49,73,97,121,145,169\}$.
6) Или $32p-1$ или $32p+1$ делится на $3$, т.е. на одном из них обязательно стоит $3$ в любой степени. А на одном из 32p-2 или 32p+2 стоит $3^2$ (в первой быть не может смотри пункт про $6p^2$, а пятую проверяем прямым вычислением).

Приступим.
$6p^2$.
Может быть только на чётных местах (нумерация здесь и далее относительно 32p). Места -6 и +6 запрещены так как тогда тройка попадёт на место 32p.
Места -4,-2,+2,+4: $6p^2=32x+\{-4,-2,+2,+4\}$ - недопустимы по модулю 8.
Итого: вариантов нет.

$10p^2$.
Тоже может быть только на чётных местах.
Места -4,-2,+4,+6 недопустимы по модулю 8: $10p^2=32x+\{-4,-2,+4,+6\}$ решений не имеет.
Место +2: $32x+2=10p^2$ решений не имеет (по модулю 32).
Место -6, вариант с 3 на 32p+1: $3^2$ на 32p-2 (в первой там недопустимо так как $6p^2$ решений не даёт, а пятую проверяем прямо), но $10p^2+6=18y+2$ решений не имеет (по модулю 6).
Место -6, вариант с 3 на 32p-1: с $5$ на 32p-1 все решения слишком малы, $5^5$ на 32p-1 проверяем прямо, остаётся вариант лишь $75y$ на 32p-1, $10p^2+6=75y+1$, решений не дающий (по модулю 5).
Итого: вариантов нет.

$14p^2$.
Тоже только на чётных местах.
По модулю 8 допустимы только места -2 и +6, второе отвергается по модулю 32, остаётся только место 32p-2.
На месте 32p+5 получаются и $3$ (32p-2 занято, значит $3^2$ на 32p+2 и $3$ на 32p+5) и $7$, т.е. $21y^2$, но все решения $14x^2+2=32p=21y^2-5$ слишком малы, значит цепочек 13+ не будет.
Для пятёрки остаётся ровно один допустимый вариант, 32p-1 (32p-2 занято, 32p занято, 32p+2 занято, 32p+1 запрещено попаданием пятёрки на 32p-4, где уже есть тройка).
В этот момент наткнулся на ошибку вольфрамальфа с решением уравнений с двумя квадратами (кстати тогда и ограниченность решений выше под вопросом), долго выяснял как их решать без него, запустил проверку этого варианта до 6e26, за 5с ничего не нашёл, и пошёл спать.

[EUgeneUS]

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

но все решения
$14x^2+2=32p=21y^2-5$ слишком малы

Если рассмотреть только одно равенство: $14 x^2 + 2 = 21 y^2 -5$, то оно приводит к Пелль-подобному уравнению:
$3 y^2 - 2 x^2 =1$, которое
а) в нашей теме встречается на каждом шагу.
б) довольно хорошо разобрано. Например, тут.

Про свойства решений этого уравнения можно сказать следующее:
1. Решений - бесконечная серия.
2. Величина чисел в решении растет экспоненциально с номером решения (примерно на десятичный порядок)
3. Остатки по люблому модулю периодичны. Поэтому для Вашего (полного) уравнения должна бы быть бесконечная серия, раз есть хоть одно.
3.1. Из предыдущего пункта и наличия решения $(1,1)$ следует, что для любого модуля найдется бесконечная серия решений, которые будут давать в остатке единицу.
4. Простые числа в решениях встречаются. Но имеется ли решение (чтобы оба числа были простыми) в простых числах - неизвестно.

С учетом пункта 2 и того, что имеется простая реккурентная формула, проверить, что нет решений в простых числах до каких-то больших чисел ($10^{20} ... 10^{50}$) не составит труда и не потребует большого времени.
Порядок чисел $10^{50}$ - это всего лишь где-то 50-е решение данного уравнения.

-- 24.10.2022, 08:49 --

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

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

И действительно, из каждых восьми решений Пелль-поддобного уравнения, четыре дают решение полного уравнения в целых числах.
Если потребовать, чтобы $p$ было нечетным, то из каждых восьми решений Пелль-подобного уравнения два будут давать решения полного уравнения.

Следующее (для нечетного $p$): $x = 1046629; y=854569; p=479251615343$ (если не ошибся при наборе цифр).
И это всего лишь седьмое решение Пелль-подобного уравнения.

[Yadryara]

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

Повторю просьбу/предложение проверить мои выкладки, вдруг я всё же в чём-то не прав и что-то упустил.

Кое-что проверил, ошибок не нашёл.

[Dmitriy40]

EUgeneUS, Yadryara
Спасибо.

Кроме такого большого решения есть и прямо вот второе по счёту: $14\cdot11^2+2=21\cdot9^2-5=32\cdot53$.
Впрочем от этого не легче: проверил все решения до 1e35, с простыми нету.

Продолжу выкладки позже, я много где основывался на вольфрамальфа, а он гад оказывается ошибается. Ну и перепроверить его ответы, а скорее даже переформулировать их на обычном языке (в модулях или ещё как, например одна серия отброшена потому что все $p$ в $32p$ чётные, но как это доказать без вольфрамальфа и перебора всех остатков по модулю в десяток тысяч пока не представляю) требует времени. Которого пока нет.

[EUgeneUS]

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

Кроме такого большого решения есть и прямо вот второе по счёту:

Это видел в Ваших сообщениях выше. Я привел следующее.

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

Впрочем от этого не легче: проверил все решения до 1e35, с простыми нету.

Так это же хорошо.
Конечно, если стоит вопрос о существованиии вообще, то это мало помогает.
Но тут же (как понял) стоит вопрос о существовании цепочек с числами меньшими, чем в уже найденной. То есть, есть граница сверху. Проверили до неё и исключили вариант.

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

например одна серия отброшена потому что все $p$ в $32p$ чётные, но как это доказать без вольфрамальфа и перебора всех остатков по модулю в десяток тысяч пока не представляю

А приведите, пожалуйста, выкладки до этого места. Может что и получится без Вольфрама.

[Dmitriy40]

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

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

например одна серия отброшена потому что все $p$ в $32p$ чётные, но как это доказать без вольфрамальфа и перебора всех остатков по модулю в десяток тысяч пока не представляю

А приведите, пожалуйста, выкладки до этого места. Может что и получится без Вольфрама.

Чудеса ошибки: попытался привести такой пример, но не смог его найти в записях, те варианты для которых там прямо так написано при проверке в вольфрамальфа вдруг выдают вполне себе и нечётные $p$ ... Скорее всего было ещё где-то упоминание этого, но потом нашёл другой более простой вариант доказательства невозможности (и скорее всего как раз при попытке сформулировать для обсуждения здесь для выложенных выше вариантов) и это утверждение выкинул.

[Dmitriy40]

Продолжу пожалуй про $p^2qr$, теперь пойду с конца и уже без опоры на вольфрамальфа.

Сначала исправление неточности:

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

Места -4,-2,+2,+4: $6p^2=32x+\{-4,-2,+2,+4\}$ - недопустимы по модулю 8.

Место 32p-2 по модулю 8 допустимо, но зато недопустимо по модулю 32.

$143p^2$.
Только на нечётных местах (напомню, относительно 32p).
Места -7,-5,-3,+1,+3,+5 запрещены по модулю 8.
Место -1 запрещено по модулю 6.
Осталось только место +7.
$3^2$ может находиться только на 32p+2, на 32p-2 она попадёт и на 32p+7, а там всё занято. Но тогда $3$ попадает и на 32p-4, где есть и $11$, т.е. это число 12 делителей не даст и значит цепочек 12+ не существует. А до 1e22 (минимальной известной 11-ки) перебрал.
Итого: решений нет.

$91p^2$.
Только на нечётных местах.
Места -7,-3,-1,+1,+5,+7 запрещены по модулю 8, а место -5 по модулю 6. Остаётся только место 32p+3.
Если $3^2$ на месте 32p-2, то нет решений $91x^2-3=18y+2$ по модулю 9.
Если $3^2$ на месте 32p+2, то на 32p-4 и 4 и 3 и 7, что недопустимо, значит таких цепочек 12+ нет. А до 1e22 проверил.
Итого: решений нет.

$77p^2$.
Только нечётные места.
Места -7,-5,-1,+1,+3,+7 запрещены по модулю 8, место +5 по модулю 6, остаётся только 32p-3.
Если $3^2$ на месте 32p+2, то нет решений $77x^2+3=18y-2$ по модулю 6.
Если $3^2$ на месте 32p-2, то на 32p+4 и 4 и 3 и 7, что недопустимо, значит таких цепочек 12+ нет. А до 1e22 проверил.
Итого: решений нет.

$65p^2$.
Только нечётные места.
Места -5,-3,-1,+3,+5,+7 запрещены по модулю 8, место -7 по модулю 5, остаётся только 32p+1.
Так как 32p+1 занято, то тройка может быть только на 32p-1, а $3^2$ на 32p+2.
На 32p-4 будут и 4 и 3 и 5, что недопустимо, значит цепочек 12+ нет. А до 1e22 проверил.
Итого: решений нет.

$55p^2$.
Только нечётные места.
Места -7,-5,-3,+1,+3,+5 запрещены по модулю 8, место +7 по модулю 6, остаётся только 32p-1.
Так как 32p-1 занято, то $3$ на 32p+1, а $3^2$ на 32p-2. Но на 32p+4 и 4 и 3 и 5, что недопустимо, значит цепочек 12+ нет. А до 1e22 проверил.
Итого: решений нет.

$39p^2$.
Только нечётные места.
Места -7,-5,-3,+1,+3,+5 запрещены по модулю 8, место -1 по модулю 32, остаётся только 32p+7.
Так как на 32p+7 и 32p+4 по тройке, то $3^2$ может быть только на 32p+1. Пятёрка может быть только на 32p+1 (места +14, +4Б -2 заняты), т.е. на 32p+1 будет $45y$, но $39x^2-7=45y-1$ неразрешимо по модулю 9.
Итого: решений нет.

$35p^2$.
Только нечётные места.
Места -7,-3,-1,+1,+5,+7 запрещены по модулю 8, место -5 запрещено по модулю 32, остаётся только 32p+3.
Если $3^2$ на месте 32p+2, то $35x^2-3=18y-2$ неразрешимо по модулю 6.
Если $3^2$ на месте 32p-2, то там же и 5 и 2, что перебор, так что цепочек 10+ нет.
Итого: решений нет.

$33p^2$.
Только нечётные места.
Места -5,-3,-1,+3,+5,+7 запрещены по модулю 8, место -7 по модулю 32, остаётся только 32p+1.
При этом на 32p-2 будет $3^2$, но $33x^2-1=18y+2$ неразрешимо по модулю 9.
Итого: решений нет.

$26p^2$.
Только чётные места.
Места -4,-2,+4,+6 запрещены по модулю 8, место +2 по модулю 32, остаётся только 32p-6.
Если $3^2$ на 32p+2, то $3$ на 32p-4, но $26x^2+6=12y+4$ неразрешимо по модулю 6.
Если $3^2$ на 32p-2, то пятёрка должна быть или на 32p+1 или на 32p+2, остальные заняты. Но и $26x^2+6=5y-1$ и $26x^2+6=5y-2$ неразрешимы по модулю 5.
Итого: решений нет.

Остальные меньшие надо допроверять.

-- 25.10.2022, 19:56 --

Если кто будет проверять выкладки: проблема даже не в том что где-то ошибся (хотя мог), а скорее что мог пропустить какой-то допустимый вариант. Например если единственная разрешённая позиция 32p+7, то могут существовать цепочки с $32p+7=ABx^2$, при том что $x$ окажется не простым, что однако не помешает цепочке иметь длину вплоть до 14. И перебором по простым $x$ я такие цепочки не нашёл. Вопрос насколько это реально, пропустить такие цепочки ... Впрочем убрал проверку простоты числа в квадрате, ничего всё равно не нашлось. Но вдруг упустил что-то другое ...

[Yadryara]

Dmitriy40, вот не зря я в своё время рекомендовал Вас в ЗУ.

Полагаю, Вам нужно систематизировать Ваши выводы о недопустимости чисел определённого вида в тех или иных цепочках того или иного диапазона.

По аналогии с 1-й и 100-й, выберите страницу, где Ваше сообщение расположено в самом верху и правьте его многократно. Так всем заинтересованным будет легче ориентироваться.

Сам я несколько устал от от этой задачи и взял паузу.

[Dmitriy40]

(Оффтоп)

На текущий момент статус ЗУ не даёт преимуществ в редактировании сообщений, плюс cepesh может дать такую возможность любому юзеру, были бы основания. Несколько неудобно, но нужно не так уж часто, собственно вообще можно сказать почти однократно, причесать выводы и выложить, это не пополняемая постоянно таблица текущих рекордов.

На днях надеюсь доразберусь со всеми такими квадратами и посмотрю на $q^3p^2$.

Кстати при попытке обосновать $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 и не париться с математикой про недопустимость вариантов цепочек.

[EUgeneUS]

Про минимизацию цепочки для $T(6,11)$

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

Если это так, тогда:
Факторизация $n_2 = 2 q r^2$ либо $n_2 = 2 q^5$. Ниже рассмотрим только первый вариант, как наихудший.

$q r^2 = 16 p +1$

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

Таких простых чисел: $N_p = \frac{\sqrt[3]{N}}{ \ln \sqrt[3]{N}} = 1023093$, чуть больше миллиона.
А проверок на простоту $\frac{q r^2 -1}{16}$ нужно выполнить: $N_c = 2 N_p^2 \approx 2.1 \cdot 10^{12}$

Остаётся вопрос, насколько реально за разумное время:
а) найти первый миллон простых чисел. Наверное даже такие базы есть, уже посчитанные.
б) выполнить $2.1 \cdot 10^{12}$ проверок на простоту.

Конечно, что только некий фильтр, и на наборы $p,q,r$, прошедшие фильтрацию, нужно будет делать проверку - какой длины цепочки получились.