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

[Dmitriy40]

Упс, а $q=31$ решений-то не даёт вообще ... Пятёрка попадает или на $32p+1$ или на $32p+2$, но и $15p^2$ и $10p^2$ в этих местах запрещены, значит там должен быть квадрат пятёрки, но $31^3p^2$ для любых $p$ не даёт нужных остатков по модулю 25.
$q=79$ не даёт решений по той же причине.
$q=41$ тоже не даёт решений по той же причине, только места $32p-1,32p-2$ и решений $15x^2+1=32p=41^3y^2-1$ нет.
$q=89$ тоже не даёт решений по той же причине.
А вот для $q=103$ решения есть:
q3=103,p2=478793964581:250500737428154988194654154841: 4, 32, 32, 48, 16, 12, 12, 12, 12, 12, 24, 48, 8, 16, 96, valids=5, maxlen=5
q3=103,p2=959513389669:1006036536031852532144601402841: 4, 8, 16, 24, 16, 12, 12, 12, 12, 12, 48, 48, 4, 32,512, valids=5, maxlen=5
q3=103,p2=1444068203419:2278699647002993413582312122841: 8, 64, 16, 96, 16, 12, 12, 12, 12, 12, 12, 24, 4, 16, 48, valids=6, maxlen=6
q3=103,p2=1621241508581:2872149904096617532322301210841: 4, 32, 16, 96, 16, 12, 12, 12, 12, 12, 32, 96, 32, 8,1024, valids=5, maxlen=5

О, даже более того, если $q^3p^2$ попадает на место $32p-1$, то варианты размещения и пятёрки (в квадрате) и семёрки (в квадрате или пятой степени) единственны. Т.е. можно перебирать с ещё в сотню раз больше шагом (примерно в сотню раз быстрее). Вероятно и про место $32p+1$ будет аналогично.

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

$11^3p^2$ может появляться в двух местах в цепочке (на 5-м и на 13-м местах) и 13-е место гарантированно не даст ни 14-ки ни 15-ки ($22p^2$ недопустимо на месте $32p-6$).

Тут я ошибся (в знаках мест относительно $32p$). На самом деле места $32p-5, 32p+3$ и оба не запрещены ($22p^2$ на месте $32p+6$ имеет решения).

[Huz]

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

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

Других цепочек с указанными условиями до 1.3e23 нет. Т.е. нет цепочек длиной 10+ с кубоквадратами (причём не обязательно в самой цепочке, может и вне её, но не далее 7 от $32r$).

Отлично. А теперь спросим, пришёл ли к такому же выводу Hugo.

I'm not sure exactly what you're trying to achieve here. If the question is "are there chains of 10 numbers each with 12 divisors of which at least one element is of the form $p^2 q^3$", then that's not something my code is designed to answer.

You could get a partial result (for $q < 10$) by asking it to list the way it would allocate powers of small primes if all such allocations were forced (a combination of the flags -a and -f), then picking out the ones with $q^3$ and asking it to work specifically on those sets (a combination of -b and the same -f). As a Unix pipeline that would look something like this:

# list signature (-a) with maximum forced primes (-f10)
  ./pcoul -f10 -a -x13e22 12 10 \
# search for signatures with a cube
    | grep '\^3' \
# get the batch number of those signatures
    | perl -nle 'print $1 if /^203 b(\d+)/' \
# invoke pcoul with -b for each of those batch numbers
    | xargs -I'{}' ./pcoul -f10 -b'{}' -x13e22 12 10

For larger $q$, it would discover them in passing by assigning $p^2$ and factorizing to check if what's left has 4 divisors, it doesn't have a way to look for them specifically.

[Yadryara]

Huz

Вот сейчас готовимся штурмовать D(12, 11). И Дмитрий, в частности, обнаружил как раз то, на что я рассчитывал:

Искомая минимальная 11-ка не содержит $p^3q^2$. Вообще. Ни на каком месте.

И теперь уже нужно меньше вариантов проверять.

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

For larger $q$, it would discover them in passing by assigning $p^2$ and factorizing to check if what's left has 4 divisors, it doesn't have a way to look for them specifically.

В частности, и эту проверку на 4 делителя теперь тоже делать не нужно.

Я прав?

[Huz]

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

Huz

Вот сейчас готовимся штурмовать D(12, 11). И Дмитрий, в частности, обнаружил как раз то, на что я рассчитывал:

Искомая минимальная 11-ка не содержит $p^3q^2$. Вообще. Ни на каком месте.

И теперь уже нужно меньше вариантов проверять.

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

For larger $q$, it would discover them in passing by assigning $p^2$ and factorizing to check if what's left has 4 divisors, it doesn't have a way to look for them specifically.

В частности, и эту проверку на 4 делителя теперь тоже делать не нужно.

Я прав?

I don't think so: the common case it is checking for is $qr$, the product of two primes (so that the entire number is $p^2qr$). The uncommon case is $q^3$. But the relevant subroutine is simply asked "does this number have 4 divisors?", and it checks what it needs to to answer that question.

I don't think it would become any faster if we replaced it with a subroutine that can answer "is this number the product of two distinct primes?" And the list of numbers we must check remains the same.

[Yadryara]

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

I don't think it would become any faster if we replaced it with a subroutine that can answer "is this number the product of two distinct primes?" And the list of numbers we must check remains the same.

Список может и останется прежним, но время-то должно уменьшиться?

Хотелось бы знать мнение Dmitriy40, VAL, EUgeneUS...

[EUgeneUS]

Yadryara
Вряд ли моё мнение по этому вопросу будет авторитетным.
Но с точки зрения банальной эрудиции:
1. Наихудший случай (требующий наибольшего времени) это $n=pq$, где $p, q \approx \sqrt{n}$
2. Если у числа четыре нетривиальных делителя, например, $n = p^2 qr$, то наихудшим случаем будет $p, q, r \approx \sqrt[4]{n}$. То есть в худшем случае делители будут в два раза короче. А значит находиться они будут существенно быстрее.

Таким образом, исключение чисел вида $n = p^2 qr$ не даст сколько-нибудь значимого ускорения.

[Yadryara]

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

2. Если у числа четыре нетривиальных делителя, например, $n = p^2 qr$

Здравствуй, Дедушка Мороз Нетривиальных делителей у таких чисел 10. А вот простых в разложении — 4.

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

Таким образом, исключение чисел вида $n = p^2 qr$

Речь-то шла о $p^3q^2$.

И не забудем о преобразованиях:

$x^2yz \to y^3x^2$ при $z=y^2$;

$x^2yz \to y^5z$ при $x=y^2$.

[EUgeneUS]

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

Нетривиальных делителей у таких чисел 10. А вот простых в разложении — 4.

"Я знал, я знал" (с) (что Вы укажете на эту некорректность. Конечно, подразумевались простые делители.

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

Речь-то шла о $p^3q^2$.

Тем более. В худшем случае порядок простых делителей будет порядок факторизуемого числа делить на $5$. То есть ещё короче.

[Dmitriy40]

Я вообще не понимаю о каком числе или списке чисел идёт речь.
Для обнаружения наименьшего делителя числа $n$ действительно достаточно перебрать простые до $\min(p,q,r)<\sqrt[4]{n}$ (иначе там не 12 делителей), но если он будет входить в квадрате (т.е. $p^2$), то для нахождения остальных придётся перебрать простые уже до $\sqrt{n/p^2}=\sqrt{n}/p$, что для малых $p$ всего на порядок-два-три меньше $\sqrt{n}$. А ведь в цепочках 7+ есть и число $4qr$, т.е. $\min(q,r)<\sqrt{n}/2$ (а в цепочках 12+ таких числа два).
Если же найденный делитель входит в первой степени (т.е. $r$), то придётся проверять дальше до $\min(p,q)<\sqrt[3]{n/r}$. А таких чисел в цепочке много, минимум 5 для цепочек 10+, и для них $r<6$.
А меньшие простые чаще появляются в разложениях, причём в первой степени намного чаще ...

Вот только откуда взялось само число $n$? Ведь насколько я понимаю мы наоборот перебираем все возможные комбинации простых $p,q,r$ (да ещё и в разных позициях цепочки) и смотрим подходит ли нам число $n=p^2qr$. И здесь уже нельзя перебирать $p,q,r$ лишь до $\sqrt[4]{n}$ или до $\sqrt[5]{n}$ или даже до $\sqrt[3]{n}$, потому что вполне могут найтись решения например с $p=31 \to n=31^2qr \to \min(q,r)<\sqrt{n}/31$, всего на полтора порядка меньше $\sqrt{n}$.

[VAL]

Почти пентадекатлон (без мечт )
$M(144)\ge 14$

(Оффтоп)

16822779398440180618906123085719853931945054017506556808284089262301370671602940

PS: Вернулся из командировки, а тут некий оживляж. Сейчас почитаю.

[Huz]

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

Я вообще не понимаю о каком числе или списке чисел идёт речь.

I think the "list of numbers" was from me, in the context of my code - it allocates various prime powers, then for each starting number up to the selected maximum that is consistent with those powers, checks if the residue has a factorization yielding the required number of divisors.

So in searching for $D(12,11)$ it may allocate a set of prime powers for the eleven values $[v_0, v_1, ..., v_{10}]$ like $[ 2\cdot 11^2, 13^2, 2^2 \cdot 3, 1, 2 \cdot 5^2, 3 \cdot 7^2, 2^5, 1, 2 \cdot 3^2, 5, 2^2 ]$. It uses CRT to determine that this pattern requires $v_0$ to yield a particular remainder $\pmod{2^5\cdot 3^2\cdot 5^2\cdot 7^2\cdot 11^2\cdot 13^2}$. Then for each $v_0$ that has that remainder, up to our maximum, it checks if simultaneously $\tau(v_0 / 242) = 2, \tau(v_1/169) = 4, \tau(v_2/12) = 2, ..., \tau(v_{10}/4) = 4$. (There are additional checks to require that the allocated factor and the cofactor are coprime.)

The check for $\tau(v_i) = t$ involves a mix of strategies oriented around finding one prime-power factor at a time (along with primality checks and power checks); it handles $t=1$ separately, otherwise it sorts the values to check, so that any $t=2$ are first checked for primality; next any $t \equiv 1 \pmod{2}$ are checked as squares or higher powers; finally, any other values are checked in parallel.

Yadryara asserts that it should be possible to speed up this process by taking advantage of the assertion that no $v_i$ is of the form $p^2 q^3$. But I suspect that is based on an assumption either that I would explicitly generate numbers with such a signature to test them, or that the $\tau()$ checks would explicitly test for such signatures; in fact neither of those is (mostly) the case.

There are cases where the code allocates $q^3$ so that the cofactor is required to be of the form $p^2$, and those cases could potentially be skipped; however it allocates those only for a subset of small $q \le k$ (where $k$ is the length of chain), and these cases are optimized such that very little time is spent on them. For $D(12, k)$, the bulk of the time is spent in cases where some $p^2$ is allocated, and we want to know if the cofactor has 4 divisors.

I hope that helps to clarify what we are talking about. :)

[Yadryara]

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

Yadryara asserts that it should be possible to speed up this process by taking advantage of the assertion that no $v_i$ is of the form $p^2 q^3$. But I suspect that is based on an assumption either that I would explicitly generate numbers with such a signature to test them, or that the $\tau()$ checks would explicitly test for such signatures; in fact neither of those is (mostly) the case.

Это я давно уже понял.

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

There are cases where the code allocates $q^3$ so that the cofactor is required to be of the form $p^2$, and those cases could potentially be skipped; however it allocates those only for a subset of small $q \le k$ (where $k$ is the length of chain), and these cases are optimized such that very little time is spent on them.

Вот именно. Very little time.

Я писал ещё на 4-й странице:

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

Ну а на что, по-Вашему, нужно умножить $17^2$, чтобы получить число, имеющее $12$ делителей? Можно на куб простого, но таких чисел очень мало. Остаётся произведение двух простых.

Но если можно выиграть very little time, то почему бы не сделать это?

Dmitriy40, помнится, Вы летом приводили расчёт, что на минимизацию 12-ки уйдёт год. А сколько уйдёт на минимизацию 11-ки?

[Huz]

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

Но если можно выиграть very little time, то почему бы не сделать это?

I just tried one of the 32 patterns that specify a cube in a pattern such that it is the only example of a square cofactor, it took 7.42s to run. Writing this answer has already taken more time than it would take to run all 32. Writing code to look for this case so as to skip it would take longer still - and if that new code has a mistake, I might need to redo a week of calculations.

There are another 180 patterns that specify a cube such that there are multiple square cofactors. These are solved with a Pell equation, and take less than 0.1s to run.

So the maximum time that could be saved by skipping these is about 5 minutes in total.

There are 98 patterns that have no square cofactors; I've been running one of those for nearly 11 days now, and it is nowhere near halfway complete. If you have a suggestion that can make such patterns run 1% faster, that would actually save days on the eventual total runtime.

[Dmitriy40]

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

Dmitriy40, помнится, Вы летом приводили расчёт, что на минимизацию 12-ки уйдёт год. А сколько уйдёт на минимизацию 11-ки?

Быстро найти эту оценку не смог, а так не помню как прикидывал. Так что несколько сомневаюсь в её адекватности.
По 11-ке можно грубо прикинуть так: среди всех возможных паттернов без больших простых в квадратах (т.е. все проверяемые числа в цепочке только вида $q^2rp$ или $q^5p$ с неизвестным лишь $p$) есть 4шт с шагом/модулем 554400 (7 и 11 входят только в первой степени) с 5-ю проверяемыми числами в цепочке, значит до известной минимальной 11-ки примерно на 1e22 надо сделать 4*1e22/554400=7e16 попыток, при скорости счёта даже в 1e9 попыток в секунду (хотя вряд ли она достигается для 5-ти проверяемых чисел) это 72млн секунд или больше двух лет в один поток. Остальные паттерны имеют на порядок и более больше шаг/модуль, потому и времени потребуют на тот же порядок меньше и можно не учитывать.
Оценка грубая, по порядку величины, реально будет в несколько раз хуже (или лучше, что впрочем очень вряд ли).

Yadryara
Варианты цепочек длины 10+ с числами вида $q^3p^2$ проверил до 6e26, т.е. до наименьшей известной 13-ки. Дальше считать совсем уж долго. Цепочек длиной 7+ не нашёл вообще, только длиной 5 и 6.
Но дать гарантию отсутствия поостерегусь, не полностью уверен что правильно исключил все невозможные комбинации (которые пропускал при счёте).
Точно нет решений длиной 10+ до 6e26 с числами вида $q^3p^2$ при $q>58$ — такие были проверены самым наитупым способом (с очень незначительной оптимизацией). Для меньших $q$ использовались проверки по модулям и не уверен на 100% что с ними всё корректно. (To ALL: при желании кого помочь проверить выложу рассуждения, но это муторно - почему и опасаюсь что где-то "зарапортовался" и выкинул что-то лишнее.)

Дополнительно исследовал вопрос о наличии решений длиной 10+ с числами вида $p^2qr$ для $q,r<15$ — т.е. с искомыми большими простыми в квадрате на проверяемых местах (непроверяемые неинтересны потому что там найдутся любые возможные комбинации). Хотя сами по себе такие числа (с большим простым в квадрате) вроде как допустимы в паре десятков вариантов размещений в цепочках, но для цепочек 12+ почти все варианты исключаются тем или иным способом (и тоже полной уверенности нет, в принципе мог запутаться и исключить лишнее), а до 1.21e23 перебрал тупо и длинных (7+) цепочек не нашёл.
Для длин 12+ остался только один возможный вариант с $15p^2$ на месте 32p-1, он проверен до 3.5e25 на текущий момент, найдены лишь 5 штук maxlen=7 (все больше 2e24), длиннее нет. И если не ошибаюсь, то и такие цепочки кончаются на длине 13 (до наименьшей известной которой надеюсь допроверю), а 14+ быть не может.
Это позволит исключить много паттернов с простыми 5,7,11,13 только в первых степенях - как раз тех которые дают малые шаги/модули (без подстановок простых 17+), что сильно облегчит жизнь.

[Dmitriy40]

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

Кто-нибудь понимает, как работает программа Huz ?

После изучения любезно выложенного Demis-ом лога работы программы Hugo стало примерно понятно как тот действует:
1) перебирает все возможные варианты размещений малых простых в паттерне;
2) для каждого варианта перебирает все простые в квадрате при наибольшем коэффициенте в виде одного простого (т.е. для мест вида $p^2qr$ для любого фиксированного малого $q$ перебираются все $p<\sqrt{up/13}$, коэффициент $13$ зависит от паттерна и длины цепочек);
3) для каждого варианта по КТО вычисляются $n_0,m$ для формулы $n=n_0+im$;
4) перебираются все $i$ пока $n<up$ и проверяется полученное $n$ (не суть важно как именно).
Первый пункт мы выполняем в виде генерации групп паттернов.
Второй пункт мы ограничили лишь наименьшими допустимыми простыми, Yadryara (и с его подачи остальные) заморочился проверкой и всех прочих, но далеко не ушли.
Третий пункт у нас выполняется для каждого паттерна при компиляции ускорителей.
Четвёртый пункт в точности эквивалентен нашему перебору интервала с одним конкретным ускорителем (VAL тут действует так же, только без ускорителей).
Это примерная схема, остаётся несколько неясностей.
Например не вполне понятно почему происходит переход к пункту 3) когда ещё остаются места вида $p^2qr$ с известным $q$ (в частности $q=3$). Возможно перебор простых в квадрате плюс КТО слишком медленно и выгоднее перебирать линейно $n$ (хотя для одного неизвестного КТО вроде бы сводится к одному умножению и сложению по модулю (т.е. фактически делению) если заранее подготовлены обратные элементы). В логах видны переборы по $i$ почти до 4e9 с 7-ю проверяемыми местами (где осталось найти лишь одно большое простое), причём этот перебор занимает аж 4830с, т.е. скорость 8e5 попыток/с, это медленно, у меня с ускорителями перебор с меньшим количеством проверяемых мест (т.е. заведомо более медленный) идёт со скоростью 2e7 попыток/с (но правда это асм+SSE2/AVX2+PARI).
Второй непонятный момент: не видно проверяются ли паттерны с неизвестным $p$ и известными $q,r$, например те же $15p^2$ на месте 32p-1. Возможно просто логи ещё до дошли до таких ...
Третий непонятный момент: не видно проверяются ли паттерны с числами вида $p^2q^3$. Возможно эта проверка выполняется между 2) и 3) и в лог не попадает по причине своей быстроты.
Четвёртый момент понятный, но странный: в логах семёрка входит в пятой степени, неужели во второй уже всё проверено?! Это же основная масса работы, получается доказательство близко к финишу?
Hugo, explanations on above are not required, I believe that you have everything right and ambiguity only because of the limited logs and my laziness to delve into the source code.

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.