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

[Huz]

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

Huz
Another acceleration method.
As far as I remember, factor uses LCM to find divisors, ...

Assuming you mean "ECM" (the Elliptic Curve Method), if I understand what you are suggesting correctly I believe I already go beyond that.

Around coultau.c#L809 is the list of factorization methods, and at coultau.c#L879 is a table providing a bitvector of which factorization methods are appropriate to use for each range of sizes in the target numbers.

When a set of numbers is to be tested in parallel, each one is given an initial scan via tau_multi_prep() which can immediately reject it, then the full set is tested in parallel by tau_multi_run(): first each number is tested using method 0 (if its bitvector permits it), then each is tested with method 1, etc.

You can see at the first link that several of the "methods" are ECM trials each with its own particular set of parameters.

[Yadryara]

Мне всё-таки до сих пор непонятно почему Владимир решил, что мы скорее всего считаем одно и то же.

Вот факторизация найденной 19-ки. 8-я, 9-я и 11-я строки:

8-я [2, 1; 17, 2; 1397153, 1; 23345543927492088936661559574192977, 1]
9-я [3, 1; 11, 2; 14669467474790328749, 1; 3540420358932534150637, 1]
11-я [13, 2; 211, 1; 1327, 1; 398415036120273117058193915803254497, 1]

А вот карта моего досчёта:

                      8  9 11
24-19   2-10-7-8!    13-11-17       2 e43   Done     40320
24-19   2-10-7-8!    13-11-17z      2 e43   Done     40320
24-19   2-10-7-8!    17-11-13       2 e43   Done     40320   Found 19
24-19   2-10-7-8!    17-11-13z      2 e43   Done     40320
24-19   2-10-7-8!    13-17-11       2 e43   Today    40320
24-19   2-10-7-8!    13-17-11z      2 e43   Today    40320
24-19   2-10-7-8!    17-13-11       2 e43   Done     40320   VAL 1/70 — 576
24-19   2-10-7-8!    17-13-11z      2 e43   Today    40320

Видно в каком комплекте найдена 19-ка и в каком комплекте считал Владимир, обсчитывая при этом лишь не более одной семидесятой части этого комплекта.

[VAL]

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

Мне всё-таки до сих пор непонятно почему Владимир решил, что мы скорее всего считаем одно и то же.

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

Кстати, найденная 19-ка в мои 576 вариантов не попадала (я переставлял 19 - 31 между собой, а 37 - 47 тоже между собой).
Но вполне вероятно встретилась бы другая 19-ка. Я выполнил порядка 16% от первоначально запланированного перебора.

[Yadryara]

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

Кстати, найденная 19-ка в мои 576 вариантов не попадала

Ну да и это прямо следует из таблицы. Или Вы не понимаете что в таблице указано?

19-ка найдена в 3-м комплекте, а Ваши 576 полноприводных паттерна целиком были в 7-м комплекте.

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

Кстати, найденная 19-ка в мои 576 вариантов не попадала (я переставлял 19 - 31 между собой, а 37 - 47 тоже между собой).

Не понимаете, да? Это несущественно, даже если бы Вы переставляли все 8 простых 19 - 47 между собой, все эти паттерны — это всё равно 7-й комплект, а не 3-й. Потому что комплекты различаются между собой перестановками 11, 13 и 17 в квадратах.

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

Но вот непустое пересечение было.

Поначалу было, да. От силы 1/70-я. Потому что начинал я тоже с 7-го комплекта.

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

Но вполне вероятно встретилась бы другая 19-ка.

Конечно могла найтись. И она была бы 47-48-значной.

Поэтому, даже если бы Вы нашли 19-ку раньше меня, я собирался продолжать поиски среди 44-значных чисел.

[VAL]

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

Цитата:

Кстати, найденная 19-ка в мои 576 вариантов не попадала (я переставлял 19 - 31 между собой, а 37 - 47 тоже между собой).

Не понимаете, да? Это несущественно, даже если бы Вы переставляли все 8 простых 19 - 47 между собой, все эти паттерны — это всё равно 7-й комплект, а не 3-й. Потому что комплекты различаются между собой перестановками 11, 13 и 17 в квадратах.

- Данное число не может быть кратно 10, поскольку оно не делится на 2.
- Это несущественно! Оно не может быть кратно 10, поскольку не делится на 5.

[Dmitriy40]

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

Assuming you mean "ECM" (the Elliptic Curve Method),

Of course, I made a mistake.

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

if I understand what you are suggesting correctly I believe I already go beyond that.

Yes, if the rest of the threads stop when the first failure is detected, then you have already done what you have proposed, and even more. It beautiful.

[Huz]

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

Yes, if the rest of the threads stop when the first failure is detected, then you have already done what you have proposed, and even more. It beautiful.

Just to be clear: there are no threads involved. When I talk of doing things in parallel I mean that the single linear process does a little work on each number in turn rather than fully processing one number before starting on the next.

But yes, as soon as one number can be rejected it returns, so no more work is done on any of the numbers.

[Dmitriy40]

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

Just to be clear: there are no threads involved. When I talk of doing things in parallel I mean that the single linear process does a little work on each number in turn rather than fully processing one number before starting on the next.

It's very similar, yes.
It's not necessary to use separate threads, of course, but it's easier to organize everything this way.
But in my proposal, it is fundamental that even the ECM test (or any another) should not be completed if it is long enough, better do to look for a tuple location with faster verification and fast reject, there are often such places.

[Yadryara]

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

:-)

Да, смайлик уместен, потому что это не вполне релевантно. Ведь при счёте во всех других комплектах кроме 7-го, пересечения моего счёта с Вашим не было вовсе.

А кстати, понятно почему я называю Ваши паттерны полноприводными? Если нет, спрошу в "Игре слов".

Ну вот закончил обсчёт, подытожил и посчитал средневзвешенные valids.

2-10-7-8!                                   11.109                            0 —  2 e43
Valids   3  4  5   6    7    8    9   10    11   12   13   14   15  16  17 18 19   Total
Found    1  1  6  48  138  335  608  863  1013  921  704  388  161  50  13  4  1    5255

2-10-7-4!x4!                          10.895                                  0 — 70 e43
Valids   3  4  5   6    7    8    9   10    11   12   13   14   15  16  17 18 19   Total
Found       2  3  15   57  124  197  254   318  266  183   89   48  12   3  3       1574

То есть как видим 10.895 в полноприводных комплектах всё же меньше чем 11.109 в полных.

Видимо, объясняется это тем, что интервал счёта был в 35 раз больше.

А в одном и том же интервале считать, пожалуй, не стоило, ведь паттернов в 70 раз меньше и кандидатов намного меньше. Может и стоит провести отдельное исследование.

Допустим, что преимущество полноприводных и в самом деле есть. Но, как видим на практике, подъём в горы полностью и с запасом его убивает.

[Yadryara]

И ... тишина. Расчехление старого ГенПата не стал продолжать. Для D(24,20) написал новый. Результаты:

Старт    Делителей   Комплектов
полосы     2  4 8     паттернов

1          2-12-6           240
2          2-14-4           420
3          2-13-5           168
4          2-12-6           160
5          3-12-5            96
6          4-10-6           576

И ещё 8! или 9! перестановок. Остальные 6 стартов полосы — зеркальные.

Пока не брал для простых степени выше второй. Конечно кроме знаменитой 32.

[Yadryara]

Посчитал получше. Вот в более привычном виде:

Старт        Серия      Комплектов
полосы     паттернов     паттернов
1          2-12-6-8!           240
2          2-14-4-8!           420
3          2-13-5-8!           168
4          2-12-6-8!           160
5          3-12-5-8!            96
6          4-10-6-9!           576

Указано количество перестановок простых в квадратах именно из произвольной программы, то есть начиная с 23.

Здесь предположительно самые перспективные серии. Сначала выбиралась серия с наименьшим количеством простых, затем, при равенстве по этому показателю — с наименьшим количеством полупростых.

Влияние количества перестановок на перспективность пока не учитывалось.

Куб тройки вроде по-прежнему бесперспективен. Попробовал взять $3^5$. Стало только хуже:

Старт        Серия      Комплектов
полосы     паттернов     паттернов
1          3-11-6-8!          1152
2          3-11-6-8!           486
3          3-11-6-8!           126
4          3-11-6-8!           800
5          4-11-5-8!           304
6          4-11-5-9!           144

То есть вариантов с двумя простыми вообще не нашлось. Только с тремя и четырьмя.

По оргвопросам:

Как у меня пропало желание общаться с Макаровой 3 года назад, так оно и не появилось. (А с чего бы ему появиться — не извинилась не только передо мной, но и ни перед кем из нашего триумвирата.)

Тем не менее лично я помощь принять готов. Варианты:

1. Самый предпочтительный вариант. Я уже предлагал его ранее, когда у нас были трудности с поиском 19-252. Передать комп(ы) в управление кому-нибудь из нашего триумвирата.
Тогда и не надо будет общаться. Поблагодарю и в случае успеха упомяну имя.

2. Общаться через посредника. Хорошо, если gris согласится. Тем более что программа пока на PARI, а gris понимает его получше меня.
И, хотя по программе уже найдена 19-ка, она всё ещё довольно сырая. И предполагается многократно её улучшать.
Программа конечно же не лично моя, ибо в ней существенным образом используются идеи Дмитрия. Посему, пока не будет прямого согласия Дмитрия, я эту программу конечно не дам.

3. Какие будут предложения?

[Yadryara]

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

2. Общаться через посредника. Хорошо, если gris согласится.

Ну вот пример непонимания уже и последовал. Простым русским языком сказано:

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

И, хотя по программе уже найдена 19-ка, она всё ещё довольно сырая. И предполагается многократно её улучшать.
Программа конечно же не лично моя,

gris, понятно же что речь идёт о программе?

Программа сырая, а не 19-ка. А раз она сырая, то предполагается многократно её улучшать. Программу улучшать, то есть оптимизировать, искать пути ускорить её работу.

Как тут можно ухитриться неправильно понять эту простую фразу? 19-ка никакая не сырая, она в полном порядке. Да, можно попытаться её уменьшить, но я такой задачи не ставил, а ставил другую, о чём и писал:

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

D(24, 20) начала маячить где-то на горизонте.

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

Ну что, за двадцаточку возьмёмся?

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

Расчехление старого ГенПата не стал продолжать. Для D(24,20) написал новый.

И привёл серии паттернов, которые мой комп нагенерил по новой отдельной проге.

А для чего негенерил? Для поиска 20-ки, для чего же ещё. Вроде совершенно логично взять программу, которая нашла 19-ку и приспособить её для 20-ки. Ведь и количество делителей то же — 24 и минимальное количество простых пока то же — 2.

Вот и собираюсь заняться этой программой, а затем улучшать её. Кого её? Программу.

gris, всё ли понятно? Или может непонятно что такое ГенПат?

[Yadryara]

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

gris, всё ли понятно? Или может непонятно что такое ГенПат?

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

Итого, самые перспективные вроде такие:

Старт        Серия      Комплектов
полосы     паттернов     паттернов

1          2-12-6-8!           120
12         2-12-6-8!z          120
4          2-12-6-8!            80
9          2-12-6-8!z           80
__________________________________
                               400

То бишь всего 16 млн. паттернов. Хватит небось не только на 20, но и на двести потоков

[Dmitriy40]

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

И тот же вопрос к Дмитрию.

ГенПат очевидно генератор паттеррнов.
А вот что непонятно (или просто ещё не вдумывался): что за "Старт полосы" (и что за полоса)? что означает буква "z" (зеркальность что ли?)?

[Yadryara]

Да, конечно, Генератор Паттернов и зеркальные комплекты (z).

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

48-22   1-4-15-2-9!

      1112222222222333333333344444444
       8901234567890123456789
   2   1 2 1 3 1 2 1 5 1 2 1 
   3   1  2  1  1  5  1  1  2
   5      1    2    1    1   
   7   2      1      1      1
  11        1          2     
  13         2            1  
  17     1                2  
  19    1                  2 
_____________________________
23-59   2  22 2 2 2 2 2 2    
       pppppppppppppppppppppp
       qqqqqq qqqqqqqqqqqqqqq
        rrrrr rrrrr r rrr rrr
                  s     s

Есть поле шириной 31, специально отмечено заготовкой из 31-й цифры: "1112222222222333333333344444444".

И есть вертикальная полоса паттерна, в данном случае её ширина 22. Её прям прекрасно видно, потому что она заполнена цифрами и буквами. И эта полоса здесь стартует со 2-й позиции. То есть стартовая точка полосы паттерна равна 2. Это почти самое крайне левое расположение полосы.

Я же меняю не только числа в паттерне, но и двигаю полосу по полю слева направо, с самой первой позиции. В данном случае 22 по 31.