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

[Dmitriy40]

Да чего тут писать, это ж просто: если считать числа с 1, то это номер проверки элемента цепочки, которая отбросила эту цепочку. А сами числа - сколько таких цепочек было отброшено именно i-й проверкой.
Самое левое число - сколько цепочек было отброшено первой же проверкой чисел цепочки.
10-е число - сколько цепочек было отброшено ровно 10-й проверкой проверкой чисел цепочки.
Единица в 19-й позиции означает что одна цепочка была отброшено ровно 19-й проверкой чисел цепочки, т.е. предыдущие 18 проверок оказались успешными и 18 чисел цепочки подошли. И значит valids точно не меньше 18.
Искомое решение никогда не отбрасывается и потому в список не попадает.

Ну и так как цепочки отбрасываются по первому же несовпадению, то и valids не подсчитывается и он может быть и выше чем позиция в [] - просто до следующих проверок дело и не дошло, а они могли дать правильное значение.

В каком порядке проверяются числа цепочки - не знаю, разбираться откровенно лень.


Huz, since people want it so badly, consider adding a key to output to the log and chains with n or more successful checks (with some kind of left-hand code at the beginning of the line and indicating which check dropped the chain), because it's not difficult.

[Yadryara]

Картина Репина "Приплыли" Сам автор не понимает как работает его программа в простейшем случае?

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

Huh, that is strange, I will investigate how it can report more cases than there are numbers.

Понятно. [5 1 1] это, оказывается, неправильно. Вы что даже не тестировали для простейших примеров?

Ну вот не зря говорил, что надо разбираться детально. Проверять, а не верить на слово. Нужно было самые короткие цепочки сначала проверить. А мы тут про valids=19 разговаривали.

А какие 3 числа должны быть в квадратных скобках по Вашей задумке?

[5 0 1] ?
[5 1 0] ?
[6 0 0] ?

Или какие-то ещё варианты?

Вы же для чего-то добавили вывод этой информации. Надеюсь, не для того, чтобы людей запутывать.

____________________________________________________________________
Repin's painting "They've Arrived" The author himself doesn't understand how his program works in the simplest case?

Huz in message #1719240 писал(а):

Ha, that's weird, I'll figure out how it can report more cases than there are numbers.

I see. [5 1 1] turns out that's wrong. Didn't you even test it on the simplest examples?

Well, I was right when I said we need to look into it thoroughly. Don't take my word for it. You should have checked the shortest chains first. And were we talking about valids=19 here.

And what three numbers should be in square brackets, according to your plan?

[5 0 1] ?
[5 1 0] ?
[6 0 0] ?

Or some other options?

That's why you added this information. I hope it wasn't to confuse people.

[Huz]

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

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

C:\pcoul\new>pcoul.exe -x1:6 4 3
001 pcoul(4 3) -x1:6 *RT*
367 coul(4, 3): recurse 1, walk 2, walkc 7 (0.00s) [5 1 1]

Huh, that is strange, I will investigate how it can report more cases than there are numbers.

Oh, I can only reproduce this with release 20251121 and older, the two 2026 releases both give me:

001 pcoul(4 3) -x1:6
367 coul(4, 3): recurse 2, walk 2, walkc 4 (0.00s) [3 0 1]

.. and sensible results all the way up to "-x1:33" giving "[13 2 3]".

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

Huz, since people want it so badly, consider adding a key to output to the log and chains with n or more successful checks (with some kind of left-hand code at the beginning of the line and indicating which check dropped the chain), because it's not difficult.

Agreed, I tried to add this already but got stuck trying to show the pattern of valids; better to add something simpler now.

[Yadryara]

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

and sensible results all the way up to "-x1:33" giving "[13 2 3]".

Переводит как "разумные результаты". И эти разумные результаты и есть правильные результаты?
__________________________________________________________________
It translates as "reasonable results." And are these reasonable results the correct results?

[Huz]

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

The author himself doesn't understand how his program works in the simplest case?
[...]
Didn't you even test it on the simplest examples?
[...]
You should have checked the shortest chains first.
[...]
That's why you added this information. I hope it wasn't to confuse people.

I make the software I write freely available in the hope that people will find it useful. The source code is also available for you to inspect to determine if it meets your admirably high standards. In the general case, though, sarcasm is unhelpful and does not translate well.

Цитата:

Are these reasonable results the correct results?

To the best of my knowledge both the old code and the new code were correctly reporting the numbers that had been tested. The old code was testing more numbers than it should when run with a low value of the '-f' option (default 0), which was a case known to be buggy that for a long time I suggested users should avoid; I believe the two recent releases fix all known problems with low values of '-f'.

The old and new code both report the same results when run with the traditionally safe value of '-f' (largest prime $p \le k$):

% ./pcoul -x1:6 -f3 4 3
001 pcoul(4 3) -f3 -x1:6
367 coul(4, 3): recurse 3, walk 3, walkc 3 (0.00s) [1 1 1]
% 

[Yadryara]

Huz
Thank you. There was no sarcasm on my part.

[Yadryara]

Скачал уже казалось бы самую новую версию. Пересчитал для D(4,3):

Проверка                Прибавка
От 1 до        0 1 2       0 1 2    Сумма

      1       [1 0 0]      1            1
      2       [1 0 0]                   1
      3       [2 0 0]      1            2
      4       [2 0 0]                   2
      5       [3 0 0]      1            3
      6       [3 0 1]          1        4
      7       [4 0 1]      1            5
      8       [4 0 2]          1        6
      9       [5 0 2]      1            7
     10       [5 0 2]                   7        
     11       [6 0 2]      1            8
     12       [6 0 2]                   8
     13       [7 0 2]      1            9
     14       [7 0 2]                   9
     15       [7 1 2]        1         10
     16       [7 1 2]                  10
     17       [8 1 2]      1           11
     18       [8 1 2]                  11
     19       [9 1 2]      1           12
     20       [9 1 2]                  12
     21       [9 1 3]          1       13
     22       [9 1 3]                  13
     23      [10 1 3]      1           14
     24      [10 1 3]                  14
     25      [11 1 3]      1           15
     26      [11 1 3]                  15
     27      [11 2 3]        1         16
     28      [11 2 3]                  16
     29      [12 2 3]      1           17
     30      [12 2 3]                  17
     31      [13 2 3]      1           18
     32      [13 2 3]                  18
     33      [13 2 3]                  18

Единственные чётные числа, на которых происходит прирост, это 6 и 8. Посмотрю ещё другие количества делителей.

-- 02.03.2026, 06:44 --

D(96, 19) найдена! Моим компом, на котором работали всего лишь 8 потоков.

См. ниже.

[Yadryara]

$\tikz[scale=1.5, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=green!70!violet!100!, white] {\color{yellow}\Huge\textbf{D(96, 19)}} }$

$\tikz[scale=.57, transform shape, font=\fontsize{11}\selectfont, black!70!]{ \node at (4.79,10)[shading=ball,ball color=red!70!violet!100!, white] {\color{yellow}\Huge\textbf{83249599403652415669870228237450726343942320967741813929974}} }$

[wrest]

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

См. ниже.

(Оффтоп)

83249599403652415669870228237450726343942320967741813929974

Для тех, кто захочет проверить.

[Yadryara]

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

Что дальше делать... Теперь уже привык что-то считать и не люблю когда сильно долго (больше недели) комп простаивает.

192 делителя это вроде слишком много. К тому же искать 20-ку интереснее и солиднее, чем 15-ку. Уже посмотрел паттерны: можно сразу, минуя 20-ку зарядить поиск D(96,21), а 20-ка может найтись попутно. Двусторонний дротик красноречиво об этом верещал

-- 02.03.2026, 10:59 --

Хотя нет, пожалуй, чтобы не пропустить цепочку, лучше таки искать 20-ку, уповая на то, что 21-ка сама соберётся.

[Dmitriy40]

Yadryara
Поздравляю!

-- 02.03.2026, 15:39 --

Мда, чувствую я опять слишком туманно описал подсчёт чисел в [].
Ну что же, тогда приведу алгоритм на PARI, как я его предполагаю:
q=vector(#v);
...
n=0; foreach(zz,d, n++; if(numdiv(x+d)<>48, q[n]++; break); );
После этого в q[] будут те самые числа из [].
В каком порядке смещения перечислены в zz[] - (мне) неизвестно. Возможно оно даже зависит от конкретного паттерна или (но вряд ли) от расставленных простых.
И если первое же смещение d (не обязательно наименьшее) не даст нужного количества делителей, то единичка добавится к q[1], хотя все остальные места цепочки могут быть и правильными и дать почти искомый valids.

[Yadryara]

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

Поздравляю!

И вам отдельное Спасибо, вы ранее тоже много помогали.

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

В каком порядке смещения перечислены в zz[] - (мне) неизвестно. Возможно оно даже зависит от конкретного паттерна или (но вряд ли) от расставленных простых.

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

Первая ласточка уже нашлась. Покажу её вместе с более слабыми приближениями — для иллюстрации метода.

                                                                                      2   2
                                                               12345                  4   8
10155866473107326880449030186812374239806885715635270357059573     1111111 11111 111111        18
42710084898169985338968105136116347278857189434666263345731573     1 1111 1 11111111 11   1    17
33444961212070223645645894698077998927340161266537541315446773     1 1111111111 1111 11        17
88693891379832968907667381990567431283282952895418667613353973    111 1 111111 1111 111        17

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

Факторизация таких огромных чисел уже занимает заметное время. Так что интерес к её оптимизации пока сохраняется.

[Dmitriy40]

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

Факторизация таких огромных чисел уже занимает заметное время. Так что интерес к её оптимизации пока сохраняется.

Как я это делал при поиске ещё больших чисел (скажем порядка 1e80), у Вас кстати мог остаться и готовый код например от M36n13:
заводим вектор флагов s[] что число цепочки точно не подходит или разложено полностью;
в простых фильтрах указываем какие числа полностью разложились чтобы не раскладывать повторно;
после простых фильтров запускаем разложение каждого недоразложенного числа на секунду (меньше нельзя) командой alarm() и проверяем разложилось ли оно;
если разложилось и не дало нужное количество делителей или и не может уже дать - тоже выставляем флаг;
если набралось много недопустимых чисел (т.е. valids точно мал и такие не интересны) - обрываем проверку;
повторяем разложение оставшихся чисел уже с ограничением на 3 секунды;
повторяем разложение оставшихся чисел уже с ограничением на 15 секунд;
повторяем разложение оставшихся чисел уже с ограничением на 90 секунд;
если valids оказался достаточно большим - запускаем полное разложение оставшихся чисел.

Вот пример цикла разложения цепочки с ограничением на 1с (указывается в alarm):

s=vector(#v);
...
for(d=1,#v,
   if(s[d]>0, next);\\Дораскладывать лишь оставшиеся числа
   if(type(alarm(1,factor(n+d-1)))!="t_ERROR",\\Дадим 1с на разложение
      s[d]=numdiv(n+d-1); if(s[d]!=nd, break);\\Если успело разложиться проверим подходит ли (numdiv выполнится моментально)
   ,
      f=factor(n+d-1,2^15); fn=matsize(f)[1];\\Не успело, проверим все ли делители найдены, до 2^15 проверяется очень быстро
      if(ispseudoprime(f[fn,1]), s[d]=numdiv(n+d-1); if(s[d]==nd, next, break));\\Если все, то проверим подходит ли число
      if(prod(i=1,fn-1,f[i,2]+1)>nd/4, s[d]=1; break);\\Если не все, то проверим не слишком ли много делителей уже найдено
   );
);

Разумеется для быстрой работы необходимо default(factor_add_primes,1).

При использовании alarm() стоит иметь в виду глюк с ней в PARI и почаще (несколько раз в сутки) проверять не вылетела ли программа.
Либо разобраться и подправить (под убунтой).

[DemISdx]

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

Yadryara
Поздравляю!

Yadryara
Присоединяюсь к поздравлениям!

(Оффтоп)

По поводу глюка.
Посмотрел:
https://pari.math.u-bordeaux.fr/faq.html
"Use alarm:"
Написано:

E      \\ this is a t_ERROR object

Т.е. объект возвращает.
И посмотрел:
https://pari.math.u-bordeaux.fr/dochtml/html-stable/Programming_in_GP__other_specific_functions.html
alarm({s = 0}, {code})
"The return value is the value of code if it ran to completion before the alarm timeout, and a t_ERROR object otherwise."
...
"We either return the factorization directly, or replace the t_ERROR result by a simple bounded factorization factor(N, 2^24). Note the factor_add_primes trick: any prime larger than 224 discovered while attempting the initial factorization is stored and remembered. When the alarm rings, the subsequent bounded factorization finds it right away."

Интересен трюк во втором примере с timefact().
Ну и Caveat Caveat2, конечно.

У Вас в строке:
"if(type(alarm(1,factor(n+d-1)))!="t_ERROR",\\Дадим 1с на разложение"
Вроде как не совсем по канонам получается...

Мало ли на свежие мысли наведет.
Еще переписка их:
https://pari.math.u-bordeaux.fr/archives/pari-dev-1406/msg00003.html

[Yadryara]

DemISdx, Спасибо!

Мы аларм обсуждаем в теме про быстрые программы.