2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 202, 203, 204, 205, 206, 207, 208 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 12:21 
Аватара пользователя


29/04/13
7136
Богородский
Конкретика.

Вот тот самый мультипустой паттерн(b1165) :

[ 1, 12, 1, 242, 75, 32, 637, 18, 1, 20, 3, 2, 1]

Наименьший куар, который можно поставить на 27-е место — 3131.

Поставил. Теперь наименьший куар, который можно поставить на 39-е место — 8903.

Поставил. Теперь наименьший куар, который можно поставить на 29-е место — 8917.

Поставил. Теперь наименьший куар, который можно поставить на 35-е место — 72451. Он единственный меньше 200 тысяч.

Ставлю и его:

[ 3131, 12, 8917, 242, 75, 32, 637, 18, 72451, 20, 3, 2, 8903]

Совершенно очевидно, что этот паттерн с огромным LCM порядка 1e25 проверится за долю секунды.

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 12:29 
Аватара пользователя


11/12/16
13195
уездный город Н
Ага, теперь понятно.
То есть расставляя $qr$ в одну позицию, мы получаем дополнительные ограничения на оставшиеся.

У меня бродили такие смутные мысли :wink:, но не вылились в конкретику. Впрочем, у меня эти мысли были вокруг расстановки $p^2$ всё таки.

Что касается идеи с расстановкой $qr$, даже расстановки двух будет достаточно для быстрой, моментальной проверки.
Так как получим Пёлль-подобное уравнение.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 15:24 


05/06/22
292
Yadryara I'm not quite sure what you are aiming at with the new focus on $qr$. If the idea is to avoid the need to iterate over all large $p^2$ by instead iterating over the possible $qr$, then it may be of interest to consider at what value the expected number of primes $p$ balances the expected number of semiprimes $qr$.

For known upper limits of $D(12,k)$, using $|p \le n| = n/\ln{n}, |qr \le n| = n \ln{\ln{n}}/\ln{n}$, I find the following results:

$k=12, p \le 71344704, |p| = 3945394$
$k=13, p \le 1228226700, |p| = 58685854$
$k=14, p \le 187746592315, |p| = 7232606363$
$k=15, p \le 649195465122, |p| = 23868358122$

Of course if a high proportion of the $qr$ can efficiently be rejected as impossible, then the balance changes; however it is not clear to me how you are rejecting them - could you clarify that please?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 16:17 
Аватара пользователя


11/12/16
13195
уездный город Н
Huz в сообщении #1578080 писал(а):
however it is not clear to me how you are rejecting them - could you clarify that please?


In each pattern ($sq=0$) there are fixed numbers that are multiples: 32, 9, 25, 7, 11 and 13.
However, numbers of the form $p^2$ do not have all possible remainders in these modules.
And from this it follows that $qr$ cannot have all possible remainders with respect to these modules. This means that some of them are forbidden (for a specific pattern and for a specific location in the pattern).

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 16:18 
Аватара пользователя


29/04/13
7136
Богородский
Huz

Huz в сообщении #1578080 писал(а):
Of course if a high proportion of the $qr$ can efficiently be rejected as impossible, then the balance changes; however it is not clear to me how you are rejecting them - could you clarify that please?

I check modules. This check is effective only for factors of prime squares. If you understand PARI/GP, I can publish the program.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 16:34 
Заслуженный участник


20/08/14
11073
Россия, Москва
EUgeneUS в сообщении #1578087 писал(а):
In each pattern (sq=0) there are fixed numbers that are multiples: 32, 9, 25, 7, 11 and 13.
However, numbers of the form $p^2$ do not have all possible remainders in these modules.
Реализовал это на асме+PARI (перебор всевдопростых с проверкой по этим модулям для каждого возможного варианта из всех паттернов), перебор $p^2$ идёт вдесятеро быстрее чем на чистом PARI, вместо 22ч оценка 2ч на одно qr (от паттернов не зависит, влияет на все). Надеюсь за несколько часов проверятся все 22<qr<600 (-p1e12).

Yadryara в сообщении #1578041 писал(а):
Так вот, есть надежда, что таких комплектов из 3-4 куаров будет не шибко много и удастся быстро проверить все мультипустые паттерны.
И всё же, почему бы не проверять места с одним простым? Ведь туда сильно меньше разных qr расставляется, ведь свобода перебора только по одному простому, а не по двум как на пустых местах.
Вообще да, очень интересная идея, потребовать правильных qr (разных) на всех местах ...

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 17:26 
Аватара пользователя


29/04/13
7136
Богородский
Dmitriy40 в сообщении #1578091 писал(а):
И всё же, почему бы не проверять места с одним простым?

Я пока не дошёл до этого. То есть ещё не думал над этим.

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

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 17:43 


05/06/22
292
EUgeneUS в сообщении #1578087 писал(а):
In each pattern ($sq=0$) there are fixed numbers that are multiples: 32, 9, 25, 7, 11 and 13.
However, numbers of the form $p^2$ do not have all possible remainders in these modules.
And from this it follows that $qr$ cannot have all possible remainders with respect to these modules. This means that some of them are forbidden (for a specific pattern and for a specific location in the pattern).
Thank you, that is quite clear.

I was thinking this could be an interesting avenue to explore for speeding up the calculation of the minimum, but since the restrictions are location-specific it is not simply a question of preparing a single list of valid semiprimes. I assume that almost all primes $p$ have $(p-1)/2$ quadratic residues, so would expect roughly one in $2^6$ of the semiprimes to be valid in a single location; fixing one at that location would then leave about one in $2^8$ valid in a second location, and so on.

(In fact it is slightly better than that, since residues of $2^3$ and $3$ already give a 6-fold improvement.)

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 18:10 
Аватара пользователя


11/12/16
13195
уездный город Н
Huz
In general, I agree. But we can look at the problem from the other side.
Suppose, for simplicity,
a) we have 3000 patterns
b) each of them has 4 places to place $p^2qr$
c) We have limited $qr$ from above and consider the first 1000 options from them.

Then the number of location variants $qr$ will be:
$N = 3000 \cdot 4! \cdot C_{1000}^4 = 3000 \cdot 24 \cdot 41417124750 = 2982032982000000$

And modulo filtering will reduce this huge number by $64^4 = 16777216$ times.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 18:21 
Аватара пользователя


29/04/13
7136
Богородский
Huz в сообщении #1578097 писал(а):
so would expect roughly one in $2^6$ of the semiprimes to be valid in a single location;

Half as much(one in $2^7$) because we need to look at the module 64, not 32.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 18:32 
Аватара пользователя


11/12/16
13195
уездный город Н
Dmitriy40 в сообщении #1578091 писал(а):
Реализовал это на асме+PARI (перебор всевдопростых с проверкой по этим модулям для каждого возможного варианта из всех паттернов), перебор $p^2$ идёт вдесятеро быстрее чем на чистом PARI, вместо 22ч оценка 2ч на одно qr (от паттернов не зависит, влияет на все). Надеюсь за несколько часов проверятся все 22<qr<600 (-p1e12).


ЗдОрово!

Насколько понимаю, что это может сильно помочь в уменьшение времени для ограничения на простые в квадратах для доказательства минимальности 13-ки (а в перспективе 14-ки и 15-ки) - через более быстрое уменьшение порога в ключе -p.

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

Считаем "перспективными" паттерны с количеством проверяемых мест 10 и 11.
Таких есть
а) три группы с $LCM=7214407200$. Насколько понимаю, там и осуществлялся ранее поиск 14-к (или отдельно 14-к, или в рамках поиска 15-к).
Эти группы мы сейчас обсчитываем с DemIS'ом, с ключом -p500.
Цель обсчитать их до 21e31, что примерно в 10 раз меньше, чем минимальная известная 14-ка.
б) три группы с $LCM > 7214407200$. Эти обсчитываются у меня в один поток. Цель та же - обсчитать их до 21e31.
Это всё не быстро. Но сроки выглядят приемлемыми (единицы месяцев).

в) и есть три группы паттернов с $LCM < 7214407200$
А вот с ними проблемы. Оценки для худшего LCM дают время расчета около 13 млн. секунд (полгода) с тем же ключом: -p500. Для одного паттерна.
Меня гложут смутные сомнения, что вероятность найти цепочку в этих паттернах все таки не настолько велика, насколько велико прогнозируемое время расчета. Но каких-то идей, уменьшить время расчета для них пока нет :-(

-- 20.01.2023, 18:33 --

Yadryara в сообщении #1578105 писал(а):
Half as much(one in $2^7$) because we need to look at the module 64, not 32.


Тут у Хуго верно.
Проверка по каждому модулю уменьшает количество $qr$ примерно в два раза (для конкретного места в конкретном паттерне).
А разным модулей - 6 штук. Итого в $2^6$ раза.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 18:44 
Аватара пользователя


29/04/13
7136
Богородский
EUgeneUS в сообщении #1578107 писал(а):
Проверка по каждому модулю уменьшает количество $qr$ примерно в два раза (для конкретного места в конкретном паттерне).
А разным модулей - 6 штук. Итого в $2^6$ раза.

А вы сами-то проверяли?

Существует 8591 $qr$ до 100 тысяч. Согласны?

Я нашёл только по 68 подходящих на 29-е и 39-е места. В 126 раз меньше. И это гораздо ближе к 128 чем к 64-м.

А сколько нашли вы?

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 19:09 
Аватара пользователя


11/12/16
13195
уездный город Н
Yadryara в сообщении #1578110 писал(а):
А вы сами-то проверяли?

Нет, выкладки теоретические. Если модули взаимно просты, то они работают "независимо".

Yadryara в сообщении #1578110 писал(а):
Я нашёл только по 68 подходящих на 29-е и 39-е места. В 126 раз меньше. И это гораздо ближе к 128 чем к 64-м.


Насколько понимаю, речь о конкретном паттерне. В котором 11 и 13 в квадратах.
Это несколько улучшает "фильтрацию по модулям". Но не в два раза.

Но применение модуля $64$ не должно улучшить фильтрацию по сравнению с модулем $32$.

Согласен. Применение модуля $64$ улучшает фильтрацию в два раза, по сравнению с модулем $32$:
$p^2$ даёт 8 вариантов по модулю $64$, а нам нужен ровно один.
$p^2$ даёт 4 варианта по модулю $32$, а нам нужен ровно один.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 19:19 
Заслуженный участник


20/08/14
11073
Россия, Москва
Yadryara в сообщении #1578041 писал(а):
Так вот, есть надежда, что таких комплектов из 3-4 куаров будет не шибко много и удастся быстро проверить все мультипустые паттерны.
Как-то она не очень оправдывается: для этого (b1165) паттерна с qr<60000 есть 584 варианта расстановки таких qr по 4-м пустым местам. Из них 18 вариантов с 3131 на левом месте, вот парочка из них:
[3131,12,6613,242,75,32,637,18,51811,20,3,2,36623]
[3131,12,49573,242,75,32,637,18,1411,20,3,2,15503]

EUgeneUS в сообщении #1578107 писал(а):
ЗдОрово!

Насколько понимаю, что это может сильно помочь в уменьшение времени для ограничения на простые в квадратах для доказательства минимальности 13-ки (а в перспективе 14-ки и 15-ки) - через более быстрое уменьшение порога в ключе -p.
Как-то оно не особо помогает, уменьшение порога до 2e12 заняло 3.5ч и до 1e12 собирается уменьшать ещё часов 10. А при уменьшении порога количество разных qr быстро растёт, соответственно падает и скорость уменьшения -p, примерно квадратично (т.е. типа сутки до 3e11 и неделю до 1e11).

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение20.01.2023, 19:23 
Аватара пользователя


11/12/16
13195
уездный город Н
О!
Эту идею можно распространить и на другие модули.
Например, проверять не по модулю $9$, а по модулю $27$. Тогда
а) всего остатков - 11 штук.
б) остаток $0$ исключается и из знаменателя, и из числителя.
в) остаётся $10$ остатков, из которых подходит только один.
Итого фильтруем $1/10$, а не $1/3$, как при применении модуля $9$.

-- 20.01.2023, 19:25 --

Dmitriy40 в сообщении #1578117 писал(а):
Как-то оно не особо помогает, уменьшение порога до 2e12 заняло 3.5ч и до 1e12 собирается уменьшать ещё часов 10. А при уменьшении порога количество разных qr быстро растёт, соответственно падает и скорость уменьшения -p, примерно квадратично (т.е. типа сутки до 3e11 и неделю до 1e11).


ИМХО. А дальше применять при расчете конкретных паттернов. А-ля, увеличить скорость "W-стадии". Нет?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3216 ]  На страницу Пред.  1 ... 202, 203, 204, 205, 206, 207, 208 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group