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

[Yadryara]

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

Во второй вашей таблице. Насколько я помню обе новые 15-ки найдены именно в ней, а не в первой. Хотя из неё "сразу два квадрата простых выброшены из паттернов" (Ваши слова).

Нет они не выброшены из паттернов, а заменены на другие.

В одном случае 31 и 37 были заменены на 41 и 53(259-й комплект).
В другом случае 23 и 37 были заменены на 41 и 43(329-й комплект).

То есть среди проверяемых цепочек по-прежнему полный порядок: одна 5-я степень и 14 гарантированных квадратов.

А в прогах по которым сейчас считаете Вы, 2 квадрата простых именно выброшены из паттернов:

среди проверяемых цепочек одна 5-я степень и только 12 гарантированных квадратов.

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

А для Вас есть разница между "не найти вообще" и "не найти за квадриллион лет"

Да, конечно. Принципиальная.

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

Какую затею? Проверку второй вашей таблицы?

Проверку второй таблицы таким способом. С выбрасыванием двух квадратов простых. Он очень хорош для поиска 13-ки, но для поиска 14-ки мало перспективен.

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

Что бы Вы ни выдумывали насчёт адекватности причины "сразу два квадрата простых выброшены из паттернов".

Что-что, простите? Я что-то выдумываю?

[Dmitriy40]

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

А в прогах по которым сейчас считаете Вы, 2 квадрата простых именно выброшены из паттернов:

И что? Я не вижу обоснования почему это плохо.

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

Он очень хорош для поиска 13-ки, но для поиска 14-ки мало перспективен.

Обоснуйте.

[Yadryara]

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

Обоснуйте.

Буду считать, что Вы имели в виду более вежливую формулировку: "Обоснуйте, пожалуйста" или "Прошу обосновать".

Начну издалека.

Меня удивило, что нужно обосновывать. Мы же оба давным-давно в теме. Прямо с февраля, с самой первой страницы.

Вот с неё и начну:

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

При этом каждое из 15 гарантированно делится на квадрат простого числа (чтобы количество делителей было кратно 3). За исключением среднего числа в цепочке, которое кратно 32 (это необходимое условие).

А зачем спрашивается нужно, чтобы каждое из 14 гарантированно делилось на квадрат простого числа?

Вы тогда этот вопрос не задали.

Потом у нас с Вами была довольно длинная дискуссия и наконец на 12-й странице до Вас дошло то, о чём впервые было сказано ещё на первой:

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

А, дошло, т.е. пустые места тоже надо забить простыми в квадрате?

Да, надо. А для чего? Чтобы увеличить вероятность успеха.

А выбрасывание квадратов простых эту вероятность уменьшает.

С этим согласны?

[Dmitriy40]

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

Да, надо. А для чего? Чтобы увеличить вероятность успеха.
А выбрасывание квадратов простых эту вероятность уменьшает.
С этим согласны?

Ладно, пусть согласен. Всё равно не вижу пока как это трансформировать во время счёта.
Хотя в такой формулировке конечно куча огрехов и вообще говоря не согласен: это верно только если угадаем с расставляемыми простыми, проверка же строк таблицы как раз и не привязана к вставляемому простому, она найдёт решения с любыми простыми, не только 17-37 или 17-179. И что из них вероятнее - ещё вопрос.

Если совсем по простому, то выкидывание квадрата простого превращает место из проверяемого в непроверяемое, и соответственно будет там квадрат простого (причём вовсе не обязательно 17-37) или не будет - вопрос интересный. И я привёл выше пример как в 3 случаях из 5 на таком выкинутом месте всё равно появился квадрат простого (и даже именно 17-37).

[Yadryara]

Ну трудно удержаться. Давайте банальность скажу. Допустим, нам надо дойти до тысячи. Сколько шагов нам нужно сделать? Мы можем сделать 500 шагов по всем нечётным. А можем сделать 10 шагов по всем нечётным простым квадратам. И в том и в другом случае мы все нечётные квадраты проверим.

Допустим мы выкинули $37^2=1369$. Шаг уменьшился в $1369$ раз. И теперь нам нужно сделать $1369$ шагов, вместо одного, чтобы добраться до этого квадрата. Да, по пути, мы и другие квадраты простых пройдём, целых 11 штук. А кубы? Да, целых 5 штук. А 5-е степени? Две штуки. Итого круглым счётом 20 потенциально полезных чисел. А стоит ли делать $1369$ шагов, вместо одного, ради всего лишь 20 чисел?

Вывод: выкидывание даже одного квадрата -- сомнительный метод. Но другого пока не придумалось.

[Dmitriy40]

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

А стоит ли делать $1369$ шагов, вместо одного, ради всего лишь 20 чисел?

Конечно стоит - ведь мы можем найти те решения, которые проходом одним шагом сразу до 1369 не нашли бы и среди них вполне могут быть цепочки с меньшими числами чем те что будут найдены с шагом 1369.
Я уже приводил такой пример про 13-ку 586683019466361719763403545:

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

Что характерно, последняя, наименьшая, 13-ка вообще не могла найтись ни в каком комплекте из второй таблицы, хотя в ней и якобы две замены, но 14-е место не имеет простого в квадрате, а в любом комплекте оно бы там было и место стало бы проверяемым и соответственно эта цепочка была бы отброшена ещё самим ускорителем (как делящееся на 131). Это ещё один пример цепочек, которые находятся проверкой строк и не находятся заменами простых в квадратах друг на друга, хоть до какой границы.

Как насчёт этой вероятности успеха, а? Её Вы вообще не нашли бы, ни по какой ячейке второй таблицы (про первую и не говорю). А по строкам она нашлась. И пока остаётся минимальной известной.
Ничто не мешает ситуации повториться и с 14-кой.

[Yadryara]

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

Как насчёт этой вероятности успеха, а?

Мне лень её считать. Но я ведь Вам сам посоветовал таким способом искать 13-ки. Так что тут меня убеждать не надо.

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

Ничто не мешает ситуации повториться и с 14-кой.

Мешает. Отсутствие двух гарантированных квадратов.

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

Я пытался почти ей заниматься: брал паттерн с размещёнными лишь 2,3,5,7,11,13 и считал.

А здесь мешает отсутствие шести гарантированных квадратов. Но не делает нахождение невозможным.

Мой прогноз: на 1000 13-к найдётся не более 1-й 14-ки.

Дайте свой. Сейчас, как я понимаю, счёт 99:0 в пользу 13-к.

[Dmitriy40]

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

Мешает. Отсутствие двух гарантированных квадратов.

Да объясните же наконец как отсутствие квадратов мешает им всё равно найтись на непроверяемом месте?! Вот же нашлись и ничего не случилось, Солнце не погасло:
S2-34-000100:196526805644360942041: 12, 32, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 8, 16, 12, valids=11, maxlen=9 - v=[1,2,3,28,1445,18,121,32,507,50,49,12,1,2,45]; z=[0,0,0,1,1,1,0,1,1,1,0,1,0,0,0]; n=7; pp=Mod(1389538300441,2084963680800);
S2-34-200000:196526805644360942041: 12, 32, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 8, 16, 12, valids=11, maxlen=9 - v=[361,2,3,28,5,18,121,32,507,50,49,12,1,2,45]; z=[0,0,0,1,0,1,0,1,1,1,0,1,0,0,0]; n=6; pp=Mod(632025544441,2604400999200);
Надеюсь видно что в паттерн поставили один квадрат (из необходимых шести), а второй нашёлся сам?

-- 24.08.2022, 00:40 --

А, или Ваше "мешает" вовсе не тождественно "запрещает"?! Т.е. просто уменьшает вероятность, но не запрещает нахождение? Тогда видимо да, мешает, в том смысле что если насильно расставить все квадраты, то они (квадраты которые) уж точно найдутся. Вопрос лишь какие именно квадраты расставлять, 17-37 хороший выбор, но не единственный и факт что не лучший (потому что при расстановках других простых найдены две меньшие 15-ки). И если мы можем себе позволить идти с шагом в $17^2=169$ раз меньшим (и соответственно в 170 раз дольше), то лучше 17 не расставлять, всё равно все решения с $17^2$ будут найдены. Зато нам не придётся вместо 17 расставлять 41,43,47,53,59,61,67,..., мы всего за 169 раз проверим их все, сколько бы их ни было, хоть миллионы и миллиарды.

[Yadryara]

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

А, или Ваше "мешает" вовсе не тождественно "запрещает"?! Т.е. просто уменьшает вероятность, но не запрещает нахождение?

Да, разумеется. Я же специально написал:

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

А здесь мешает отсутствие шести гарантированных квадратов. Но не делает нахождение невозможным.

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

И если мы можем себе позволить идти с шагом в $17^2=169$ раз меньшим (и соответственно в 170 раз дольше),

Утомились, наверное. Всё-таки $17^2=289$.

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

Зато нам не придётся вместо 17 расставлять 41,43,47,53,59,61,67,..., мы всего за 169 раз проверим их все, сколько бы их ни было, хоть миллионы и миллиарды.

Абсурд. Чтобы проверять именно $41^2=1681$ нам и надо $1681$ шаг делать от одного такого квадрата до другого. А чтобы проверить $67^2$ нам надо делать $4489$ шагов от одного такого квадрата до другого.

По пути, конечно, могут встреться и другие квадраты, кубы и 5-е степени. И не только могут, но и обязательно встретятся. Вот только далеко не на каждом шаге.

А если у нас конкретный квадрат имеется в паттерне  —  то гарантированно на каждом шаге. Этот конкретный квадрат.

[Yadryara]

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

Я вот кстати досчитал уже до 1.6e30 по всей расширенной таблице с двумя заменами и 14-ка не встретилась, даже вообще valids=14 не было, не только непрерывных.

Ну вот уже известная 14-ка должна встретиться чуть ниже 3.8e30. Когда примерно 200 13-к найдётся. Будет ли ещё хотя бы одна за следующие 800 13-к — очень сомнительно.

[Dmitriy40]

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

Абсурд. Чтобы проверять именно $41^2=1681$ нам и надо $1681$ шаг делать от одного такого квадрата до другого. А чтобы проверить $67^2$ нам надо делать $4489$ шагов от одного такого квадрата до другого.

Давайте по другому. Нам нужно проверить интервал 0-1e35 (весь до 15-ки), мы можем проверить его с шагом 1 и тогда понадобится $10^{35}/1$ шагов. А можем разместить в паттерн $37^2=1369$ и проверить с шагом 1369 и тогда понадобится лишь $10^{35}/1369$ шагов. Да, казалось бы в полторы тысячи раз быстрее. Но только для одного конкретного простого. А если нам надо проверить этот интервал с шагами $p_i^2$, где $i=7...10^5$, то общее количество проверок будет $\sum_{i=7}^{10^5}10^{35}/p_i^2=10^{35}\sum_{i=7}^{10^5}1/p_i^2$, при верхнем пределе больше нескольких сотен сумма стремится к 0.0165 и соответственно в среднем надо будет сделать в 60 раз меньше шагов. Казалось бы прекрасно. Но это верно только для чистого времени счёта, без учёта накладных расходов и времени компиляции. Которые растут линейно с ростом количества используемых простых. Т.е. реальное затрачиваемое время будет не той суммой, а $\sum_{i=7}^{n}(C+10^{35}/p_i^2)=Cn+10^{35}\sum_{i=7}^{10^5}1/p_i^2$ и при некотором количестве простых $n$ первое слагаемое пересилит второе. Вопрос лишь когда именно это произойдёт, будет ли такое $n$ меньше ста тысяч (или сколько к тому времени придётся простых до границы) или нет.

Возьмём реальный пример, по моим данным.
Компиляция комплекта занимает круглым счётом 6ч (в один поток), счёт для 234 комплекта 3200с, т.е. для 00 комплекта он занимал бы в 3.34 раза больше или 10700с. Соответственно формула общего затраченного времени в секундах на $n$ комплектов выглядит так $\sum_{i=1}^{n} (21600+10700\frac{17^2}{p_{i+6}^2})$, что для $n=1$ даёт исходные $21600+10700=32300$. Подсчитаем для какого $n$ она даст больше чем $21600+10700\times37^2=14669900$ (проверка самой медленной строки с заменой 37 на другие простые), это происходит при $n=677$, т.е. проверять менее 700 комплектов выгоднее по одному, а больше - проверкой всей строки. Для строки с заменой 17 время проверки строки будет $21600+10700\times17^2=3113900$ и порог наступает уже при $n=142$.
Тут конечно можно возразить что при проверке комплектов по одному мы можем значительно уменьшить границу с 1e35 и остальные комплекты считать быстрее, вот только уменьшение порога в 10 раз, до 1e34, приводит к увеличению порога с 142 до 144. А в 100 раз - до 145. И даже при полностью мгновенном счёте (вместо 10700с берём 0с) порог всё равно 145. Всего лишь. Потому что основное время тратится на компиляцию, а она линейна по $n$. Так что пока граница не опустилась ниже 150 простых в строке замен 17, выгоднее скомпилить один раз проверку всей строки чем компилить множество комплектов. 150 простых это примерно до тысячи, или граница 1e19. Всего лишь!
Для строки с заменой 37 даже при нулевом времени счёта порог поднимается с 677 до 680 (простое примерно 5150), или граница 1.1e19.
Я очень-очень сильно сомневаюсь что 15-ка будет найдена до такой границы. Т.е. проверять строки первой таблицы выгоднее всегда проверкой строки, а не отдельных комплектов. Что собственно я и хотел сказать.
Можете что-то сказать по этому расчёту? Я опять где-то просчитался или посчитал не то?

И это только про поиск именно 15-ки, когда надо получить все места с квадратами простых. Тут уж как ни искать, а всё равно найдём.
С поиском 14-ки и менее всё сложнее, на края паттерна квадрат простого размещать вовсе необязательно, соответственно размещая там квадрат простого мы отбрасываем какие-то возможные решения. И выходит что-то можем не найти в принципе. Оценивать выгоду в скорости не буду, это заметно сложнее (из-за непонятных краёв).

[Yadryara]

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

Можете что-то сказать по этому расчёту?

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

В общем выбрасывание одного простого заметно лучше старого способа. Я это и раньше говорил.

А вот с выбрасыванием двух простых сомнения, да. Я думаю, надо продолжать до победы(непрерывной 14-ки) или до 1000 13-к, а потом думать. Это Вам месяц счёта?

У меня ничего интересного. Дошёл про строке 31 до 270е30. 10 13-к, ни одной непрерывной.

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

а вот встретится ли 15-ка это вопрос и тогда до 976481e28 считать ...

В 10 раз хуже: до 976481e29

[Dmitriy40]

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

В общем выбрасывание одного простого заметно лучше старого способа. Я это и раньше говорил.
А вот с выбрасыванием двух простых сомнения, да.

Вы говорили что выбрасывание двух простых (в квадратах конечно) резко затрудняет нахождение 14-ки. По аналогии можно сделать вывод что выбрасывание одного простого резко затрудняет поиск 15-ки. А мой расчёт это опровергает. Значит и для 14-ки Ваш вывод тоже как минимум спорный, надо считать.

Выше с границами я похоже ошибся, не возвёл простое в квадрат, соответственно для 145-ти простых (строка с заменой 17) граница будет 7е30, а для 680-ти простых (строка с заменой 37) граница 5е31. Выше этих границ выгоднее считать строками.

[Yadryara]

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

Вы говорили что выбрасывание двух простых (в квадратах конечно) резко затрудняет нахождение 14-ки. По аналогии можно сделать вывод что выбрасывание одного простого резко затрудняет поиск 15-ки.

Думаю, что нам нет необходимости ставить телегу впереди лошади. Мы же ведь шли-то наоборот. Сначала выбросили квадрат одного простого. Я сам считал:

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

После События — менее 116 тысяч во всех 6-ти строках первой таблицы.

А именно в 6-й строке(где слева 17) всего лишь 13100 комплектов.

А в той строке, где слева 37 — 26637 комплектов.

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

$$\frac{8\cdot 26600}{24\cdot365}\approx24.29$$

24 года только на одну компиляцию! И при этом многие стартовые точки не будут обсчитаны!

А вот если по-новому, то есть если из паттернов выбросить квадрат 37:

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

Я пока скомпилил строку, где слева 37
[..]
У меня счёт идёт медленнее, чем ожидалось. Интервал 1495 — 1600e30 будет считаться чуть ли не сутки. Таким темпом до 182213е30 лет 5 добираться.

И всё равно 5 лет на счёт — ​​​​​​​это намного меньше, чем 24 года на одну только одну компиляцию.

Вот такую прикидку я уже раньше делал, но не постил, посчитав, что новый метод(с выбрасыванием одного квадрата) очевидно лучше старого. И полагал, что не только мне это очевидно.

[Dmitriy40]

Yadryara
Держите для коллекции:
S9-14-503124:183436393254779779079147135428441: 48, 24, 32, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=12, maxlen=12
N9-73-421506:259037697563588532195140710301145: 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 12, 12, valids=14, maxlen=12, ALL
N2-71-162430:385427596323439044431572262121945: 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 8, valids=12, maxlen=12
S9-13-501326:411073904522730959260971181190041: 6, 12, 64, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, valids=13, maxlen=12, ALL
Они в Ваши текущие таблицы не попадают.