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

[Yadryara]

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

Меня, например, смущает округление в задаче, где все изначально целочисленно.

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

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

Вот для 8 паттернов с 98 на 11-м месте (это maple, а не PARI):

Пощадите . Я тока-тока с PARI чуток освоился, а тут новая напасть — Maple.

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

Действительно для 28 подходящих случаев больше (814 против примерно 700).

814 на 4-м месте я прекрасно вижу, а вот где эти примерно 700 на 11-м месте? Или это усреднённое значение?

[Dmitriy40]

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

Насколько реально внести такие изменения?

Реально все.
Про 11 чисел уже и так встал вопрос, если Вы голосуете за 11 вместо 14, то ОК, мне тоже так кажется боле логичным. Вот вариант exe с проверкой лишь 11 чисел (в облаке пока оставлю старый): https://dropmefiles.com/vryWw
Количество мелких простых увеличить — в ближайших планах. 65536 конечно перебор (таблицы в программе станут десятки мегабайт, но проблема не в их размере, а в превышении размера кэша L3), но что-то разумное хочу сделать. На мой взгляд достаточно отфильтровать так чтобы проверка в PARI занимала менее 10% общего времени (вместо 70% как сейчас).
Размер чисел $k$ на входе тоже нетрудно, но непонятно надо ли: $2^{64}\cdot 4.4\cdot10^{26}\approx 8\cdot10^{45}$, это более семи тысяч лет счёта в один поток.
Плюс в планах проверить скорость фильтрации по делимости индекса первой проверкой.

PS. Проверил на PARI достижимое качество фильтрации при разных пределах на малые делители для миллиона чисел где-то около $10^{14}$:
$2^8: 5154$
$2^9: 1353$
$2^{10}: 439$
$2^{11}: 166$
$2^{12}: 57$
$2^{13}: 34$
$2^{14}: 14$
ИМХО достаточно из миллиона чисел оставить PARI проверить 57 вместо сегодняшних 5154, позволит уложиться в пару мегабайт таблиц. Впрочем посмотрим.

[VAL]

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

Пощадите . Я тока-тока с PARI чуток освоился, а тут новая напасть — Maple.

Как говорится, "взялся за гуж...".
Впрочем, можете и не проверять, а поверить

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

814 на 4-м месте я прекрасно вижу, а вот где эти примерно 700 на 11-м месте? Или это усреднённое значение?

Усредненное. Но 98 неожиданно оказалось не на 11-м, а на 14 месте

Сейчас либо найду, либо пересчитаю для случая, когда 98 на 11-м.

Стоп!
98 и не может быть на 11-м месте. На 11-м месте может быть 49. Как раз когда 28 на 4-м.

Так что с чем сравниваем?

[Yadryara]

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

98 и не может быть на 11-м месте.

Вот именно. Но не я начал эту путаницу:

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

Вот для 8 паттернов с 98 на 11-м месте

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

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

[Dmitriy40]

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

Вы внимательно читали лемму 6 в той самой статье 2018 года?

Процитирую главный вывод из той леммы:

Цитата:

Let n25, n26, . . . , n15 (where ni is congruent to i modulo 32) are the numbers of such run.
...
Thus n0 and n8 cannot at the same time belong to a required run

ОК, n0 и n8 одновременно быть не могут, не вопрос, это понятно. Но нигде тут не сказано что недопустим вариант n1,...,n15. Либо я в упор не вижу где.

[Yadryara]

Ну вот моя добавка-то:

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

Нельзя чтобы хоть какое-то число 15-шки делилось ровно на $8$ или, тем более, ровно на $16$. А на числовой оси такие места есть только вблизи чисел кратных $32$. Вот и получается, что наши планеты удалены не дальше чем на 7 единиц от центральной звезды. Они равны $32p\pm7$.

Или Вы не согласны, что нельзя допустить, чтобы хоть какое-то число 15-шки делилось ровно на $8$ или, тем более, ровно на $16$ ?

[Dmitriy40]

Иначе говоря, $4pq=0\pmod8$ в позиции $n+7$ неразрешимо при любых нечётных $p,q$? ОК, это я понимаю, значит $32p$ действительно обязательна.

[VAL]

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

Но нигде тут не сказано что недопустим вариант n1,...,n15.

Совершенно верно.

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

Или Вы не согласны, что нельзя допустить, чтобы хоть какое-то число 15-шки делилось ровно на $8$ или, тем более, ровно на $16$ ?

На 16, ни одно из искомых чисел, конечно, делиться не может. Иначе число делителей было бы кратно 5.
Но делиться на 8 среднему числу искомого набора никто не запрещает (в том числе и лемма 6).
Например, среди пятнашек, где среднее число равно $8(301522186930606735689318659+82601031698135096600604150k)^2$, практически наверняка найдется искомая.
Вот только числа здесь гораздо больше, чем в пятнашках, где посередине $32p$.

[Dmitriy40]

Выше говорилось про оптимальность шага (модуля), но я вот обнаружил два интересных зеркальных паттерна:

Используется синтаксис Text

n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
45p     2pq^2   13pq^2  12p     7pq^2   50p     3pq^2   32p     11pq^2  18p     5pq^2   28p     3pq^2   2pq^2
        2pq^2   3pq^2   28p     5pq^2   18p     11pq^2  32p     3pq^2   50p     7pq^2   12p     13pq^2  2pq^2   45p

В которые можно подставить 9 произвольных простых в квадрате на места $q^2$ и свободное и получить прямые условия на 14 чисел из 15-ти. При подстановке простых $19,47,41,29,43,37,31,23,17$ в указанном порядке в первый паттерн шаг (модуль) получится порядка $6\cdot3\cdot10^{33}$. Полезнее ли это пока без понятия. Моя программа работает на 30% медленнее (10с вместо 7с), но фильтрует почти вдвое лучше (2700 вместо 4700 на миллион).

[VAL]

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

Выше говорилось про оптимальность шага (модуля), но я вот обнаружил два интересных зеркальных паттерна:

Используется синтаксис Text

n+0     n+1     n+2     n+3     n+4     n+5     n+6     n+7     n+8     n+9     n+10    n+11    n+12    n+13    n+14
45p     2pq^2   13pq^2  12p     7pq^2   50p     3pq^2   32p     11pq^2  18p     5pq^2   28p     3pq^2   2pq^2
        2pq^2   3pq^2   28p     5pq^2   18p     11pq^2  32p     3pq^2   50p     7pq^2   12p     13pq^2  2pq^2   45p

В которые можно подставить 9 произвольных простых в квадрате на места $q^2$ и свободное и получить прямые условия на 14 чисел из 15-ти. При подстановке простых $19,47,41,29,43,37,31,23,17$ в указанном порядке в первый паттерн шаг (модуль) получится порядка $6\cdot3\cdot10^{33}$. Полезнее ли это пока без понятия.

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

Цитата:

Моя программа работает на 30% медленнее (10с вместо 7с), но фильтрует почти вдвое лучше (2700 вместо 4700 на миллион).

Хорошо бы 1 на миллион

[Yadryara]

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

На 16, ни одно из искомых чисел, конечно, делиться не может. Иначе число делителей было бы кратно 5.

Примерно на это и намекал, говоря "тем более". Если мы хотим получить 12 делителей, то 4-я степень простого нам никак не годится, а могут пригодится только степени 1, 2, 3, 5, 11.

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

Но делиться на 8 среднему числу искомого набора никто не запрещает (в том числе и лемма 6).

Важное уточнение: лучше говорить "ровно на 8". Значит я эту лемму слишком широко трактовал.

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

За исключением среднего числа в цепочке, которое кратно 32 (это необходимое условие).

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

Молодец, Dmitriy40, проявил ту самую дотошность.

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

Спасибо за дотошность.

И Вам спасибо.

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

наработки по задаче с разных сторон и под увеличительным стеклом

Я специально написал про лупу. Потому что надо бы не под лупой, а под микроскопом рассматривать многие вещи, но это затруднительно.

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

Впрочем, можете и не проверять, а поверить

То то и оно, что нельзя нам здесь верить друг другу, а надо проверять, да ещё как тщательно. В интересах дела.

Ну так что насчёт эпической битвы 28 против 98 ?

Да, вот у меня ошибка. К счастью, не в самом паттерне, а в его описании:

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

3-й этап. Ещё две: $2^2\cdot7$ и $7^2\cdot2$

Не надо умножать на 2 в конце: $2^2\cdot7$ и $7^2$

Dmitriy40, а можно Вас попросить как-то по-другому изображать паттерны? Ну не помещаются они по ширине страницы даже в мелком масштабе! Необязательно как у меня, но чтоб покомпактней.

[Yadryara]

Пока единственное ядро моего компа считает, попытаюсь написать обобщающий пост.

Во-первых, уточнение. Предлагаю считать самой перспективной концепцией КМК37-11.

Почему я удлиняю название и уточняю насчёт 11-ти:

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

При этом в наборах нет третьего числа, кратного 7, и вторых чисел, кратных 11 и 13 (последние теоретически могли бы присутствовать, но их допущение резко снижает эмпирическую вероятность успеха, поскольку в интересующем нас диапазоне произведения двух простых встречаются гораздо чаще, чем простые).

Ну так вот, я проговорю явно то, что может быть не замечено, как уже было. Если хоть одно из вторых чисел кратных 11 и/или 13 попадёт в паттерн, то огромных простых будет уже 12, а то и больше.

А для нас и 11 огромных простых это очень много. Пока продолжаю считать, что меньшее количество невозможно.

Жду момента, когда уважаемый Dmitriy40, тщательно проверит все другие пути и вернётся к КМК37-11.

Также 12 дней жду ответа на этот важный вопрос:

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

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

координировать действия нескольких участников

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

Например, спрошу проверялся ли ранее тот самый паттерн, для которого Dmitriy40 делал программу:

45p 722p 841qr 12p 49qr   50p 507p 32p 961qr 18p   605p 28p 867p 1058p 1369qr

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

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

"Идентичные начальные условия для программы поиска" мы уже вовсю называем паттернами.

А Вы пытались рассчитать точное количество этих паттернов в рамках КМК37-11? Не о сотнях ли тысяч надо в таком случае говорить?

Я вот пытался ограничить количество самых приоритетных паттернов до $2880$, используя новые ограничения:

На 3-м этапе брать только 28, но не 98.

На 4-м этапе брать только 605, но не 845, 1445, ..., 6845 .

Дальше есть ещё ограничения. Но обоснованность их всех пока сомнительна, да.

Тем временем комп проверил диапазон 0-500 миллиардов. И счёт в противостоянии $605$ и $2645$ получился $31 : 9$. На этот раз тоже преимущество меньшего числа над большим. Но не в 8, а в 3 раза. Хотя числа, конечно, пока маловаты.

[VAL]

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

Например, среди пятнашек, где среднее число равно $8(301522186930606735689318659+82601031698135096600604150k)^2$, практически наверняка найдется искомая.

Таки не найдется!
Среднее число в пятнашке имеет вид $8p^2$. Тогда 6-е число $2(4p^2-1)=2(2p-1)(2p+1)$, где $2p-1$ кратно 9 и больше 9. Поэтому у 6-го числа не менне 24 делителей.

Так что условие "среднее число в пятнашке имеет вид $32p$", по-видимому, все же, необходимо.

-- 22 фев 2022, 18:10 --

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

Я вот пытался ограничить количество самых приоритетных паттернов до $2880$, используя новые ограничения:

У меня получилось $2\cdot (12+20) \cdot 720=46080$ вариантов. Впрочем, считал наспех. Но порядок числа, видимо, такой.

[Yadryara]

Ещё одно непонимание попробую ликвидировать.

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

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

Вот именно, что далеко не все:

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

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

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

У меня получилось $2\cdot (12+20) \cdot 720=46080$ вариантов.

Так вот, я по-прежнему сильно подозреваю что нет никаких десятков тысяч идентичных начальных условий.

И всем же ведь будет лучше, если я окажусь прав. Если одни варианты действительно имеют приоритет над другими, перебор сократится в $\dfrac{46080}{2880}=16$ раз. Это предварительно, я думаю, что исходно более 46 тысяч имеется. Прошу более подробный расчёт. Думаю по 7 этапам удобно будет рассчитать.

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

Правда, подтверждается она только мной, но и не опровергается пока никем, ибо:

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

814 против примерно 700

Это оказалось неверным.

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

Так, флуктуации в пределах статистической погрешности (780 против 694 на 10 000 )

А это пока не подтверждено ничем.

[VAL]

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

Правда, подтверждается она только мной, но и не опровергается пока никем, ибо:

VAL в сообщении #1549301

писал(а):
814 против примерно 700
Это оказалось неверным.

Неверным оказалось лишь то, что я по неаккуратности приписал 98 11-ю позицию. На самом деле в рассматриваемом паттерне 98 стояло в 14-й. А частотность вполне себе верная.