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

[Yadryara]

Dmitriy40, Спасибо, обдумаю.

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

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

Перепроверил и несколько переформулировал. Одиночное искомое простое в первой степени(single prime) обозначил через p.

Первое single prime — $32p$.

Ешё четыре single prime находятся там, где 2-ка в 1-й степени — $18p$ + $50p$ + ... + ...

Ешё три single prime там, где 3-ка в 1-й степени — $12p$ + ... + ...

Ешё два single prime там, где 5-ка в 1-й степени — $45p$ + ...

Ешё одно single prime там, где 7-ка в 1-й степени — $28p$ или ...


Итого: минимум 11 single prime.

Это важно было чётко прописать в интересах дела, то есть возможных попыток минимизации 12-15. У кого-нибудь есть возражения?

[EUgeneUS]

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

Итого: минимум 11 single prime.

Это важно было чётко прописать в интересах дела, то есть возможных попыток минимизации 12-15. У кого-нибудь есть возражения?

Это соответствует тем подходам для оценки количества single prime, которые писал выше. Так что 11 single prime - это минимум, если не искать $p^2$, для 12-15.

-- 14.07.2022, 18:09 --

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

Это решений не добавило.

Спасибо!
Это навело меня на некоторые размышления вот о чём.
Пусть $w+1 = q$, $w^2+1=p$ (или $w^2 +w+1=p$)

Тогда
1. если $w$ - перебираем линейно, то будет бесконечно случаев, когда $p, q$ - простые. Это гипотеза Шинцеля.
2. если $w = A B^n$ и линейно перебираем уже $n$, то можно выдвинуть следующие гипотезы
2.1. $q$ - простое. Имеем бесконечное количество случаев.
2.2 $p$ - простое. Имеем бесконечное количество случаев.
2.3. $p, q$ - простые (одновременно, при одном и том же $n$). Имеем конечное количество случаев.

Не знаю, это известная гипотеза или нет

-- 14.07.2022, 18:30 --

upd. эти гипотезы можно обосновать, но не доказать, из вероятностных соображений.

[Yadryara]

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

Промерять реальные ускорения мне лень

Хорошо, пока отсортирую нереальные ускорения:

12-15(11) ускорение 17765х.

172-7(7) ускорение 14000х.

172-7(5) ускорение 2570х.

156-8(6) ускорение 1800х.

36-13(6) ускорение 1075х.

296-7(2) ускорение 62х.

272-7(1) ускорение ?

Пока не пытался вникнуть, как для 12-15 реальное ускорение в тысячу раз превратилось в нереальное в 17 тысяч раз. Кто-нибудь разобрался?

[Huz]

Define $r(x)$ by $r(1) = 0, r(pq) = r(q) + p - 1: p \in \mathbb{P}$, then $\tau(n) = t$ requires that $n$ have at least one prime factor $\le n^{1/r(t)}$. That is, if $n$ is $n^{1/r(t)}$-rough, $\tau(n) \ne t$.

I'm not sure if you guys ever need to factorize numbers for which you haven't yet allocated all the large powers, but this will certainly save me some time: I just gave up on factorization of a C112 after 2 days, but I had $r(t) = 13$, and trial division up to $n^{1/13}$ took just 0.75s. I had not appreciated that it would be so fast.

[Dmitriy40]

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

272-7(1) ускорение ?

272-7(1) ускорение 16х, 18х, 8х, 9х.

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

Пока не пытался вникнуть, как для 12-15 реальное ускорение в тысячу раз превратилось в нереальное в 17 тысяч раз. Кто-нибудь разобрался?

Считаем общее количество попыток как отношение интервала (1e35) к шагу (4.4e26) умножить на количество паттернов (11520), коэффициент фильтрации это отношение к N, общее время это умножить на время в PARI, ускорение поделить это на полное время. Метод так себе, явно предполагается что скорость в PARI останется неизменной и равной N поделить на время в PARI, что вообще говоря совершенно не обосновано, и чем выше коэффициент фильтрации, тем менее обосновано (время будет расти медленнее из-за более частых отказов на ранних проверках isprime). Вот для малой разницы между общим временем и временем в PARI ускорение ближе к реальному так как основная работа выполняется как раз в PARI и ускорение приближается к коэффициенту фильтрации.
Вспомнил про вариант с 10-ю проверяемыми местами: 36 делителей, 10 проверяемых мест из 15-ти, 5760 паттернов, шаг 2.48e77, N=4211214, 716.039s (263.049s in PARI) per round 9e85 - 4e7 попыток на паттерн, 2.32e11 попыток всего, 4.2e6 кандидатов, коэффициент фильтрации 55150, 16010 кандидатов в секунду в PARI, проверка 2.32e11 кандидатов заняла бы 14.5млн.с (полгода), ускорение 20235х.

Специально ради Вас запустил измерение реальной скорости $M(12)$ без ускорителей по всем паттернам (тупо заменил вызов ускорителей на перебор всех чисел, как будто ускоритель мгновенно вернул их все без фильтрации вообще), только интервал взял сильно поменьше (ждать 3 года влом): 12 делителей, 11 проверяемых мест из 15-ти, 46080 паттернов, шаг 4.4e26, N=105523200, 1246.490s (1148.330s in PARI) per round 50050816e30 - 2273 попыток на паттерн, 1e8 попыток всего, 91900 кандидатов в секунду в PARI. Сравните с 2.615e12/2574с=1e9/с с ускорителями, т.е. фактическое ускорение составило 11050х. А тысяча раз была видимо по сравнению с перебором по одному конкретному паттерну по немного другому алгоритму проверок (специально же сравнивал с исходной программой VAL, она 1e35 считала 169.1с, т.е. 1.34млн/с, от неё ускорение лишь порядка 750х) и на более старой программе (7.03 вместо выложенной 21.03, не буду вспоминать/искать чем отличались).

Вот кстати и ещё одна неувязка в Вашем вопросе: ускорение по отношение к чему Вам интересно, только от применения ускорителей (11050х) или по отношению к исходной программе VAL (750х). Разница между 11050х и 750х — видимо плата за множество паттернов. Проверил, запустил по ровно одному паттерну:
N=197563, 16.962s (3.666s in PARI) per round 5e37 - с ускорителями, 1.34e9/с, почти ровно 1000х от исходной программы VAL;
N=2272800, 22.281s (22.090s in PARI) per round 50050e33 - без ускорителей, 1e5/с, в 13400 раз медленнее ускорителей и в 13 раз медленнее исходной программы VAL, вот столько накладных расходов в PARI на организацию перебора паттернов и прочие циклы.
Разницу в 1.3 раза можно списать на замедление счёта из-за больших объёмов массивов для 46080 паттернов (не влезают в кэши).

[VAL]

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

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

Полагаю, тут-то, как раз, все ясно.
В идейном плане. Конкретные случаи, конечно, лучше подкреплять расчетами.

Для понимания общей тенденции удобно сравнить два случая: 15 чисел по 12 делителей и 9 по 784.

Для поиска пентадекатлона нужны 11 проверок на простоту, а остальных 4-х позициях проверяемое число должно иметь вид $pq$.
С ростом проверяемых чисел обе искомых ситуации становятся все более редкими. Плюс растет время на факторизацию (ростом времени на проверки на простоту можно пренебречь). Ясно, что поиск в ширину в такой ситуации эффективнее.

Поиск девятки чисел, имеющих по 784 делителя, осуществлялся с помощью 3-х проверок на простоту. В остальных 6-и позициях проверяемые числа должны были иметь вид $pqrst$. В том диапазоне, с которого стартует поиск, вероятность такого разложения мала (даже меньше, чем вероятность простоты). Но с ростом чисел она растет. Причем быстрее, чем уменьшается вероятность для простых. Поэтому поиск в глубину хорош. Даже вопреки тому, что время на факторизацию растет. Но, разумеется, так будет лишь до тех пор, пока факторизация не станет тормозить катастрофически. К счастью, искомая девятка обнаружилась до наступления этого момента (иначе пришлось бы таки прибегать к поиску в ширину).

[Dmitriy40]

VAL
Возможно эти оценки верны для поиска в PARI, но вот с применением ускорителей добавляются несколько новых факторов и потому оценки становятся неубедительны:
1. Большие накладные расходы на организацию перебора паттернов (10-13 раз! мрак ), плюс сюда же и расходы на запуск ускорителей (величину круга step приходится выбирать чтобы каждый ускоритель считал хотя бы раз в 10 дольше чем запускается, с увеличением количества паттернов величина круга растёт до десятков и сотен часов, что просто неудобно).
2. Я больше чем уверен что при любой ширине поиска мы никогда не найдём решение для длинных цепочек в первых же кругах перебора (с малым $k$ из формул $p=p_0+km$). А значит лучше побыстрее добраться немного повыше дна низин, т.е. поиск в глубину. Возможно имеет смысл вообще любой поиск в ширину начинать со значений $k$ типа миллиардов невзирая на уменьшение вероятности простоты ...
3. Коэффициент фильтрации и соответственно скорость поиска сильно зависит от количества проверяемых мест и где он пересилит уменьшение вероятности простых зависит от величины чисел.

Плюс не вполне понимаю как соотносятся вероятности $pqrst$ и $pqrs$ с фиксированным $t$. Числа увеличиваются в $t$ раз, вероятность простоты падает на $\ln(t)/\ln(n)$, и это уменьшение не должно достичь вероятности $pqrst$, но совершенно явно есть зависимость от $n$, т.е. от величины чисел, и потому вердикт будет для каждого варианта паттернов свой.

Время на факторизацию меня не волнует, для трудно разлагаемых чисел более примерно 70 цифр оно по любому слишком велико для тотального полного разложения, а полно цепочек имеют и сильно большие числа. Потому факторизацию всё равно придётся ограничивать (при этом уже неважно сколь она трудна) и ждать нахождения легко разлагаемых вариантов. Их вероятность правда тоже будет падать, но как быстро это ещё вопрос (не знаю как ECM ищет делители, иногда быстро находит большие, иногда долго ищет небольшие, плюс ECM в PARI и у альпетрона работают сильно по разному, были примеры когда альпетрон находил делитель за пару секунд, а PARI его же не находил за минуту, был и противоположный пример).

[VAL]

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

Я больше чем уверен что при любой ширине поиска мы никогда не найдём решение для длинных цепочек в первых же кругах перебора (с малым $k$ из формул $p=p_0+km$). А значит лучше побыстрее добраться немного повыше дна низин, т.е. поиск в глубину. Возможно имеет смысл вообще любой поиск в ширину начинать со значений $k$ типа миллиардов невзирая на уменьшение вероятности простоты ...

Категорически не согласен!
Это я про использование буквы $k$, отвечающей за количество делителей в цепочке, а не за номер шага

Теперь по существу.
Кроме мат. ожидания числа проб, есть еще и дисперсия. И она велика.
Так, пятерка по 318 делителей, нашлась гораздо позже, чем показывал предварительный расчет, а пятерка из 402 наоборот практически мгновенно, хотя должна была искаться гораздо дольше первой.
Я понимаю, что чем длиннее цепочка, тем менее вероятны такие отклонения. Но все равно, заменил бы слова "больше чем уверен" на "скорее всего".
И уж точно не стоит пропускать начальные отрезки.

[Dmitriy40]

Букв мало, а $km$ я уже использовал в теме раньше.
Да, короткие цепочки бывает находятся быстро, но это не значит что $k$ при этом непременно мало. Впрочем я говорил скорее про цепочки длиной 11-12 и более. Да и вообще это лишь предположение ...

[VAL]

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

Букв мало, а $km$ я уже использовал в теме раньше.

Я в курсе

[Dmitriy40]

(О буквах)

Вообще я согласен что единые обозначения удобнее.

Вот только сложно согласовать обозначения из разных областей, например в программировании уже лет наверное 50 принято (и даже попало в учебники) обозначать переменные цикла буквами i,j,k,l,m,n,... Да, это наследие ещё 60-70-х годов, когда памяти было мало и переменные были однобуквенные, однако очень многие если не большинство пользуются и поныне. И это удобно, сразу понятно что переменная счётчик цикла и временная, не глобальная, и не надо натужно выдумывать по новому имени на каждый цикл (многие из которых короткие, одна-две команды), и писанины меньше.
Однако как только приходится писать переменные в формулах, так сразу возникает путаница с комплексными числами. Плюс трудно отличить i от j и от l. Я пытался где-то выше писать $p=p_0+im$, мне не понравилось.
Вот и выходит что i,j не подходят, k занята, l неудобна (плохо отличима от единицы или черты), m,n заняты (и часто обозначают размерность чего либо), o режет глаз, p,q,r,s,t заняты под простые (а t ещё и как нечто сугубо временное/локальное), x,y,z предназначены для другого да и часто заняты, u,v,w в качестве индексов очень непривычны, e,f,g (и иногда h) заняты под функции, a,b,c,d в циклах тоже непривычны (это как в математике вместо $f(x)$ писать скажем $c(f)$), они скорее глобальные константы/параметры. Ну и всё, букв нет.

Кроме того, даже в рамках данной темы активно используется перегрузка обозначений (разный смысл в разном контексте), например $p$ используется и как искомое простое, и как простое в разложении количества делителей. Потому не вижу особой проблемы придать и $k$ разный смысл в зависимости от контекста, главное не смешивать, но вроде я везде привожу полную формулу $p_0+km$ чтобы явно указать на смысл букв когда говорю про индекс ...
Так что страсть к фиксации раз и навсегда смысла отдельных букв мне непонятна.

Я не ради поспорить, скорее пояснить свои мотивы почему пишу так.

[VAL]

(Про буквы)

Согласен, с аргументами про все буквы кроме $i$.
Вот когда Денис в своих изысканиях докопается до необходимости использовать комплексные числа, тогда и будем "репу чесать"
А пока $p=p_0+im$ смотрится замечательно.

-- 15 июл 2022, 20:25 --

Есть еще один пентадекатлон!

$T(48,15)\le 23502743153262834519466832982608904075248676530415612$
Соответственно $M(96)\ge 15$.
Полагаю, 16 можно поймать (и вывести 96 на чистое 3-е место) за реальное время.

[Huz]

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

Есть еще один пентадекатлон!

$T(48,15)\le 23502743153262834519466832982608904075248676530415612$
Соответственно $M(96)\ge 15$.

Congrats. :)

[mathematician123]

Есть вопрос по оформлению доказательства $M(12t + 6) \le 5$. Доказательство сводится к решению четырёх групп диофантовых уравнений. При этом, уравнения в каждой из этих групп решаются аналогично (применяются те же методы, но с другими числами). Можно ли в этом случае в доказательстве рассмотреть только одну группу этих уравнений, а про остальные сказать, что они решаются аналогично?

[VAL]

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

Можно ли в этом случае в доказательстве рассмотреть только одну группу этих уравнений, а про остальные сказать, что они решаются аналогично?

Полагаю, не только можно, но и нужно.