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

[Yadryara]

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

вот M84n11 компилились 2000шт/час как видно по датам файлов

У меня для 12 делителей компилятся по 4600 шт/час, но это всё равно не радует. Для последнего подкласса 11-228 10 часов на компиляцию и 53 часа на счёт.

А для первого самостоятельного подкласса 11-23 были те же 10 часов на компиляцию и чуть ли не 700 часов на счёт.
Так что близится момент переписывания кода. Сомневаюсь, что смогу сам его переписать.

[VAL]

Составил два базовых паттерна: на 21 и 22 числа по 48 делителей.
Протестирую и пришлю таблицы.

Без ускорителей оптимальное число проверок на простоту - 3. Насколько я понимаю, ускорители будут тем эффективнее, чем таких проверок будет больше (но без искусственного раздувания модулей за счет фиксации дополнительных множителей).
Пока в обоих вариантах сделал по 5 проверок на простоту.
Но для цепочки длиной 21 это удалось сделать за счет увеличения степени тройки и уменьшения количества позиций, в которых оставшийся сомножитель должен быть произведением трех простых (наиболее благоприятный случай). Возможно, лучше сделать паттерн на 4 простых, но избавиться от этих недостатков.

[Huz]

EUgeneUS в сообщении #1557787 писал(а):

Huz
The link to the pdf with draft (in Russian) of the whole proof was published in this post
Well, I'll try to translate it to English with some style corrections.

Thanks, I've started working through it - up to section 2.2 so far.

Translating from the PDF caused problems with the hyphens over line breaks, so I switched to the Google doc. It took me a while to realise that I was then in "edit" mode - I hope I didn't make any changes.

In "Terms", it seems worth spelling out the proof for items 10 and 11 - it hardly takes any more words to do so:
* $n_4$ cannot be in the chain, since 3 does not divide k; $n_6$ cannot be in the chain, since $\frac{n_6}{2}$ cannot be a square. Thus if $M(2pq) = 4$, the chain must include $n_0$ and $n_2$.
* $n_2 \not\equiv 1 \pmod{3}$ since B must be an integer, so 3 must divide either $n_0$ or $n_2$.

Item 15 in "Terms" translates as: "If the factorization of the number of divisors is known, then all possible factorizations of numbers that have exactly this number of divisors are known." Is the intended meaning here the same as "For a given k, each n must have one of an easily enumerable finite set of possible prime signatures"? If so, I'm not sure why you bother to say it, since you write out all the possibilities in section 2.1.

For section 2.2, it finishes with "The impossibility of other "exotic" variants of the factorization of $n_0$ is proved similarly", but I think it is probably worth spelling out the proof for $2^{pq-1}a$ - I imagine it is easy, but it has a rather different shape to the case that is treated in full.

[Dmitriy40]

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

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

вот M84n11 компилились 2000шт/час как видно по датам файлов

У меня для 12 делителей компилятся по 4600 шт/час, но это всё равно не радует. Для последнего подкласса 11-228 10 часов на компиляцию и 53 часа на счёт.

Да, это потому что порог малых простых меньше и разворачивание цикла в сотни раз, а не 32768 и тысячи, соответственно таблицы меньше и скорость их генерации выше. А вот скажем до переделки на внутреннюю генерацию самых больших таблиц файл .inc мог занимать до 53М (вместо сотни К сейчас) и компиляция всего одного паттерна могла занять до минуты! Т.е. всего полсотни шт/ч. А ещё незадолго до этого строки не накапливал в переменной, а сразу писал в файл, что резко замедляло запись (в десятки раз) и компиляция рабочего варианта (одного паттерна!) занимала десятки минут, приходилось всё отлаживать на урезанных вариантах ...
Компиляция варианта M32_x32_SSE в середине марта заняла вроде бы 4.5ч, т.е. примерно 10000шт/ч, что вполне соответствует разнице в скорости gp64 у меня и gp32 у Вас. Так что радуйтесь что для M12 оптимальным оказался вариант с 3584 простыми вместо максимально возможного и компиляция сотни тысяч паттернов (для новых M) не занимает неделю ... Ну и я радуюсь, пока.
На самом деле да, скорость компиляции не ахти, можно и нужно менять, уносить всё в asm, но это много переписывать и тестировать, а как известно "работает? ну и не трожь!" ...

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

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

Вот тут не понял, какого именно кода. M12mods1.gp Вам придётся менять кажется уже на следующей итерации (номер следующего простого станет больше 9 и всё собьётся), а Yadryara5.gen.gp и Yadryara6.asm менять почти не придётся (последний и для всех новых M ровно тот же). Ну там ближе к часу X решим.

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

оставшийся сомножитель должен быть произведением трех простых

Вот кстати ещё и это, сейчас-то PARI код перебора заточен под варианты только $p$ или $pq$, и я уже не совсем уверенно помню в каких именно местах, придётся аккуратно всё это искать/проверять ...

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

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

Покажите три паттерна (не группы), на 3, на 4, на 5 проверок, сделаю три программы и сравню скорость нахождения кандидатов на большом интервале — и будет понятно что выгоднее. Я бы предположил что выгоднее на 5 проверок, при этом больше действий переносится в более быстрый асм код, несмотря на уменьшение вероятности простых.

[Yadryara]

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

Так что радуйтесь что для M12 оптимальным оказался вариант с 3584 простыми

У меня простые до 4096.

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

Вот тут не понял, какого именно кода. M12mods1.gp Вам придётся менять кажется уже на следующей итерации (номер следующего простого станет больше 9 и всё собьётся),

Так у меня уже номер простого числа 67 равен 13. Но ничего не сбилось, потому что Вы мудро включили 16-ричную СС. Так что 13 это D.

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

а Yadryara5.gen.gp и Yadryara6.asm менять почти не придётся

У меня Yadryara5.asm

Я по-прежнему меняю только 37 на 41, 43, 47, ..., 67

Скоро надо будет уже на замену 31 переходить.

[EUgeneUS]

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

It took me a while to realise that I was then in "edit" mode - I hope I didn't make any changes.

Don't worry. There is right for reading only, not for writing.

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

In "Terms",

The "Terms" chapter is only memorandum, naming convention. Meaningful statement from it must be doubled in the text below.

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

For section 2.2, it finishes with "The impossibility of other "exotic" variants of the factorization of $n_0$ is proved similarly", but I think it is probably worth spelling out the proof for $2^{pq-1}a$ - I imagine it is easy, but it has a rather different shape to the case that is treated in full.

Thanks. I'll think about this and will answer later.

FYI. I am translating text to the English and planning to publish draft today, may be tomorrow. It'll be with the different presentation layout.

[VAL]

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

Покажите три паттерна (не группы), на 3, на 4, на 5 проверок, сделаю три программы и сравню скорость нахождения кандидатов на большом интервале — и будет понятно что выгоднее.

Я ровно так и делал (для 3-х и 4-х простых), когда искал 20-ку.

Цитата:

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

Я тоже исходил из этого.
Но сейчас, после тестовых прогонов и эмпирического замера мат. ожидания, засомневался. "Очко" удастся набрать, прогнав порядка двух квадриллионов цепочек. Многовато будет!
Сейчас попробую сделать на 4 простых, чтобы было с чем сравнить.

В прилагаемой таблице, как обычно, "типичный представитель". Квадраты простых в сиреневых клетках можно переставлять между собой, в красноватых - между собой. А еще можно все отзеркалить. Итого $24\cdot 24\cdot 2=1152$ набора.

[EUgeneUS]

Huz

English draft was published here. Some typos in the formulas was correctected also.

-- 18.06.2022, 17:47 --

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

For section 2.2, it finishes with "The impossibility of other "exotic" variants of the factorization of $n_0$ is proved similarly", but I think it is probably worth spelling out the proof for $2^{pq-1}a$ - I imagine it is easy, but it has a rather different shape to the case that is treated in full.

Yes, you're right. This is the hole in the proof instead of the whole proof
I think it can be closed basing on analogue of the "Лемма 1" in the Russian draft (Lemma 2 in the English draft).
The text needs to be added, of course.

[Dmitriy40]

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

Так у меня уже номер простого числа 67 равен 13. Но ничего не сбилось, потому что Вы мудро включили 16-ричную СС. Так что 13 это D.

Да? Ну хорошо, значит момент Ч немного откладывается.

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

У меня Yadryara5.asm

Зря, лучше сейчас заменить на Yadryara6.asm, пока ещё более-менее помним что за свой глюк я там исправил (и когда он проявлялся). А то задействуете код для других цепочек и полезут вдруг глюки ...

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

Я по-прежнему меняю только 37 на 41, 43, 47, ..., 67
Скоро надо будет уже на замену 31 переходить.

Это не должно приводить к проблемам, там же без разницы что на что менять (пока оно укладывается в рамки).

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

Я ровно так и делал (для 3-х и 4-х простых), когда искал 20-ку.
[...]
Но сейчас, после тестовых прогонов и эмпирического замера мат. ожидания, засомневался. "Очко" удастся набрать, прогнав порядка двух квадриллионов цепочек. Многовато будет!

Я про то что Вы не сможете адекватно сравнить реальные скорости выполнения с ускорителями без их наличия, даже оценив все вероятности, ведь скорость выполнения ускорителей тоже не константа и в разных условиях (тем более разное количество проверок) она может быть заметно разной. Даже если смоделируете работу ускорителя (что вообще говоря несложно, я делал для оценки качества фильтрации) и получите точные оценки вероятностей (и качества фильтрации и соответственно уменьшения вычислений в PARI), то смоделировать скорость работы ускорителя нельзя. Потому Ваши оценки скорее всего будут показывать правильную тенденцию, но вот конкретные величины могут быть далеки от реальности. Снова напомню странную ситуацию с 164 и 172 делителями, когда и 5 проверяемых чисел и 7 (т.е. все) дают схожую картину работы (различие максимум в несколько раз), никаких квадриллионов раз пока нет и близко.

[VAL]

Сделал схему паттернов на 4 проверки на простоту (вторая таблица в том же файле).
Всего (с учетом возможности отзеркалить) $6\cdot120\cdot2=1440$ наборов.
Требуемая цепочка в среднем должна возникать на порядок чаще. Важнее ли это замедления перебора судить не берусь.

[Yadryara]

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

Зря, лучше сейчас заменить на Yadryara6.asm, пока ещё более-менее помним что за свой глюк я там исправил (и когда он проявлялся).

Я ничего не помню. Может это как-то связано с потоками? Но у меня один поток. В общем если пришлёте, попробую заменить.

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

Это не должно приводить к проблемам, там же без разницы что на что менять (пока оно укладывается в рамки).

То есть чтобы считать 41 вместо 31 мне просто надо заменить bb=[5,37]; на bb=[5,31]; и взять r=[1,2,3,4,6,7] ?

[mathematician123]

Huz
Maybe you will also be interested. After EUgeneUS proof of $M(2pq) \le 3$, I proved the following statement: If $k \equiv \pm 2 \pmod{12}$ and $gcd(p_i-1) > 2$ ($p_i$ - odd prime divisors of $k$, $gcd(p_i-1) := gcd(p_1-1, p_2-1, \ldots, p_m-1)$ ), then $M(k) \le 3$.

[Huz]

EUgeneUS в сообщении #1557854 писал(а):

English draft was published here.

Thanks, it does help quite a bit not to have to rely on auto-translation. (I note that "Доказательство" is not translated for some reason, but I reasonably well recognise that now.)

[Dmitriy40]

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

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

Зря, лучше сейчас заменить на Yadryara6.asm, пока ещё более-менее помним что за свой глюк я там исправил (и когда он проявлялся).

Я ничего не помню. Может это как-то связано с потоками? Но у меня один поток. В общем если пришлёте, попробую заменить.

Я Вам в ЛС писал, что глюк проявляется если поставить порог простых больше 16384. И сразу же прикладывал новую версию, та ссылка уже протухла, вот снова: https://dropmefiles.com/U9G9U - достаточно положить .asm к предыдущему и поправить в .cmd везде где речь про Yadryara5.exe или Yadryara5.asm цифру в Yadryara5 на Yadryara6 (а файл Yadryara5.inc так и останется под номером 5 и править PARI программу не придётся).

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

То есть чтобы считать 41 вместо 31 мне просто надо заменить bb=[5,37]; на bb=[5,31]; и взять r=[1,2,3,4,6,7] ?

bb менять на самом деле и не обязательно. А вот менять r=[] как раз и надо. И всё.

[Huz]

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

Huz
Maybe you will also be interested. After EUgeneUS proof of $M(2pq) \le 3$, I proved the following statement: If $k \equiv \pm 2 \pmod{12}$ and $gcd(p_i-1) > 2$ ($p_i$ - odd prime divisors of $k$, $gcd(p_i-1) := gcd(p_1-1, p_2-1, \ldots, p_m-1)$ ), then $M(k) \le 3$.

Thanks, it sounds like a great result; for now, I'm particularly interested in satisfying myself that $M(70) = 3$ for the purposes of the A292580 a-file (which runs only to n=100), so I'm most eager to see whichever might be the simplest proof of that. :)