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

[Huz]

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

Гексадекатлон нашелся!
Так что, $T(48,16) \le 41780573338629779703065418979464122604969472482834053115$, а $M(96) \ge 16$

Congrats. :)

By my count there are now just 82 values up to $M(100)$ for which we have no proof whether they exist or not. It does not seem likely to me that theory will push down the limit for any of 24, 48, 96, and even finding $M(36)<15$ seems unlikely; but there may still be room for theory to reduce limits for 60, 72, 84.

[mathematician123]

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

but there may still be room for theory to reduce limits for 60, 72, 84

Have you seen the proof of $M(84) \le 15$? It's in this post. The proof is based on lemmas 6 and 7 from this article. I can try to translate the proof If needed.

[Huz]

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

Have you seen the proof of $M(84) \le 15$? It's in this post. The proof is based on lemmas 6 and 7 from this article. I can try to translate the proof If needed.

No, I hadn't seen that - as far as I was aware, best known proof was $M(84) \le 21$. I'll try to take a look at this tomorrow (if the weather isn't too hot), and will let you know if I have any difficulties with translation.

I've taken a quick look: lemma 6 is slightly problematic, since it starts "since $8x^2 \equiv 24 \pmod{32}$ has no solutions, a run of 23 consecutive integers each with 12 divisors ...", but ends with "thus [...] $M(12) \le 15$". It should be recast to say "since $8x^2 \equiv 24 \pmod{32}$ has no solutions, a run of 16 consecutive integers each with 12 divisors ..." (must include both $n_0$ and $n_8$, etc). It would be useful to show a variant of this that explicitly extends it to $12(2m+1)$ divisors.

With this more general version of lemma 6, is lemma 7 still necessary? If so, explaining why it is would be instructive.

[Yadryara]

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

Гексадекатлон нашелся!

Проздравляю

И также поздравляю Hugo с весьма немаленьким количеством находок, о которых он скромно умолчал в теме.

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

Это сообщение открыло 100-ю страницу темы

Как и было предсказано. А количество правок 1-й страницы всего-то 86.

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

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

Разница между 11050х и 750х — видимо плата за множество паттернов.

Тут я не прав, это плата за слишком слабую проверку на простоту в ускорителях.

Спасибо. Но можно ли как-то поподробнее?

Например, что такое слишком слабая проверка на простоту в ускорителях ?
В тех подклассах, что я проверяю сейчас, экзешные проги, судя по файлу .INC проверяют делимость на простые до 4093.

[EUgeneUS]

Huz
Hugo, FYI, in the our project in the Papeeria there is the prof for the more general theorem:
$M(k) \le 15$, where $k=12t$, and $t >5$ is prime.

But, it's in the "russian folder", we didn't translate it to the English yet.

[mathematician123]

Huz
I think it would be better if I write the proof without referring to Lemmas 6 and 7.

Proof. If $n \equiv 24 \pmod{32}$ or $n \equiv 16 \pmod{32}$, then $\tau(n) \ne 84$. Therefore, any run of 16 consecutive integers with 84 divisors must occur within consecutive integers $n_{25}, n_{26}, n_{27}, n_{28}, n_{29}, n_{30}, n_{31}, 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}, n_{15}$, where $n_i \equiv i \pmod{32}$. Hence it follows that numbers $n_0, n_1, n_2, n_3, n_4, n_5, n_6, n_7, n_8$ belong to the run.

From $\tau(n_8) = 84$ it follows that $n_8 = 8x^2$. Therefore, $3 \mid n_6$ or $3 \mid n_8$.

1) Suppose $3 \mid n_8$. Then $9 \mid n_8$. Therefore, $n_2$ is divisible by 3, but not divisible by 9. Then $n_2 = 6y^2$ and $n_8 = n_2+6 = 6(y^2+1)$, which is impossible since $9 \mid n_8$.

2) Suppose $3 \mid n_6$. Then $3 \mid n_0$. From $\tau(n_6) = 84$ it follows that $n_6 = 2py^2$, where $p \ge 3$ is prime and $y \equiv 1 \pmod{2}$. Then $8x^2-2 = 2py^2$, $(2x+1)(2x-1) = py^2$. $2x+1$ and $2x-1$ are coprime and cannot both be divisible by $p$. Therefore, $2x \pm 1 = z^2$. If $2x = z^2-1$, then $2 \mid x$, which is impossible. Suppose $2x = z^2+1$. Let $z = 2w+1$. We get $x = 2w^2+2w+1$. From $n_8 - 8 = n_0$ we get $n_0 = 32w(w+1)(w^2+w+1)$. $n_0$ has at least 3 distinct prime divisors, since $w$, $w+1$, $w^2+w+1$ are pairwice coprime. Now we need to consider possible factorizations of $n_0$. Note that $64 \cdot 3 \mid n_0$. $n_0 = 2^a 3^b q^c$ or $n_0 = 2^a 3^b q^c r^d$, where $q, r$ are primes, $a, b, c, d$ can be determined from $\tau(n_0) = 84$. $w$, $w+1$ or $w^2+w+1$ is not divisible by $p$ and $q$. Therefore, $w$, $w+1$ or $w^2+w+1$ equals $2^{a_1}3^{b_1}$, where $a_1, b_1$ can be determined from $\tau(n_0) = 84$.

-- 21.07.2022, 08:01 --

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

Note that $64 \cdot 3 \mid n_0$. $n_0 = 2^a 3^b q^c$ or $n_0 = 2^a 3^b q^c r^d$, where $q, r$ are primes, $a, b, c, d$ can be determined from $\tau(n_0) = 84$. $w$, $w+1$ or $w^2+w+1$ is not divisible by $p$ and $q$. Therefore, $w$, $w+1$ or $w^2+w+1$ equals $2^{a_1}3^{b_1}$, where $a_1, b_1$ can be determined from $\tau(n_0) = 84$.

For example, let $n_0 = 2^6 3 q r^2$. Then $w(w+1)(w^2+w+1) = 6qr^2$. $w$, $w+1$ or $w^2+w+1$ is not divisible by $p$ and $q$. Therefore, $w \le 6$.

[Huz]

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

For example, let $n_0 = 2^6 3 q r^2$. Then $w(w+1)(w^2+w+1) = 6qr^2$. $w$, $w+1$ or $w^2+w+1$ is not divisible by $p$ and $q$. Therefore, $w \le 6$.

I assume "not divisible by $p$ and $q$" (twice) should be "not divisible by $q$ or $r$". If I correctly worked through the various cases, overall I find $w \le 18$, and the rest of the proof all looks good to me.

I've always found it very inconvenient that A292580 is defined as a chain of exactly $k$ rather than at least $k$ consecutive integers - my code, originally developed for A165501, finds chains of at least $k$, so for rare cases such as $T(6,8) > T(6,9)$ I need to do extra work. But having found $T(42,4)$ means as a bonus it has already checked all $w < 141876$ for any possible $T(42,16)$.

[VAL]

Huz

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

No, I hadn't seen that - as far as I was aware, best known proof was $M(84) \le 21$

All news of this topic are regularly recorded on the first page.

[VAL]

$M(432) \ge 8$

(Оффтоп)

231574760818231098812797517235901847235358032562848211568545352077609136940798

[Dmitriy40]

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

Спасибо. Но можно ли как-то поподробнее?

Например, что такое слишком слабая проверка на простоту в ускорителях ?

Провёл дополнительное исследование, вот что получается.
Запуск исходной программы VAL (с незначительными изменениями):
N=37832460/16879458/1298669, 229.467s (228.791s in PARI) per round 603914e35.
Здесь 37832460 кандидатов осталось после исключения модулей 2 и 3 (это делается неявно выбором $p_0$ и $m$ в формуле $p_0+im$), именно столько передано на проверку индексов; 16879458 кандидатов осталось после проверки индексов и передано на первую isprime; 1298669 прошло первую isprime и передано на длинный if; всего ушло 230с (секундная погрешность это дефекты PARI); проверенный интервал 1e35.
Скорость проверки по длинному if (расходы на вывод результатов игнорирую, туда попали всего один раз из более чем миллиона) составила примерно $1298669/229\times11/10=6238$ кандидатов в секунду (коэффициент 11/10 учитывает что проверок в if всего 10, а время считается для 11-ти проверок плюс циклы).
Скорость проверки всех 11-ти мест составила примерно $16879458/229=73709$ кандидатов в секунду.
В "натуральном" выражении скорость проверки составила $10^{35}/229=4.37\cdot10^{32}$ в секунду или 991e3 шагов/попыток в секунду.

Запуск ускорителя по тому же паттерну фактически в той же программе (только циклы и вычисление $n=p_0+im$ заменены):
N=226994743464/1973614/335311, 156.011s (37.362s in PARI) per round 603e38.
Здесь 226994743464 всего попыток; 1973614 кандидатов вернулось из ускорителя; 335311 из них прошли проверку первой isprime (аналогично программе VAL) и передано на длинный if; всего ушло 156с, из них на долю PARI 37.4с; проверенный интервал 1e38.
Коэффициент фильтрации $226994743464/1973614=115015$.
Расчётное время 11-ти проверок всех 226994743464 попыток без ускорителей составило бы $226994743464/73709=3.08\cdot10^6$ секунд, что в 19740 раз больше 156с с ускорителями.
Разница 19740х и коэффициента фильтрации 115015 на 72% объясняется большим временем работы ускорителя.
Разница 3080c (для интервала 1e35) и 229с объясняется наличием во втором случае фильтрации по модулям 2 и 3 и индексам, ведь на первую isprime приходит уже в $226994743/16879458=13.45$ раз меньше кандидатов.
Скорость проверки по длинному if составила примерно $335311/37.4\times11/10=9862$ кандидатов в секунду, в 1.6 раза больше программы VAL.
Скорость проверки всех 11-ти мест составила примерно $1973614/37.362=52824$ кандидатов в секунду, в 1.4 раза меньше программы VAL.
Отличие этих двух скоростей от программы VAL иллюстрирует недостаточную адекватность таких оценок скорости.
В "натуральном" выражении скорость проверки составила $10^{38}/156=6.41\cdot10^{35}$ в секунду или 1.455e9 шагов/попыток в секунду, ускорение от программы VAL составило 1468х.

Запуск ускорителя для более коротких интервалов проверки:
N=22699474348/196860/33212, 15.428s (3.775s in PARI) per round 6039e37.
N=2269947437/19624/3316, 1.563s (0.436s in PARI) per round 60391e36.
N=226994746/1961/345, 0.222s (0.093s in PARI) per round 603914e35.
N=22699476/170/41, 0.091s (0.062s in PARI) per round 6039142e34.
N=2269949/14/2, 0.075s (0.046s in PARI) per round 60391422e33.
N=226996/2/1, 0.073s (0.047s in PARI) per round 603914228e32.
Как видно линейность сохраняется лишь до интервала (круга) 1e36, на меньших интервалах резко возрастает влияние накладных расходов и погрешности измерения времени.
Для используемого интервала 1e35 скорость в "натуральном" выражении снижается c 6.41e35 до 4.5e35 или лишь 1030х от программы VAL. Разница между 1468х и 1030х именно из-за недостаточно большого интервала (круга, step) проверки, накладные расходы на множество ускорителей сюда ещё не включены, тут ускоритель ровно один.

Но из этой кучи цифр так и непонятно почему при коэффициенте фильтрации 115015 до проверки на простоту скорость повышается лишь в 1468 раз. Будем разбираться.
Для начала отмечу что в программе VAL тоже присутствует фильтрация (только не внешними ускорителями, а прямо в коде PARI) и фильтрует она в 13.45 раз (в 6 раз учётом модулей 2 и 3 выбором $p_0$ и $m$ в формуле $n=p_0+im$ и в 2.24 раза по индексам). Этим преимущество ускорителей снижается примерно в 13.45 раз, с 115015 до 8551 раза.
Далее, ускорители выполняются не мгновенно, а за 118.6с, этим коэффициент снижается ещё в $156/37.4=4.17$ раз, до 2048.
На что списать разницу между 2048х и 1468х я не знаю.

Есть соблазн списать это на то что после первой (и вероятно каждой) isprime количество кандидатов в программе VAL уменьшается в 13.45 раз, а с ускорителями это же количество уменьшается только в $1973614/335311=5.9$ раза, т.е. дальше на длинный if проходит относительно больше кандидатов и соответственно проверка каждого несколько замедляется. Несмотря на якобы бОльшую скорость проверки длинного if, думаю это огрехи метода измерения скорости. Для проверки этого предположения разделил цикл проверки на три с сохранением промежуточных результатов в массив и замерил время каждого этапа — время на фильтрацию (13.45х в PARI для программы VAL или 115015х в ускорителях) + время на первую isprime + время на длинный if:
N=37832460/16879458/1298669, 245.193s=34.634s+197.849s+12.710s per round 603914e35.
Программа VAL, скорость первой isprime $16879458/197.8=85336$ в секунду, скорость длинного if $1298669/12.71=102177$ в секунду, их отношение $85336/102177=0.8352$.
N=226994743464/1973614/335311, 156.982s=119.681s+32.098s+5.203s per round 603e38.
Ускоритель, скорость первой isprime $1973614/32.1=61483$ в секунду, скорость длинного if $335311/5.20=64482$ в секунду, их отношение $61483/64482=0.9535$.
Ну, скорость всех isprime явно ниже и если с длинным if это ещё хоть как-то понятно, то почему замедляется одна первая isprime не совсем ясно (возможно из-за отсутствия малых делителей ей приходится выполнять больше работы).
В итоге предположение верно, скорости isprime меньше, а не больше, выше то был артефакт метода измерения.
Эффективная скорость проверки всех 11 мест в программе VAL составила $16879458/(197.85+12.71)=80165$ кандидатов в секунду, с ускорителями $1973614/(32.1+5.20)=52912$ кандидатов в секунду, в 1.515 раза меньше, что уменьшает выигрыш ускорителей с 2048х до 1352х вместо реальных 1468х. Вот они и нашлись. А разницу 1352х vs 1468х спишу на погрешности и разницу в коде.


Резюмируя, превращение коэффициента фильтрации 115015 в ускорение всего лишь 1030х получается из-за следующих факторов:
1. В программе VAL тоже есть быстрая (15% общего времени) фильтрация с коэффициентом примерно 13.5.
2. Ускорители выполняются не мгновенно и даже не 15% общего времени, а скорее 76%.
3. Ускорители проверяют простоту чисел не точно, потому относительно больше кандидатов проходит через каждую isprime, что увеличивает время проверки и снижает скорость.
4. Величина круга (step) 1e35 недостаточна для нивелирования накладных расходов, лучше бы её делать раза в три больше (разумеется пропорционально увеличится время проверки всех паттернов).

[VAL]

$M(324)\ge 8$

(Оффтоп)

14838204548865794066564147584822253497617184436611341528665979599909903737856824737311442930487474507518

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

Все время забываю (поскольку никак не соберусь изучить обобщение своих же лемм ):
$M(k)\le 15$ проходит (после конечного числа проверок) для $k$, кратных 12, но не кратных ни 5, ни 24
или для $k=12p$, где $p$ простое, отличное от 2 и 5.

[mathematician123]

Huz
Thanks for checking the proof!

VAL

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

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

Пока доказано только $M(324) \le 21$.

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

Все время забываю (поскольку никак не соберусь изучить обобщение своих же лемм ):
$M(k)\le 15$ проходит (после конечного числа проверок) для $k$, кратных 12, но не кратных ни 5, ни 24
или для $k=12p$, где $p$ простое, отличное от 2 и 5.

В случае, когда $k \equiv 12 \pmod{24}$ и $k$ не делится на 5, доказано следующее:
1) $M(12t) \le 15$, где $t$ - простое, отличное от 2 и 5. Это доказательство уже есть в Papeeria.
2) $M(108) \le 15$. Набросок доказательства тут.

Необходимость конечного числа проверок была в случае $k = 12t$, но в связи с появлением общего доказательства, это уже не актуально. В общем случае для любого $k \equiv 12 \pmod{24}$ и не делящегося на 5 оценку $M(k) \le 15$ пока доказать не удаётся. Но там во всех случаях получаются уравнения Пелля. То есть, если решения и есть, то они очень редки.

[VAL]

mathematician123,
Спасибо!

-- 22 июл 2022, 00:25 --

$M(432)\ge 9$

(Оффтоп)

20879311575533226738395292129967309619425241312389021801583298874745185210766358268

Как-то подозрительно быстро и восьмерка и девятка нашлись

[VAL]

$M(300)\ge 8$

(Оффтоп)

2559652074083521193602816028170310415442208225390370449451728355326910911691886887987411067130695098664639549008773118

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

[Yadryara]

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

Величина круга (step) 1e35 недостаточна для нивелирования накладных расходов, лучше бы её делать раза в три больше

Давным-давно уже делаю больше:

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

2e35 это интервал

В тот же день уже брал то ли по 4, то ли по 5e35 на круг. Затем не меньше чем по 8e35. А в последнее время уже 11e35 и больше увеличивать не стоит, ибо рекордная 14-ка имеет как раз такую величину.

Фрагмент переборной проги:

start=   0*10^33;\\Откуда начать
stop= 1100*10^33;\\Где закончить (не включая)
step=stop;\\

Ну а в большом ифе уже давно 2-ю и 3-ю проверку раскомментил. Количество находок уменьшилось, но зато скорость возросла аж на 3%

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