Как писать быстрые программы

[Yadryara]

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

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

Очевидно: чтобы wresta не грузить этими вычислениями.

По моему одна строка простых вычислений проще длинных таблиц и подготовки файла.

Я не понимаю что Вы хотите сказать. Почему одно с другим сравнивается?

Мне нужно было показать wrestу числа. Как они вычисляются, wrest знать не желает и только что ещё раз это подчеркнул.

Поэтому я взял самые маленькие числа-кандидаты из программы (при i=0) и показал 42 из них. Также для тестов подготовил файл, куда записал уже побольше таких чисел.

Насколько понял, wrest тесты по этим числам не проводил. Я провёл их сам.

[wrest]

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

Не знаю зачем Yadryara выкладывает список чисел, их же легко получить по формуле n=n0+i*m с некими n0 и m (ну потом ещё поделить (n+d-1)/v[d], d=[1..22] чтобы получить именно факторизируемые числа).

Давайте ещё раз по задаче ускорения факторизации пройдём. Подтвердите что я правильно понимаю.
Есть какие-то предварительные вычисления (которые мы пока не обсуждаем тут), в результате которых получаются два числа n0;m (переменные) и константа len
n0 число-"кандидат", первый член арифметической прогрессии
m - "шаг арифметической прогрессии"
len=22 - константа, количество членов арифметической прогрессии, не меняется в процессе вычисления (равно 22 при поиске D(48,22) например)

Есть так же постоянный (константа) проверочный вектор (массив) длиной len, который содержит
- количество делителей, ожидаемое у членов арифметической прогрессии (Yadryara называет его kdel)
или
- количество различных простых множителей, ожидаемое у членов арифметической прогресси (Yadryara называет его nu)

Цель: проверить нет ли среди членов арифметической прогрессии таких, что количество их делителей не соответствует kdel (или количество различных простых множителей не соотвествует nu).

Всё верно? Если да, предлагаю сделать "эталонный набор" из пар n0;m на котором и проверять эффекты ускорения.

Для определения размера эталонного набора, прошу сообщить какая сейчас примерная скорость проверки одного "кандидата" n0, то есть всех членов $a_i$ одной арифметической прогрессии $a_i=n_0+i\cdot m, i=1..22$, сколько кандидатов проверяется в секунду (или какой темп - сколько секунд на кандидата)?

Должна ли проверка (возможно, многоэтапная) обязательно закончиться точным результатом "подходит/не подходит"?
Какие имеются априорные знания о кандидатах и образуемых ими арифметических прогрессиях?

[Yadryara]

Отвечу пока на часть вопросов, зато быстро. Длиннющий термин "арифметическая прогрессия" предлагаю выбросить за ненадобностью, а говорить цепочка или кортеж. Это просто сплошной отрезок натурального ряда.

wrest в сообщении #1711508 писал(а):

Цель: проверить нет ли среди членов арифметической прогрессии таких, что количество их делителей не соответствует kdel (или количество различных простых множителей не соотвествует nu).

Да. Но первая задача для простоты обычно сводится ко второй.

А если наоборот, количество делителей в точности равно искомому, то главная задача выполнена — найдена искомая цепочка ( D(48,22) ).

[Yadryara]

wrest в сообщении #1711508 писал(а):

n0 число-"кандидат", первый член арифметической прогрессии

У меня в программе n0 это так называемая добавка, вычисляемая по КТО, а первое число цепочки это n.

wrest в сообщении #1711508 писал(а):

m - "шаг арифметической прогрессии"

У меня m это шаг перебора по простому числу.

wrest в сообщении #1711508 писал(а):

Если да, предлагаю сделать "эталонный набор" из пар n0;m на котором и проверять эффекты ускорения.

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

Оставшиеся вопросы надо как-то переформулировать. Хотя, возможно, Дмитрий ответит.

В остальном верно.

[wrest]

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

Да. Но

OMG... да но нет, не совсем, наверное

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

первая задача для простоты обычно сводится ко второй

в моём тексте нет описания что такое "первая задача" и что такое "вторая задача"
Давайте про тонкости "количество делителей", "количество различных простых множителей", "кратность делителей" то есть
$\omega (n)$ отсюда: https://ru.wikipedia.org/wiki/%D0%9F%D1 ... 0%BB%D1%8C
а также про $\sigma _0(n)$ отсюда: https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 0%B5%D0%B9
и про $\mu (n)$ отсюда https://ru.wikipedia.org/wiki/%D0%A4%D1 ... 1%81%D0%B0
и их взаимосвязь поговорим чуть попозже.

[wrest]

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

У меня в программе n0 это так называемая добавка, вычисляемая по КТО, а первое число цепочки это n.

Хорошо, тогда задача - ускорить проверку "цепочки" на соответсвие количества делителей каждого слена
Цепочка это 22 последовательных числа, начиная с n, т.е. $a_i=n+i, i=0...len, len=21$
Но тем не менее, мы ожидаем различное количество делителей для различных $a_i$ в соответствии с этим (под арифметической прогрессией понимаем $a_i=n+i, i=0...len, len=21$):

wrest в сообщении #1711508 писал(а):

Есть так же постоянный (константа) проверочный вектор (массив) длиной len, который содержит
- количество делителей, ожидаемое у членов арифметической прогрессии (Yadryara называет его kdel)
или
- количество различных простых множителей, ожидаемое у членов арифметической прогресси (Yadryara называет его nu)

Цель: проверить нет ли среди членов арифметической прогрессии таких, что количество их делителей не соответствует kdel (или количество различных простых множителей не соотвествует nu).

Верно?

Если нет, напишите уже ясно - что ускоряем? В смысле, какой-то конкретный этап всего вычисления, где сосредоточена основная масса факторизаций

[Dmitriy40]

wrest
Есть число $n$, полученное откуда-то (по формуле, из файла, с потолка).
С него начинаются 22 числа кортежа: $a_i=n+i-1, i=1\ldots22$ (можно и с нуля, но в PARI удобнее так).
Нужно чтобы все они имели ровно 48 делителей (numdiv=$\sigma_0$).
И вот эту проверку, что все имеют 48 делителей, и надо ускорить.
Причём так как такие цепочки/кортежи исключительно редки, то важнее быстро находить причину отбросить кортеж и перейти к другому $n$, чем убедиться что все числа имеют 48 делителей. Т.е. найти любую ошибку важнее проверки правильности всех чисел.

Но! Вы же понимаете что среди этих 22 числе будут чётные? Т.е. какие-то из них уже содержат как минимум 2, а также и 4 и 8 и 16 и 3 и 9 и 5 и 7 и 11 и 13 и 17 и 19, в разных комбинациях. Плюс некоторые другие простые, помещённые туда насильно (причина пока не столь важна). Разумеется при этом $n$ перестаёт быть произвольным числом и на него накладывается много ограничений, но это тоже к делу не относится.
Вот такой список/массив/вектор чисел уже содержащихся в $a_i$ и называем v[] ($v_i$).
Соответственно раскладывать на множители желательно не исходные $a_i$, а $a_i/v_i$, ведь часть множителей мы уже точно знаем, они скомпонованы в v[]. И потому в частных (22 штуки) количество ожидаемых делителей разное, оно указывается в nu[] (если как omega). И тут мы пока плюём на высшие (больше первой) степени.
Потому ускоряем проверку не на 48 делителей, а на nu[] разных простых делителей (omega), но не исходных чисел $a_i$, а частных $a_i/v_i$. Можно считать что они уже нам заданы как $r_i=a_i/v_i$ и брать просто вектор r[].

[Yadryara]

Ну вот, Дмитрий как раз объясняет математику задачи. Частично. И правильно делает. Говорил уже об этом. Если человек расспрашивает, значит надо вникать.

wrest в сообщении #1711527 писал(а):

Хорошо, тогда задача - ускорить проверку "цепочки" на соответсвие количества делителей каждого слена

Что ещё за слен? Член, может?

Да, задача ускорить проверку "цепочки. Искать возможности как можно быстрее отбрасывать негодные.

[Dmitriy40]

wrest в сообщении #1711508 писал(а):

Для определения размера эталонного набора, прошу сообщить какая сейчас примерная скорость проверки одного "кандидата"

Под кандидатом понимаем одно конкретное число $n$, с которого начинаются 22 последовательных натуральных числа.
Сейчас у меня 100000 кандидатов (разных n) проверяются четырьмя циклами с factor(x,porog) с порогами 2^12,2^14,2^17,2^20 за 4.8с и остаётся 20 вероятно подходящих кандидатов (чисел n).

Код PARI для получения и проверки с factor() всех этих 100000 чисел n:

default(factor_add_primes,1);\\Для ускорения factor()
v=[63, 3610, 3179, 12, 17797, 3362, 75, 392, 841, 18, 2209, 20, 1587, 242, 6727, 96, 14045, 338, 243, 68, 35131];
n0=283938699868309713921641266159023371777169;
m=229403502054304075118105309394590566946400;
nu=[3, 2, 3, 3, 3, 3, 3, 2, 4, 3, 4, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3];\\Сколько разных простых делителей должно быть в каждой позиции
kpod=q=0;\\Счётчики
t0=getwalltime();\\Замер времени
for(i=1,oo,\\Не знаю до какого индекса перебирать чтобы накопить 100000 кандидатов на проверку
   if(kpod==100000, break);\\Будем копить 100000 кандидатов на проверку
   n=n0+m*i*2;\\Получение числа начала кандидата
   if((n+#v-1)%3^6==21-19, next);\\Такие n не подходят
   if((n+#v-1)%5^3==21-7, next);\\Такие n не подходят
   if((n+#v-1)%7^3==21-8, next);\\Такие n не подходят
   if((n+#v-1)%11^3==21-14, next);\\Такие n не подходят
   if((n+#v-1)%13^3==21-14, next);\\Такие n не подходят
   if((n+#v-1)%17^3==21-3, next);\\Такие n не подходят
   if((n+#v-1)%19^3==21-2, next);\\Такие n не подходят
   kpod++; removeprimes(addprimes());\\Оставшиеся n подходят, будем их проверять и только такие учитываются в 100000

\\Здесь начинается проверка конкретного n
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^12); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^14); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^17); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
   foreach([1..#v],d, g=factor((n+d-1)/v[d],2^20); nf=matsize(g)[1]; if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2)); );
\\Проверка закончена, что осталось то осталось, подсчитаем сколько их и выведем в консоль для проверки

   q++;
   print(n);
);
print(kpod,"/",q,", time: "strtime(getwalltime()-t0));

При запуске выводит:

6467627468614808795443546523718456286724685969
10855657655909537144302664881818184651275425169
17837782644434335974597318078551943146856055569
17953860816473813836607079365105605973730933969
19384879862288562657193820285109061930342577169
19573908347981309215091139060050204557506410769
43326346950683953152819762794766111859136666769
45041367532041930418402718087800070937627953169
49421139193262703820557584654761594041768621969
52556626259340931919271848023566857910792017169
70629034151179006957076184297672702774829409169
86848779360426522284226702093107834220207674769
89313949393502073875445861747862104452613689169
92677922347626388832977758004824380526315698769
95685861066562423865926354821606252040116895569
96086399581149238781082566691809207170005309969
100372574613531856120589246292537737322831847569
112355237139836375180308359023454780996710105169
116404667758098950714293153944888093684447957969
123328524257101956309507808393035626176024202769
100000/20, time: 4,801 ms

-- 03.12.2025, 17:54 --

wrest
Ещё важный момент: нужно проверять именно много разных чисел n, не одно-два-три, важна скорость именно в среднем по большой выборке, ведь условия отбрасывания будут заметно различаться для каждого n. Потому 100000 (ну можно и 10000, но точность замера времени пострадает), а не 2.

-- 03.12.2025, 18:05 --

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

if(nf>nu[d], next(2)); if(nf==nu[d] && !ispseudoprime(g[nf,1],1), next(2));

Первый if проверяет что делителей больше необходимого, второй проверяет что уже сколько надо, но разложение не закончено и значит их точно больше необходимого.
Условия что их точно меньше необходимого здесь нет, с ним фильтруется ещё лучше. Можно добавить в конец каждого цикла foreach третье условие:
if(nf<nu[d] && ispseudoprime(g[nf,1]), next(2));
Тогда из 100000 остаётся лишь одно:
52556626259340931919271848023566857910792017169
100000/1, time: 6,726 ms
Зато время заметно больше.

Отмечу что это попалось найденное ранее D(48,21) при i=114550, в котором все 21 числа начиная с этого имеют ровно по 48 делителей. Так и задумывалось, v[] и nu[] и n0 были специально так выбраны. И это ещё один признак что всё работает правильно.

-- 03.12.2025, 18:27 --

Накладные расходы на получение всех 100000 кандидатов/n малы:
100000/100000, time: 377 ms
Это просто убрал все 4 цикла проверок.

-- 03.12.2025, 18:52 --

Пример предлагаемой мною проверки (заменяет все 4 цикла проверок с factor):

   nf=vector(#v,d,1); nn=vector(#v,d,1);\\Вектор количества делителей (omega) и вектор накопления их для каждой позиции
   forprime(p=59,2^20,\\Проверяем делимость только на такие простые
      d=(n+#v-1)%p; if(d>=#v, next); d=#v-d; nf[d]++; nn[d]*=p;\\Получение остатка, проверка что он (и простое p) попадает в кортеж, накопление числа и самих делителей
      if(nf[d]>nu[d], next(2));\\Если уже перебор, то отбрасываем
      if(nf[d]==nu[d] && !ispseudoprime((n+d-1)/v[d]/nn[d],1), next(2));\\Если ровно сколько нужно проверим закончена ли факторизация и если нет - тоже отбрасываем
   );

Запуск для разных порогов вместо 2^20:
2^12: 100000/1271, time: 3,513 ms
2^14: 100000/357, time: 3,764 ms
2^17: 100000/68, time: 4,216 ms
2^20: 100000/22, time: 5,085 ms
Осталось 22 вместо 20, это не ошибка, в двух из них попалось лишнее простое меньше 59 (точнее оно оказалось в неправильной степени чем есть в v[]), factor это обнаружил и кортеж отбросили, эта проверка этого не обнаружила и посчитала в 22.

-- 03.12.2025, 19:22 --

Если хотим отбросить и степени выше первой, то после строки
if(nf[d]>nu[d], next(2));
добавляем проверку на квадрат:
if((n+#v-1)%p^2<#v, next(2));
Почему не до? Потому что простое сравнение быстрее деления и лучше кандидата отбросить сравнением nf с nu, чем делить длинное число на квадрат простого (а на квадрат потому что возвести малое число в квадрат быстрее чем поделить длинное число на малое, можно было бы задействовать divrem, но особого выигрыша не даст). Но деление точно намного быстрее проверки простоты, потому ту оставляем после этой проверки.
С такой проверкой время для порога 2^20 уменьшается до 5.018с.

-- 03.12.2025, 19:59 --

В этот код можно добавить и проверку что разложение завершилось и делителей меньше нужного, для этого после закрытия цикла forprime добавляем строку:
foreach([1..#v],d, if(nf[d]<nu[d] && ispseudoprime((n+d-1)/v[d]/nn[d]), next(2)); );
Она для случая когда делителей нашлось меньше нужного проверяет завершилось ли разложение и если да, то такие n не подходят. Здесь существенно что все высшие (больше первой) степени уже исключены!
Так из 100000 кандидатов остаётся снова ровно один, тот самый. Время возрастает несущественно, до 5.134с с порогом 2^20.

[wrest]

текст написан до ответа Dmitriy40 в предыдущем посте.

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

Вы же понимаете что среди этих 22 числе будут чётные?

Это я понимаю, и про чётные и про другие последствия того, что числа последовательные.

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

Плюс некоторые другие простые, помещённые туда насильно (причина пока не столь важна).

А вот это я предполагал, но не был точно уверен. Эти помещённые насильно точно есть? Какие и в каких членах "цепочки"?*

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

Соответственно раскладывать на множители желательно не исходные $a_i$, а $a_i/v_i$, ведь часть множителей мы уже точно знаем, они скомпонованы в v[].

Вот я тут пока сходу не уверен, учитывая вашу идею учитывать остатки при trial division и сразу вписывать найденные множители в разложения $a_i$ имея остаток от деления $a_0$ (оно же n). Мне тут наверное надо поразмышлять и поизобретать велосипед, на котором вы уже ездите эти годы.

Ну хорошо, пока за исключением вопроса выше помеченного * всё ясно. Во всех поисках, как я понимаю, речь о числах n в диапазоне 130-150 бит

Теперь, чтобы проводить более-менее чистый эксперимент:
1. Eсть ли у вас "эталонный" код на pari, который занимается только этой задачей: берёт на вход первое число цепочки, сколько должно быть делителей ($\sigma _0 (n)$, длину цепочки len (возможно, это параметр по умолчанию и равен 22) и возвращает 1 ("n подходит") или 0 ("n не подходит"). Возможно, этот код получает на вход так же и предвычисленный вектор $v_i$, ну или этот вектор тоже захардкожен.
2. Есть ли код на pari, который генерирует такое количество A начальных чисел n цепочек, что их проверка "эталонным" кодом занимает от 20 до 40 секунд? Каково это количество A?

[Dmitriy40]

wrest в сообщении #1711541 писал(а):

А вот это я предполагал, но не был точно уверен. Эти помещённые насильно точно есть? Какие и в каких членах "цепочки"?*

Точно есть. Простые 23...53, каждое в квадрате. Зависит от паттерна, для каждого своё.
Но это неважно и на суть (скорости разложения) не влияет.

wrest в сообщении #1711541 писал(а):

Вот я тут пока сходу не уверен, учитывая вашу идею учитывать остатки при trial division и сразу вписывать найденные множители в разложения $a_i$ имея остаток от деления $a_0$ (оно же n).

Остаток можно проверять от исходного числа n, оно не меняется при разложении, как не меняется и остаток, а только для isprime нужно число уже без найденных делителей. Я показал выше готовый код, там найденные остатки копятся в nn[] и потом для isprime удаляются из проверяемого числа (делением).

wrest в сообщении #1711541 писал(а):

1. Eсть ли у вас "эталонный" код на pari, который занимается только этой задачей: ...
2. Есть ли код на pari, который генерирует такое количество A начальных чисел n цепочек, что их проверка "эталонным" кодом занимает от 20 до 40 секунд? Каково это количество A?

Уже сделал сообщением выше, специально. Не совсем именно так как Вы пишете, но как оно реально работает.

[wrest]

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

Уже сделал сообщением выше, специально. Не совсем именно так как Вы пишете, но как оно реально работает.

Да, ваш код понятен.
Он работает слишком быстро при 10^5 кандидатов, увеличил до 10^6, время работы 35 секунд, из них генерация 3 секунды. Это интерпретация. Скомпилированное работает 29 секунд, из них генерация 2 секунды.
Будет эталоном

Но таки есть и вопрос. Вас устраивает, что 20 цепочек из 10^5 (или 185 из 10^6) остались нефакторизованными?
И ещё вопрос. Ну поскольку мы теперь знаем, что в этом эталонном наборе нет ни одной подходящей цепочки, надо бы придумать что-то такое, что будет считаться пренебрежимо мало времени, но покажет, что проверки реально отбросили неподходящие цепочки. Иначе вся функция может быть из одного только return(0)

[Dmitriy40]

wrest в сообщении #1711546 писал(а):

Вас устраивает, что 20 цепочек из 10^5 (или 185 из 10^6) остались нефакторизованными?

Да. Это ведь не весь рабочий код, в нём могут быть и дополнительные проверки, например factor(x,2^24), которая ещё сколько то отбросит. Или проверка на высшие степени. Или разложение всех чисел цепочки через numdiv и вывод в лог, который потом смотрим глазками или поиском по valids или по числу делителей.
20 чисел раз в несколько секунд конечно ещё многовато, лучше пару чисел/кандидатов в минуту чтобы торможение numdiv всех чисел цепочки на них уже не сказывалось на средней скорости, но на то есть ещё проверки.
Кроме того, я несколько раз дополнял своё сообщение с кодом, там есть и вариант когда от 100000 (и от миллиона) не остаётся ничего (кроме одного реального решения) - и это более чем устраивает.
От 10млн предлагаемой проверкой (с проверкой и высших степеней и меньшего количества делителей) за 9 минут остаётся 15 цепочек:

(Оффтоп)

52556626259340931919271848023566857910792017169: 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,  valids=21, i=114551
1797366169973077798872613587903651099882336242769: 96, 96, 48, 24, 48, 24, 48, 96, 24, 48, 24, 48, 48, 48, 96, 48, 64, 48, 96, 48, 24,  valids=10, i=3917478
3115348016571580612269358825334778922174542521169: 48, 96, 24, 48, 48, 64, 48,192, 48, 48, 24, 48, 24, 48, 48, 48, 48, 24, 24, 48, 48,  valids=13, i=6790106
3891338855181564074751317277737153125093514695569: 48, 48, 24, 24, 48, 48, 24, 48, 48, 96, 24, 48, 48,192, 32, 48, 48, 24, 48, 24, 24,  valids=11, i=8481429
5076702996049477810930436072017886929815141026769: 48, 48, 24, 24, 48, 48, 24,192, 24, 96, 12, 48, 48, 48, 96, 48, 48, 48, 96, 48,192,  valids=11, i=11065008
5104506700498459464834750435516511306529044706769: 48, 48, 96, 24, 48,192, 48,192, 48, 96, 12, 48, 48, 96, 48, 48, 48, 24, 96, 24, 48,  valids=11, i=11125608
7104478089091165885676758821351248322665998509969: 48, 48, 48, 48, 48, 96, 48, 48, 24, 96, 12, 24, 96, 96, 48, 48, 48, 48, 48, 48, 96,  valids=13, i=15484677
7454585455400370810175306892758134240679184119569: 24,192, 48,192, 48, 96, 96, 48, 48, 96, 12, 48, 48, 48, 24, 48, 24, 24, 48, 48, 48,  valids=11, i=16247759
7598686182829790132177045215275583883668833065169: 96, 96, 48, 48, 24, 48, 24, 48,192, 96, 24, 48, 96, 48, 24,192, 48, 48,192, 24, 48,  valids=9, i=16561836
7945988403115875026445049094959192748229398095569: 96, 48, 48, 24, 48, 48, 48, 48, 16, 24, 24, 48, 48, 48, 48, 48, 48, 48, 24, 48, 48,  valids=15, i=17318804
8002281269677976594830130720620912538271241298769: 48,192, 48, 48, 48, 24, 48, 48, 48, 48, 48, 24, 48, 48, 48, 96, 48, 48, 24, 24, 96,  valids=14, i=17441498
8379745462414161388894663086383722170573919001169: 24, 48, 96, 48, 48, 24, 48, 96, 48, 24, 12, 96, 48, 24, 48, 48, 24, 96, 48, 48, 48,  valids=11, i=18264206
8652543848531065840078409668524631067526167810769: 48, 48, 48, 24, 24, 48, 96, 48, 24, 48, 48, 24, 96, 48, 48, 96, 48, 48, 48, 48, 48,  valids=14, i=18858788
10830491062087542448478546515493879337311477661969: 48, 48, 48, 24, 48, 48, 24, 96, 24, 48, 24, 48, 48, 48, 24, 48, 24, 24, 96, 24, 48,  valids=11, i=23605767
11033364507936270365917393182067604294371660394769: 48, 48, 24, 24, 48, 96, 96, 48, 48, 48, 96, 24, 24, 96, 48, 96, 48, 48, 48, 24, 48,  valids=11, i=24047943
10000000/15, time: 9min, 8,356 ms

Можно взять и руками разложить любое число или даже любую цепочку и убедиться правильно ли они остались. Без подсчёта точного количества делителей (numdiv) для вывода в лог будет чуть быстрее 9 минут.

wrest в сообщении #1711546 писал(а):

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

Она есть, с i=114550, посмотрите внимательнее, её наличие это один из признаков что всё работает правильно.
Потому код и для известной D(48,21), а не не найденной пока ещё D(48,23).

wrest в сообщении #1711546 писал(а):

но покажет, что проверки реально отбросили неподходящие цепочки.

Это делалось по другому: выводим какие цепочки остались и изучаем их, почему они остались. Если ничего не осталось - убираем проверки по одной до получения оставшихся цепочек и проверяем их. Либо увеличиваем количество проверяемых кандидатов до получения оставшихся цепочек, но это менее надёжно.

[Yadryara]

Пока не разбирался в чём там дело, но 2-й способ проверки при 2^20 не показывает ни одной цепочки:

2^14   100000/357
...
2^17   100000/68
2^18   100000/44
2^19   100000/29
2^20

[Dmitriy40]

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

Пока не разбирался в чём там дело, но 2-й способ проверки при 2^20 не показывает ни одной цепочки:

Не понимаю что за "второй" способ.
Учитывая что все числа совпадают с моими, ищите опечатку в редакции 2^20.
Мои числа:
2^14: 100000/357, time: 3,868 ms
2^15: 100000/195, time: 4,038 ms
2^16: 100000/113, time: 4,161 ms
2^17: 100000/68, time: 4,343 ms
2^18: 100000/44, time: 4,543 ms
2^19: 100000/29, time: 4,838 ms
2^20: 100000/22, time: 5,135 ms
2^21: 100000/15, time: 5,525 ms
2^22: 100000/9, time: 6,209 ms
2^23: 100000/8, time: 6,931 ms
2^24: 100000/7, time: 8,440 ms

-- 03.12.2025, 20:48 --

wrest в сообщении #1711546 писал(а):

Он работает слишком быстро при 10^5 кандидатов, увеличил до 10^6, время работы 35 секунд, из них генерация 3 секунды. Это интерпретация. Скомпилированное работает 29 секунд, из них генерация 2 секунды.

Не понял, это с 4 foreach+factor или уже без них, только forprime?
Плохо что мало ускорение от компиляции. Надо разбираться можно ли что-то сделать.