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

[Yadryara]

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

Угу. К счастью, это не арифметический запрет, а ошибка подсчета.

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

Не парьтесь с загрузкой, сумел увидеть через онлайновый Эксель.

[VAL]

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

Это да, но подозрение, что Вы их чуть ли не вручную составляете, укрепилось.

Конечно, вручную.
Как и для всех остальных сотен $k$, для которых построены цепочки.
Потом, конечно, проверяю программкой. Но составляю руками.

[Dmitriy40]

EUgeneUS
Yadryara
Вчера до меня дошло что я зря для 0 простых грохнул проверку по индексам (длинный if), он не позволяет возрасти степени размещённых простых, что применимо и для паттернов без простых.
Плюс в него же можно добавить и простые в квадратах, ровно с той же целью - не допустить возрастание степени. Ради скорости перебора.
Возврат длинного if и расчёта для него вектора bad[] ускоряет программу где-то втрое - но лишь для достаточно больших st, когда время проверки паттернов становится сильно больше времени генерации расстановки. У меня это происходит для st>100 вдвое, при st>1000 втрое (какой диапазон i перебирать для каждой расстановки).
В коде надо добавить две строки, одну до цикла forstep и одну после (вторая это длинный if, а первая вычисление остатков для него):
bad=vector(19); forprime(p=3,#bad, bad[p]=2^p-1; for(d=0,p-1, for(j=1,#v, if(((n0+m*d+j-1)/v[j])%p==0, next(2))); bad[p]-=2^d; ); );\\Довольно тупое вычисление запрещённых остатков
forstep(i=ii,ii+st-1,2,\\Это и так было
if(bittest(bad[3],i%3) || bittest(bad[5],i%5) || bittest(bad[7],i%7) || bittest(bad[11],i%11) || bittest(bad[13],i%13) || bittest(bad[17],i%17) || bittest(bad[19],i%19), next);
Пытался оптимизировать вычисление bad[], вроде там внутренний цикл по j не нужен, условие можно проверить проще, но что-то не получилось, пока оставил так.

Yadryara
Да, проверки по младшим модулям можно и объединить или переделать в проход по таблице, делать не стал.

EUgeneUS
Выше не про подсчёт статистики, а про программу поиска цепочки.
Я это к тому что оценка времени для паттернов без простых может и уменьшиться, раза в 3-4.

[Yadryara]

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

Плюс в него же можно добавить и простые в квадратах, ровно с той же целью - не допустить возрастание степени. Ради скорости перебора.
Возврат длинного if и расчёта для него вектора bad[] ускоряет программу где-то втрое - но лишь для достаточно больших st,

Здорово. У меня — в 2.8 раза. st у меня по старой практике огромный — 435920. Ускорение в 2.8 раза. За 5 с лишним секунд отрабатывает одну расстановку вместо 15.

VAL, понимаете что это значит. 0 простых и так выигрывали у 3-х простых, а теперь, с возвращением терапевтики, выигрывают ещё больше. А в расчёт 3-х простых нельзя вернуть терапевтику, она там и так была. И идеи ускорения на одном только PARI далеко не исчерпаны.

Правда, приближений по D(48,22) для 0-6-12-4-9! за полтора часа нашлось пока не густо — всего два. 49 и 51-значные.

Как понял, обратно поменять s[d]=numdiv(n+d-1) на s[d]=48 всё равно нельзя.

[Dmitriy40]

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

Как понял, обратно поменять s[d]=numdiv(n+d-1) на s[d]=48 всё равно нельзя.

Можно, но тогда придётся убрать условие s[d]==0 в последнем foreach([1..#v], который досчитывает неразложившиеся числа в цепочке и он их тогда корректно пересчитает, причём из-за default(factor_add_primes,1) это будет относительно быстро (не всё заново искать). Я не уверен как будет быстрее, потому что и так как есть и так как можно поправить каждое место будет разлагаться через numdiv лишь единожды и потому заметной разницы быть не должно, но надо бы проверить.

-- 22.10.2025, 15:44 --

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

Я не уверен как будет быстрее, потому что и так как есть и так как можно поправить каждое место будет разлагаться через numdiv лишь единожды и потому заметной разницы быть не должно, но надо бы проверить.

Был не прав, действительно быстрее - не все i доходят до финальной проверки, много отбрасывается и потому numdiv лучше делать как можно позже.
s[d]=48 не обязательно, можно любое ненулевое число. Во всех циклах кроме самого последнего конечно. Лучше даже просто s[d]=1 и тогда последний цикл сделать таким: foreach([1..#v],d, if(s[d]<2, s[d]=numdiv(n+d-1)); ), это позволит досчитывать лишь недоразложенные места, как и задумывалось.
Время на st=100 уменьшилось с 134c до 117с, -13%.

[VAL]

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

Ускорение в 2.8 раза. За 5 с лишним секунд отрабатывает одну расстановку вместо 15.
VAL, понимаете что это значит.

Не совсем. По мне, 1 вместо 15 - это замедление в 15 раз, а не ускорение в 2.8 раза.

[Dmitriy40]

VAL
Каждая расстановка стала проверяться не 15с, а 5с.

[VAL]

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

VAL
Каждая расстановка стала проверяться не 15с, а 5с.

У меня были подозрения, что трактовка такова.
Но был бы не я, если бы не прицепился к корявой формулировке.

Если же говорить серьезно, я пока не понял, как браковать числа, делящиеся на малые простые, если проверяемое число не обязано быть простым.
Отклонять делящиеся на произведения двух простых? Но это долго. Займет много памяти и может не дать выигрыша по времени.
Эффективнее искать НОД с произведением многих простых. Эта идея?
Извиняюсь, за свое неведение. Эти вопросы тут наверняка обсуждались.
Но я честно признался, что выпадал на время из дискуссии.

[Dmitriy40]

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

Если же говорить серьезно, я пока не понял, как браковать числа, делящиеся на малые простые, если проверяемое число не обязано быть простым.

Те простые что размещены в паттерне (2-19 или 2-53) - браковать как и обычно, чтобы остаток от на 1 большей степени не равнялся остатку от наибольшей размещённой степени (т.е. чтобы степень не повышалась). Так игнорируются цепочки с высокими степенями простых, но их слишком мало чтобы всерьёз на них рассчитывать.
Простые больше 53 - никак не забраковать, они имеют право встретиться на любых местах (кроме p если таковые есть).
Можно поделить на малые простые (скажем 59-1000) и проверить что остаток является простым. Это Ваша проверка по nu[] с factor(,300000). Которую лучше растроить с разными порогами (я обычно беру 2^14, 2^18, 2^24).
А больше собственно ничего и не сделать.

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

Эффективнее искать НОД с произведением многих простых. Эта идея?

Разница мизерна, скорее даже в пределах погрешности:

? n=0; m=2*3*5*7*11*13*17*19; for(i=1,1e8, n+=(gcd(i,m)==1)); n
time = 1min, 279 ms.
%1 = 17102401
? n=0; for(i=1,1e7, n+=(i%2<>0 && i%3<>0 && i%5<>0 && i%7<>0 && i%11<>0 && i%13<>0 && i%17<>0 && i%19<>0)); n
time = 1min, 311 ms.
%2 = 17102401

[Yadryara]

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

Но был бы не я, если бы не прицепился к корявой формулировке.

Ну я понял Тогда скажите, а зачем нам считать с ускорителями, если можно посчитать с замедлителями, а потом изловчиться и обратить (в свою маленькую веру).

Хоть и быстро считается, но очень мало приближений находится: всего 4 за почти 6 часов. Но... нашлось одно в топовую таблицу:

215061488180856945610675212184452970781283307745937     11 1111 11111111111 11             19

[Dmitriy40]

Мало приближений - значит хорошая фильтрация неподходящих.

[EUgeneUS]

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

В коде надо добавить две строки, одну до цикла forstep и одну после (вторая это длинный if, а первая вычисление остатков для него):
bad=vector(19); forprime(p=3,#bad, bad[p]=2^p-1; for(d=0,p-1, for(j=1,#v, if(((n0+m*d+j-1)/v[j])%p==0, next(2))); bad[p]-=2^d; ); );\\Довольно тупое вычисление запрещённых остатков
forstep(i=ii,ii+st-1,2,\\Это и так было
if(bittest(bad[3],i%3) || bittest(bad[5],i%5) || bittest(bad[7],i%7) || bittest(bad[11],i%11) || bittest(bad[13],i%13) || bittest(bad[17],i%17) || bittest(bad[19],i%19), next);

Тут проверяются плохие остатки для простых до 19.
У меня в одном из пробных запусков нашлась цепочка с $47^3$

[Dmitriy40]

Да, кубы не столь редки как кажется, но ведь в пару к ним тогда нужен и ещё квадрат, а вот такая комбинация уже совсем невероятна.
Вот если бы нашлась цепочка с 5-й или 11-й степенью вместо квадрата ...

-- 22.10.2025, 22:40 --

А учёт простых 23-53 не стал добавлять чтобы ещё больше не замедлять вычисление расстановки, не нравится мне там внутренний цикл, лишний он там, тормоз.