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

[Dmitriy40]

Yadryara
Потому что kolshag используется в двух местах (как шаг цикла по ii и при вызове ускорителя), а править надо лишь одно (у ускорителя).
Реально конечно цикл по ii уже не нужен, но опять же, это вот сейчас и вот вам не нужен, а мне например бывает интересно разделить время счёта ускорителей и интервал записи в лог (а туда у меня пишется статистика по каждому кругу) - бывает первое время единицы минут (если вообще не доли минуты), а второе мне нравится порядка часа чтобы лог не разрастался. И ради этого и затевался цикл по ii, чтобы на экран показывать статистику почаще (внутри цикла по ii), а в лог пореже (в цикле по h, раз на круг).
Ну и насчёт "давно используется" Вы как-то не совсем правы, нигде он не используется, только лишь выводится в лог, везде по прежнему стоит расчёт из step и pp.mod.
Да и просто не получается выражаться коротко.

[Yadryara]

Dmitriy40, не хочется пока спорить об обозначениях, ей-богу.

У меня вопрос к поклонникам брутфорса, в частности к gris.

Вот есть у меня не самая сложная прога:

write("begin.tmp","is begin");
allocatemem(2^27);
start=281;
stop= 1*10^9;
print();
{forstep(i=start,stop, 450,
n=i^2*2-1;
if (numdiv(n)==6 && isprime(i) && isprime((n+2)/9) && isprime((n+3)/4) && isprime((n+4)/25), print(n, "   ",numdiv(n), "   ",numdiv(n+1), "   ",numdiv(n+2), "   ",numdiv(n+3), "   ",numdiv(n+4));print())
)}
write("end.tmp","is end");
quit;

Она за считанные минуты находит три пятёрки по 6 делителей:

    10093613546512321   6   6   6   6   6

   266667848769941521   6   6   6   6   6

  1579571757660876721   6   6   6   6   6

Сколько времени займёт доказательство умным перебором, что пятёрка 1.009е16 минимальная? Всё-таки она 18 порядков меньше известной 15-ки по 12 делителей...

[Dmitriy40]

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

Вот есть у меня не самая сложная прога:

Боле быстрые команды лучше ставить в начало проверки, а более медленные в конец. Numdiv намного медленнее isprime, потому её лучше подвинуть в самый конец условия. Только это даст выигрыш с 385с до 1.7с! А с возрастанием чисел выигрыш будет ещё увеличиваться.

Но вообще вопрос конечно не слишком адекватный: брутфорс тоже может быть очень разным, можно тупо перебирать все числа подряд, можно идти с каким-то шагом (гарантированно покрывающим все возможные варианты паттернов), можно отдельно подоказывать какие-то варианты (типа отсутствие решений с $p^5$). Конечно в 2с ничего из этого не уложится.

-- 12.10.2022, 17:04 --

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

Dmitriy40, не хочется пока спорить об обозначениях, ей-богу.

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

[Yadryara]

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

Numdiv намного медленнее isprime, потому её лучше подвинуть в самый конец условия.

Ну что Вы подсказываете Я-то это знаю.

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

брутфорс тоже может быть очень разным, можно тупо перебирать все числа подряд,

Видите, "тупо", а я написал "умным:

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

Сколько времени займёт доказательство умным перебором,

То есть пусть максимально умным способом попытаются доказать.Теперь это легче, ибо Вы уже кое-что подсказали. Чувствуется, что Вам эта задача тоже интересна.

И нет бы людям за 11-ку взяться или за 12-ку, так чегой-то сразу за 15-ку...

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

Да я и не спорил,

А я могу поспорить, но не буду пока.

[Huz]

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

Yadryara в сообщении #1566576

wrote:
Сколько времени займёт доказательство умным перебором,
То есть пусть максимально умным способом попытаются доказать.

To know how fast it would be by the most intelligent way, you would need to be infinitely intelligent.

I think my algorithm for proving minimality is pretty good though. It proves minimal D(6, 5) in less than a second on my machine. (It finds a total of 631508 numbers that need testing.)

It is less obvious how good my approach us for finding the minimal value in the first place - as Dmitry once pointed out, the fact that my approach cannot test numbers in ascending order means it may do a lot of extra work. However my older approach did test numbers in ascending order but as a result was far less able to restrict which numbers should be tested, and was therefore far slower overall.

For proving that an actual minimum is minimal, though, order doesn't matter - you need to show every smaller number is not a solution, and what order you test them is irrelevant.

[gris]

Не люблю это слово — бр-рс. Оно агрессивное и гадкое. Я использую "сплошной перебор". Вот программа: Поиск шестёрок определённого типа.

{A1=6250000000;A2= 6260000000;
print("tuples of type 2-14-5-6-11 from ",A1*32," to ",A2*32);
k=0;
forprime(i=A1,A2,m=32*i;
  if(numdiv(m-6)==12,if(numdiv(m+6)==12,
  if(numdiv(m-3)==12,if(numdiv(m-2)==12,
  if(numdiv(m+3)==12,k++;print(m));););););
);
print("only ",k," tuples was found");
}

Последовательность проверок установлена опытным путём.
Я произвёл сплошной перебор до 250 000 000 000! (это не факториал!) и не нашёл шестёрок особого вида, а значит нет и пентадекатлона.
Кто хочет, может продолжать. Моя программа свободна для использования.

[Yadryara]

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

To know how fast it would be by the most intelligent way, you would need to be infinitely intelligent.

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

I think my algorithm for proving minimality is pretty good though. It proves minimal D(6, 5) in less than a second on my machine.

Я и не сомневался, что именно Вы это можете сделать весьма быстро. Но чтобы меньше секунды !! Пока не показывайте код.

gris, мы с Дмитрием ждали Вас в теме. Есть у Вас какие-нибудь мысли про D(6, 5) ?

[gris]

Yadryara, я трепетно отношусь к вашей замечательной теме, но по слабости моих познаний могу только провести сплошной перебор ещё на десяток миллиардов. А Наталия Макарова провела его уже до триллиона. Вы с ней наладьте контакты и будет вам счастье. А я разжалован и нахожусь в отставке. Я бы выдал ей логин и пароль для участия в теме. У неё везение есть, она будет полезна.

[Yadryara]

gris, я вижу, что Вы использовали факт наличия в искомой 15-ке $32p$, причём ровно в середине.

Но как Вы использовали факт наличия в ней 4 других обязательных чисел? Я писал о них ещё на 3-й странице:

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

$12p_1$ , $18p_2$ , $32p_3$ , $45p_4$ , $50p_5$.

[Dmitriy40]

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

Ну что Вы подсказываете

О, извиняюсь.

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

Чувствуется, что Вам эта задача тоже интересна.

Мне интересны задачи оптимизации программ (и алгоритмов), и приложение их к аппаратуре (SSE, AVX, GPU). Не только в этой теме, а и вообще.
А задача доказательства минимальности ... Я сделал несколько подходов, для разных цепочек, для некоторых даже доказал что нет минимальных некоторых видов (потому что перебрал их все), но все они упираются в огроменное время вычислений. Почему у Hugo считается значительно быстрее я не разбирался, думаю дело в алгоритме (что по каким остаткам проверять или разлагать), а не в его реализации.

gris в сообщении #1566583 писал(а):

Я произвёл сплошной перебор до 250 000 000 000! (это не факториал!) и не нашёл шестёрок особого вида, а значит нет и пентадекатлона.
Кто хочет, может продолжать.

Думаю кроме Макаровой никто не захочет: хоть Вы и не озвучили затраченное время на проверку этих 25e10 чисел, но его несложно прикинуть, а все могут взять калькулятор и посчитать сколько времени понадобится для доказательства минимальности 15-ки с такой скоростью перебора, которая пока что порядка 8e34. И вероятность что 15-ка есть до 1e22 (и думаю и до 1e27) скорее всего ничтожна.

И самое главное: Вы в программе перебираете числа с шагом 640 (из миллиона чисел от 625e6 до 626e6 лишь почти 50 тысяч чисел простые) и для каждого из них запускаете медленную numdiv. Но если потребовать отсутствия в цепочке высоких степеней большого (больше тысяч) простого, то тройку можно разместить в 15-ке лишь единственным (с точностью до зеркальности) способом - квадрат должен стоять на первом (или последнем) месте и никак иначе (в середине будет конечно ещё и второй квадрат тройки). Аналогично с квадратом пятёрки, он обязан быть только на 6-м месте (с точностью до зеркальности), в итоге на первом месте получается коэффициент 45 и никак иначе (либо он же только на последнем месте). Других вариантов для 15-ки не существует, если не привлекать степени выше первой для неизвестного простого в каждой позиции. Уже это в итоге даёт увеличение шага проверки центрального числа до двух вариантов (45 слева или справа на краю) для $45\cdot64=2880$ чисел или каждые 1440 чисел. Уже это более чем вдвое быстрее перебора лишь по центральному простому. Плюс здесь вместо медленной numdiv на первом (или последнем) месте можно использовать гораздо более быструю isprime потому что там осталось найти лишь ровно одно простое в первой степени.
Одновременно с этим автоматически оказывается что и на местах 4, 6, 10 (когда 45 слева) тоже осталось найти лишь одно простое в первой степени и проверку тоже можно сделать быстрой isprime вместо медленной numduv. Причём на этих местах коэффициенты всегда ровно 12, 50, 18 соответственно, а значит шаг проверки можно ещё увеличить чтобы числа на этих местах гарантированно делились на вот эти коэффициенты, т.е. с 2880/2 до 14400/2=7200 или в 11 раз больше шага только по центральному простому.
Дальнейший учёт вариантов размещения простых 7, 11, 13 (а они все обязаны быть в цепочке, в степени 2 или 3 или 5 и/или ещё и в первой) даёт если не ошибаюсь 806 варианта размещения всех этих простых и величину шага проверки от 7207200 до 7236072072036007200 для разных вариантов. Понимаете, уже не по 650 чисел можно проверять за раз, а по миллионам или квадриллионам. И это всё ещё будет доказательством минимальности и полным перебором.

Есть правда одна тонкость. Вовсе не обязательно проверять все эти 806 вариантов, почти во всех них присутствуют неизвестные простые в квадрате, но такие простые не могут находится совсем уж в любом месте цепочки, их вообще допустимо лишь 24 варианта и практически все они нереализуемы потому что цепочек с двумя и более квадратами почти всегда просто не существует, либо вообще в целых, либо в простых. Т.е. эти 24 варианта дают не все возможные варианты сочетаний, а максимум несколько. И эти несколько вариантов в принципе вполне можно проверить отдельно, перебрать $10^{16}$ простых на PARI конечно нереально, но вот на нормальном языке (C/C++, асм, может ещё что-то из новых) уже не выглядит неподъёмным. Я тут недавно прикидывал, вроде бы получается за пару суток проверить отсутствие решения для каждого из 24-х вариантов с квадратами, но для этого надо писать непростую программу на асме с AVX2 (С тут не помощник, про остальные вообще молчу), да и достигнется ли такая скорость заранее непонятно, это скорость лишь самого внутреннего цикла, а что там будет снаружи и насколько оно затормозит ещё большой вопрос.

И это я ещё не касался вопроса ускорения счёта использованием внешних программ (типа моих ускорителей).

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

-- 12.10.2022, 22:01 --

gris
Что 25e10, что триллион - это всё ни о чём. Надо то до 8e34 (если не обнаружится сильно-сильно меньшая 15-ка, что ну очень сомнительно). И везение тут не особо поможет, если 15-ки нет до 1e26, то хоть с везением, хоть без него, но её там не найти. А если случайно и наткнуться на достаточно большую (вдруг и правда повезёт и она есть где-то немногим выше 1e26), то не доказать что она минимальная.
Потому я видел энтузиазм Макаровой, но кроме улыбки он ничего более не вызывает.
Если честно, просто жалко смотреть как люди (и их компы) занимаются бесполезной работой, можно же гораздо эффективнее считать (даже без моих программ, не в них дело). Но что-то объяснять Макаровой лично у меня категорически не хватает терпения, потому пусть считает что и как хочет.

gris
Если будет желание разобраться, то объяснить почему те же тройка и пятёрка должны быть в строго определённых местах (и потому можно перебирать с гораздо большим шагом чем 32p) несложно. Всего лишь аккуратно выписать все возможные варианты (их типа 9+9+9=27 для тройки и 15+15+15+5=50 для пятёрки) и чётко указать почему почти все они недопустимы. Несколько муторно и объёмно, но ничего сложного для понимания.

[Yadryara]

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

А задача доказательства минимальности ... Я сделал несколько подходов, для разных цепочек,

Тут есть ещё 3 стартовых подквадратных числа с шагом 450. Кроме 281 ещё 331, 119 и 169. Все они дают решения, но повыше.

$2p^2$ и $4p$ должны быть обязательно, а вот вместо $9p$ надо проверять ещё $3p^2$, а вместо $25p$ — $5p^2$.

Про 5-е число пока молчу.

[Dmitriy40]

Yadryara
$D(k=6)$ я не занимался, только $D(k=12)$ (от десятки и длиннее, в разных вариантах) и некоторыми с большим $k$.

[Yadryara]

А я вот занялся. Отсёк 5-ю степень простого. Не забыв, что 243 всё-ж таки входит в 4-ку.

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

вместо $9p$ надо проверять ещё $3p^2$, а вместо $25p$ — $5p^2$.

И в ту же самую четвёрку входит $5p^2$. А именно 245.

Вот, собственно и всё.

Итак, "я себе уже всё доказал". А вот и семёрка наименьших пятёрок по 6 делителей:

 1.   10093613546512321     ( 281 )

 2.   14414905793929921     ( 169 )

 3.  266667848769941521     ( 281 )

 4.  562672865058083521     ( 169 )

 5. 1579571757660876721     ( 281 )

 6. 1841337567664174321     ( 119 )

 7. 2737837351207392721     ( 331 )

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

Здесь представлены все 4 различных стартовых числа. А других и нет.

Как Hugo ухитряется доказать минимальность меньше чем за секунду, пока по-прежнему непонятно. Dmitriy40, будем думать? Я ещё подумаю.

[Yadryara]

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

Что 25e10, что триллион - это всё ни о чём.

Грубовато, конечно. Но по сути верно. Это слишком маленькие числа.

Наименьшая десятка начинается с $2973879756088065948$. А это 2 миллиона 973 тысячи триллионов.

У меня вопрос к Hugo. При поиске 10-ки Вы могли пропустить более длинные цепочки? Или для каких-то более длинных цепочек, например для 15-ки, можно записать

$2973879756088065948 < T(6,15) \leqslant 80215613469168729088982885848674841$

Или для всех длин 11-15 можно в качестве нижней границы взять число не меньше минимальной десятки?

[Huz]

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

У меня вопрос к Hugo. При поиске 10-ки Вы могли пропустить более длинные цепочки? Или для каких-то более длинных цепочек, например для 15-ки, можно записать

$2973879756088065948 < T(6,15) \leqslant 80215613469168729088982885848674841$

Или для всех длин 11-15 можно в качестве нижней границы взять число не меньше минимальной десятки?

My journey started (in 2009!) with A165497 and A165501, so my code has always searched for chains of at least a specified length: for the benefit of A292580 I do separate checks at the end to verify that they are exactly the requested length, and not longer.

So yes, having completed the $T(6,10)$ search, I have also established a lower bound for $T(6,11)$ etc.

(This was a problem for $T(6,8)$ - I had to do a secondary search specifying $T(6,9) + 2$ as the minimum to find the published value, and record it as an exception in the script I use to generate the a-file.)