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

[Yadryara]

Huz, то есть по-Вашему это верно?

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

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

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

Я специально переспрашиваю, подумайте, пожалуйста, не торопитесь с ответом.

[Dmitriy40]

Это легко проверить Hugo напрямую: запустить проверку с 8.0215613469e34, найдётся ли пятнашка (как минимальная десятка) или нет. Ставлю что найдётся, т.е. условие выполнено, 3e18 нижняя граница для всех цепочек 11 и длиннее и нет никакого смысла искать пятнашку ниже.

[Huz]

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

А вот и семёрка наименьших пятёрок по 6 делителей

I agree that those are the 7 smallest examples. I think the first example not divisible by 7 is 5344962129269790721.

-- 13.10.2022, 13:07 --

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

Huz, то есть по-Вашему это верно?

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

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

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

Я специально переспрашиваю, подумайте, пожалуйста, не торопитесь с ответом.

What time is needed? Yes, from my own results I consider it proven that $2973879756088065948 < T(6,15) \leqslant 80215613469168729088982885848674841$.

[Yadryara]

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

3e18 нижняя граница для всех цепочек 11 и длиннее и нет никакого смысла искать пятнашку ниже.

Звучит слишком категорично. Насколько я понимаю, это была идея gris'а, искать настолько низко.

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

Надеюсь, уважаемый gris всё же прокомментирует.

Желающим заняться нижней границей вполне можно искать её, например, для 11-ки, только нужно обязательно свериться с результатами Hugo, чтоб не считать одно и то же.

[Dmitriy40]

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

Вот программа: Поиск шестёрок определённого типа.

{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! (это не факториал!) и не нашёл шестёрок особого вида, а значит нет и пентадекатлона.
Кто хочет, может продолжать.

Так как в пятнашке обязательно или 6-е или 10-е место содержит число вида 18p, которое можно проверять быстрой isprime, то добавив даже вот в эту программу дополнительное условие для его проверки время проверки диапазона по i с 625e7 по 635e7 (в 10 раз больше указанного в листинге) сокращается с 46.5с до 3.8с. Добавляется всего лишь перед первым if-ом код

x=m%18; if(((x==2 && isprime((m-2)/18)) || (x==16 && isprime((m+2)/18))),

Аналогично можно учесть и факт обязательного наличия на 4-м или 12-м месте числа вида 12p, ещё несколько ускорив перебор.
После этого порядок проверки numdiv роли уже не играет, разница от любого порядка проверки станет слишком незначительной.

[Huz]

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

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

I am delighted for people not to trust my results - no program of this complexity is free of bugs, independent confirmation is always valuable.

(Indeed, in looking at values of T(3,5) prompted by your recent comments, I found two more bugs; happily, they were not bugs that affected any previous results.)

[gris]

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

Насколько я понимаю, это была идея gris'а, искать настолько низко.

Как интересно звучит:) Никогда не отмечал в себе подобного любопытства . Но если меня спрашивают, я всегда отвечаю.
Достаточно крупный и энергичный проект всегда привлекает внимание. Я вовсе не ставил под сомнение теоретические либо практические результаты его участников, но слегка прикоснуться хотелось. Именно слегка, потому что иначе нужно основательно погрузиться в теорию, изучить то, что уже сделано, а при возможности самому попробовать изобрести маленький велосипедик. Но нет такой возможности.
Даже не очень мощный комп с его начинкой даёт возможность погрузиться в своё альтернативное детство и посчитать кучу интересных вещей в образе себя восьмиклассника. О, какие возможности есть у современных школьников! Ага. Мои упражнения в написании простеньких программ про разные свойства пентадекатлона являются исключительно упражнениями в написании простеньких программ. Я не искал ни самого его, ни <грамматических> ошибок у подвижников процесса. Скажу откровенно, что очень большие числа мне не нравятся. Слишком много цифр. Чёрный квадрат мне милей, чем композиция VII.
Мой диапазон до триллиона. В нём нельзя ненароком споткнуться о пентъ, но много интересного можно посмотреть. Увы, эти мои таблички и "оптимизации" — просто забава, не имеющая практического применения:(

[Yadryara]

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

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

А надо бы поставить И Huz это подтвердил.

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

Скажу откровенно, что очень большие числа мне не нравятся.

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

Что касается того, почему уважаемый VAL начинал поиск примерно с 28-значных чисел, то ответ прост. Я, например, в начале темы об этом писал. Потому что 6-кратный шаг для того комплекта паттернов имел примерно тот же порядок.

Уж столько раз говорилось, что в начале темы речь шла только об одном-единственном комплекте паттернов. КМК37-11(эталонный комплект). Но ведь других комплектов тьма-тьмущая. И в них встречается шаг в миллионы и триллионы раз меньше, так что теоретически может найтись гораздо меньший(чем $10^{28}$) пентадекатлон.

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

I am delighted for people not to trust my results - no program of this complexity is free of bugs,

Ну то есть теперь за секунду всё-таки не можете доказать? Потому что надо рассматривать различные особые случаи.

[Huz]

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

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

I am delighted for people not to trust my results - no program of this complexity is free of bugs,

Ну то есть теперь за секунду всё-таки не можете доказать? Потому что надо рассматривать различные особые случаи.

The translation of this comes out somewhat garbled, but let me try to answer.

I'm sure there are remaining bugs in my program - but most bugs I have found have no effect on the correctness of previous findings. Occasionally I find a bug that affects a small amount of previous work, but in those cases I have never needed to rerun more than a week or two of calculations (and in each case the original result stands even after the recalculation).

So: if my code is perfect, the case is proved; even if my code is not perfect, previous experience suggests the result is very likely to be correct.

The worst example I had in the past was a bug in a factorization library I was using, which could give incorrect results for numbers $n: 2^{63} \le n < 2^{64}$. That affected a couple of years-worth of calculations - but luckily I had just acquired a new, much faster computer, and was able to rerun those years of calculations in just a few weeks. Even on that occasion, it turned out that all the results I had previously found were correct.

[Yadryara]

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

Это легко проверить Hugo напрямую: запустить проверку с 8.0215613469e34, найдётся ли пятнашка (как минимальная десятка) или нет. Ставлю что найдётся, т.е. условие выполнено,

Huz, Вы попробовали сделать как предложил Dmitriy40 ?

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

The translation of this comes out somewhat garbled, but let me try to answer.

Да, Вы, видимо, не поняли. Я о другом говорил. Весьма много первых пятёрок получается из этого паттерна:

$* \quad 2p^2 \quad 9p \quad 4p \quad 25p $

И именно с двумя последними цифрами "21" для первого числа цепочки.

Но кроме этого надо проверять ещё числа $p^5$, $3p^2$ и $5p^2$.

Вы всё это проверяете? И всё это успеваете сделать меньше чем за одну секунду?

[Yadryara]

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

I think the first example not divisible by 7 is 5344962129269790721.

Доработал прогу. Сделал её более универсальной. Менее чем за 2 секунды она находит первое число. За 120 секунд — первые 25 чисел. В том числе 5344962129269790721 на 13-м месте.

Все найденные совпадают с https://oeis.org/A141621/b141621.txt

write("begin.tmp","is begin");
t0=getwalltime();
allocatemem(2^27);
start=0;
stop= 10000000;
v=[119,169,281,331];
m=0; print();
{for(i=start,stop,
for (j=1,4,
x=450*i+v[j];n=x^2*2-1;
if (isprime(x) && isprime((n+2)/9) && isprime((n+3)/4) && isprime((n+4)/25) && numdiv(n)==6, m=m+1; print(m, "   ",n, "   ",numdiv(n), "   ",numdiv(n+1), "   ",numdiv(n+2), "   ",numdiv(n+3), "   ",numdiv(n+4));print())
))}
tob=getwalltime()-t0;
print();
printf("TIME = %0.2f seconds",tob/1000);
write("end.tmp","is end");
quit;

[Huz]

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

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

Это легко проверить Hugo напрямую: запустить проверку с 8.0215613469e34, найдётся ли пятнашка (как минимальная десятка) или нет. Ставлю что найдётся, т.е. условие выполнено,

Huz, Вы попробовали сделать как предложил Dmitriy40 ?

No, I didn't try it: I don't understand it (and had not realised it was addressed to me). The translation comes out as "run the check with 8.0215613469e34, whether there is a tag (as a minimum ten) or not". I don't understand what "tag" is supposed to mean, or what check is supposed to be run, or what doing this check is intended to prove.

Цитата:

Да, Вы, видимо, не поняли. Я о другом говорил. Весьма много первых пятёрок получается из этого паттерна:

$* \quad 2p^2 \quad 9p \quad 4p \quad 25p $

И именно с двумя последними цифрами "21" для первого числа цепочки.

Но кроме этого надо проверять ещё числа $p^5$, $3p^2$ и $5p^2$.

Вы всё это проверяете? И всё это успеваете сделать меньше чем за одну секунду?

If I correctly understand the question, my code doesn't work quite like that. Given $t$ as the required number of divisors, it assigns each possible prime at each possible power to satisfy each of the odd primes dividing $t$. So for $t=12$, it will assign one of $p^2, p^5, p^{11}$ to each of the positions along the chain, until all of them are assigned (or until the number of values to check is small enough). It then uses the Chinese Remainder Theorem to determine an overall modular constraint for that selection of assignments, and for each value matching that modular constraint checks if we have a solution.

That's the basic theory at least, ignoring lots of optimizations. For example if an assignment leaves the unassigned part of some value $v_i$ forced to be a square, I take advantage of that to require that every assignment of $p^e$ to a different value $v_j$ has $i -j$ being a quadratic residue $\pmod{p^e}$ - for $T(3,5)$ that kicks in as soon as a power of 2 gets assigned. If two values are forced to be square I just solve the Pell equation, so those cases are resolved pretty much instantly.

In fact, for $T(3, 5)$, the code tells me that there are very few valid options for placing powers of 2, 3 and 5 (ignoring 7 cases such as $p^5$ where one value is completely specified):

(Оффтоп)

. 2 3^2 2^2 5^2
. 2 3^2 2^2 5
. 2 3 2^2 5^2
. 2 3 2^2 5

.. and all but the first of those give Pell equations.

[Dmitriy40]

Huz
I suggested checking whether the program can find chain length of 10 as part of the known chain length of 15 (in general, any, and not only 15, but any known chain longer that 10). For example, by running a check starting from about 8e34.

[Huz]

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

Huz
I suggested checking whether the program can find chain length of 10 as part of the known chain length of 15 (in general, any, and not only 15, but any known chain longer that 10). For example, by running a check starting from about 8e34.

Ah, thanks for the clarification.

My code is not optimized for searching a range that is small compared to its start point, so to do this in a reasonable time I need to subtract the lower end of the range when calculating whether to recurse further or not with a little patch:

+#ifdef DMITRY
+    mpz_sub(Z(r_walk), Z(r_walk), min);
+#endif

With that I can easily find the known $T(6,11)$ and $T(6,12)$ values as $T(6,10)$ candidates, using a range $\pm 100$ around the known value:

% ./dmitry-pcoul -x9887353188984012120246:9887353188984012120446 -f7 12 10
001 pcoul(12 10) -f7 -x9887353188984012120246:9887353188984012120446
202 Candidate 9887353188984012120347 (0.00s)
202 Candidate 9887353188984012120346 (0.01s)
367 pcoul(12, 10): recurse 504, walk 393, walkc 62 (0.01s)
200 f(12, 10) <= 9887353188984012120346 (0.01s)
% ./dmitry-pcoul -x120402988681658048433848:120402988681658048434048 -f7 12 10
001 pcoul(12 10) -f7 -x120402988681658048433848:120402988681658048434048
202 Candidate 120402988681658048433950 (0.00s)
202 Candidate 120402988681658048433949 (0.00s)
202 Candidate 120402988681658048433948 (0.00s)
367 pcoul(12, 10): recurse 504, walk 393, walkc 73 (0.01s)
200 f(12, 10) <= 120402988681658048433948 (0.01s)
% 

However the known $T(6,13)$ and higher fall outside the range I'm able to check for $T(6,10)$ - if CRT tells me my candidates are of the form $am + b$, I expect to set $a$ to successive values for checking, and it doesn't make sense to allow $a$ to be more than 64 bits as it would need to be for those cases.

[Dmitriy40]

Ну то есть если бы пентадекатлон был менее 3e18, то он был бы найден. Что и хотелось выяснить.