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

[EUgeneUS]

Huz

Thank you for the clarification

I have larger ranges calculated, so I didn’t realize what could happen in smaller ones.

[Dmitriy40]

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

О D12n13: проверил все паттерны без неизвестных квадратов и с LCM=17304487200 и больше, новых решений не найдено.

Проверены и все 418 паттернов с LCM=7214407200, но лишь с ключом -p2e5, для полноты осталось доказать что решений нет и в интервале 2e5<p<6e5 (досюда порог уже опустил), это доказательство пока ещё в процессе, нужно ещё до недели-двух.

[Dmitriy40]

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

осталось доказать что решений нет и в интервале 2e5<p<6e5

Доказал.
Нашлось много десяток (maxlen=10) и ни одной более длинной.

[Yadryara]

Интересовались моим мнением. Если я правильно понял Дмитрия, то с проверкой 13-к сейчас дело обстоит так:


$\tikz[scale=.08]{ \fill[green!90!blue!50] (0,30) rectangle (81,70); \fill[green!70!blue!80] (0,10) rectangle (81,30); \fill[green!90!blue!50] (68,0) rectangle (81,10); \draw (0,140) rectangle (10,150); \draw (10,140) rectangle (55,150); \draw (55,140) rectangle (68,150); \draw (68,140) rectangle (81,150); \draw (0,130) rectangle (10,150); \draw (10,130) rectangle (55,140); \draw (55,130) rectangle (68,140); \draw (68,130) rectangle (81,140); \draw (0,120) rectangle (10,130); \draw (10,120) rectangle (55,130); \draw (55,120) rectangle (68,130); \draw (68,120) rectangle (81,130); \draw (0,110) rectangle (10,120); \draw (10,110) rectangle (55,120); \draw (55,110) rectangle (68,120); \draw (68,110) rectangle (81,120); \draw (0,100) rectangle (10,110); \draw (10,100) rectangle (55,110); \draw (55,100) rectangle (68,110); \draw (68,100) rectangle (81,110); \draw (0,90) rectangle (10,100); \draw (10,90) rectangle (55,100); \draw (55,90) rectangle (68,100); \draw (68,90) rectangle (81,100); \draw (0,80) rectangle (10,90); \draw (10,80) rectangle (55,90); \draw (55,80) rectangle (68,90); \draw (68,80) rectangle (81,90); \draw (0,70) rectangle (10,80); \draw (10,70) rectangle (55,80); \draw (55,70) rectangle (68,80); \draw (68,70) rectangle (81,80); \draw (0,60) rectangle (10,70); \draw (10,60) rectangle (55,70); \draw (55,60) rectangle (68,70); \draw (68,60) rectangle (81,70); \draw (0,50) rectangle (10,60); \draw (10,50) rectangle (55,60); \draw (55,50) rectangle (68,60); \draw (68,50) rectangle (81,60); \draw (0,40) rectangle (10,50); \draw (10,40) rectangle (55,50); \draw (55,40) rectangle (68,50); \draw (68,40) rectangle (81,50); \draw (0,30) rectangle (10,40); \draw (10,30) rectangle (55,40); \draw (55,30) rectangle (68,40); \draw (68,30) rectangle (81,40); \draw (0,20) rectangle (10,30); \draw (10,20) rectangle (55,30); \draw (55,20) rectangle (68,30); \draw (68,20) rectangle (81,30); \draw (0,10) rectangle (10,20); \draw (10,10) rectangle (55,20); \draw (55,10) rectangle (68,20); \draw (68,10) rectangle (81,20); \draw (0,0) rectangle (10,10); \draw (10,0) rectangle (55,10); \draw (55,0) rectangle (68,10); \draw (68,0) rectangle (81,10); \node at (5,145){\text{№}}; \node at (31,145){\text{LCM}}; \node at (62,145){\text{Pat}}; \node at (75,145){\text{Done}}; \node at (5,135){\text{1}}; \node at (45,135){\text{7207200}}; \node at (63,135){\text{34}}; \node at (5,125){\text{2}}; \node at (44,125){\text{50450400}}; \node at (62,125){\text{114}}; \node at (5,115){\text{3}}; \node at (44,115){\text{79279200}}; \node at (62,115){\text{164}}; \node at (5,105){\text{4}}; \node at (44,105){\text{93693600}}; \node at (62,105){\text{124}}; \node at (75,105){\text{}}; \node at (5,95){\text{5}}; \node at (43,95){\text{554954400}}; \node at (62,95){\text{270}}; \node at (75,95){\text{}}; \node at (5,85){\text{6}}; \node at (43,85){\text{655855200}}; \node at (62,85){\text{264}}; \node at (75,85){\text{}}; \node at (5,75){\text{7}}; \node at (42,75){\text{1030629600}}; \node at (62,75){\text{382}}; \node at (75,75){\text{}}; \node at (5,65){\text{8}}; \node at (42,65){\text{7214407200}}; \node at (62,65){\text{418}}; \node at (74,65){\text{418}}; \node at (5,55){\text{9}}; \node at (41,55){\text{17304487200}}; \node at (63,55){\text{34}}; \node at (75,55){\text{34}}; \node at (5,45){\text{...}}; \node at (5,35){\text{25}}; \node at (35.8,35){\text{5436568048111200}}; \node at (62,35){\text{110}}; \node at (74,35){\text{110}}; \node at (5,25){\text{26}}; \node at (34.5,25){\text{21096420035090400}}; \node at (62,25){\text{44}}; \node at (75,25){\text{44}}; \node at (5,15){\text{27}}; \node at (32.5,15){\text{7236072072036007200}}; \node at (62,15){\text{26}}; \node at (75,15){\text{26}}; \node at (32.5,5){\text{Total}}; \node at (62,5){\text{3408}}; \node at (75,5){\text{2056}}; }$

[EUgeneUS]

Dmitriy40
Поздравляю!
А Вы pcoul считаете или своими программами?

[Dmitriy40]

EUgeneUS в сообщении #1593446 писал(а):

А Вы pcoul считаете или своими программами?

И так и так: я же написал что pcoul считала с ограничением -p2e5, а все большие значения простых под квадратом проверялись моими программами (их кажется три или 4 разных варианта было) и разумеется именно ими и были найдены все 10-ки (pcoul ничего кроме конечного результата не находит). Моими потому что они считали на порядок быстрее для больших значений -p (специально под это оптимизировались) и в 1.5-2 раза быстрее для малых (потому что проверяли сразу несколько паттернов за раз в отличии от pcoul с ключом -W, 418 паттернов свернулись в 308 разных вариантов).

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

Если я правильно понял Дмитрия,

Похоже что правильно.

PS. Как-то более двух месяцев счёта совершенно не радуют, а для меньших LCM время будет только расти. Пока не собираюсь дальше считать, есть другие задачи, а там посмотрим.

[Huz]

Note that I am working on a further improvement, but it is not ready yet.

I extended my Perl code to find solutions for A309981, and then also extended the C code to do the same. To my surprise the Perl code was faster for about half the cases, and that appears to be because of an additional type of check it does. So I have added that to the C code.

It will add new options -c<n> ('check', default 0), -cp<n> ('check_prime', default 0), -cr<d> ('check_ratio', default 1.0), -cc<n> ('check_chunk', default 'check').

During initialization, it will analyse all moduli from 2 to 'check' (skipping moduli that are not 'check_prime'-smooth, if check_prime > 0) looking for modular values that are disallowed for the given chain. It will then combine the moduli into bitvectors of size at most 'check_chunk' bits, discarding any that do not have a reject ratio of at least 'check_ratio'. At runtime, during linear walk, we then do a single mod calculation and bitvector-lookup for each of those combined bitvectors aiming to reject a value before doing any further primality or factorization tests. Obviously if only one value remains allowed for a particular modulus, we handle that directly.

The 3 types of constraint are pretty simple: 1) for a modulus m and target divisors t, if $\tau(m) > t$ then no value in the chain can be a multiple of m, and if $\tau(m) = t$ then no value $> m$ can be; 2) writing $r(m)$ for rad(m): if $\tau(m)$ does not divide t then $mx \pmod{m r(m)}$ is disallowed for each x coprime with $r(m)$; 3) if a square is fixed at some value, then quadratic non-residues $\pmod{m}$ are disallowed.

Some experimentation will be required to find optimal values for the 4 new options; I believe that a speedup of between x 2 and x 10 is realistic, but it is likely to vary a lot for specific values.

[EUgeneUS]

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

I believe that a speedup of between x 2 and x 10 is realistic, but it is likely to vary a lot for specific values.

It's a good news!

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

Some experimentation will be required to find optimal values for the 4 new options;

Well.
As you probably know, we (Demis and I) are trying to find a new estimate for D(12,14).
I'm sure:
1. The current estimate for D(12,14) is not the minimum
2. It can be improved several times in the set of "promising" patterns that we test

I'm not sure, but I hope that on the tested set of "promising patterns" the estimate can be improved by a factor of 10 or more. Therefore, the current check is implemented until 21e31 (keys: -x21e31 or -x14e31:21e31 f.e.).

However, the check is now very slow: about 5-6 million seconds per pattern in one thread on the Demis side and 7-9 million seconds per pattern in one thread on my side

Acceleration by 5-10 times would allow:
a) check "promising" patterns up to 21e31 faster
b) think about testing promising patterns to a known estimate - about 200e31 (which is not currently planned)

The search is carried out with the restriction: -p500 (may be of the form -p50:500 or -p50:200).

In the context of these searches, your recommendations for installing new keys would be very valuable.

[Huz]

EUgeneUS в сообщении #1593470 писал(а):

In the context of these searches, your recommendations for installing new keys would be very valuable.

Sorry, I don't understand what you mean by "installing new keys", could you rephrase?

[EUgeneUS]

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

orry, I don't understand what you mean by "installing new keys", could you rephrase?

Yaeeehhh

Цитата:

If Google Translator doesn’t help, then who will help

Well. (now & below - google tr-n)
You discovered how to speed up the calculation.
To speed up the calculation, you entered four parameters.
Well.
But how to choose these four parameters - the question remained open.
Well.
And now the question is What values ​​of the new parameters need to be (better) set to finding as We find

[Huz]

EUgeneUS в сообщении #1593540 писал(а):

how to choose these four parameters

Ah ok, as I said above: some experimentation will be needed.

The optimal chunk size is likely dependent on your computer's onboard cache lines: Dimitry probably knows more about that sort of thing than I do. I have had reasonable results with -cc32768. (Note that it is a size in bits, so that will create bit-vectors at most 4K long.)

The optimal ratio will be determined mostly by the magnitude of the numbers you are testing. A check ratio of 1.1 would mean that for every 11 values tested, 1 would be rejected immediately, the rest would be passed through. The cost of doing the test is essentially one bigint division; the saving, when it rejects a number, is typically one or more primality tests. My guess is that a ratio somewhere in the range 1.1 to 1.001 would work.

The optimal values for check and smoothness are mostly about finding moduli that will give a good ratio - if you choose a ratio carefully you don't need to worry too much about the precise values of 'check' and 'check_prime'. I usually set check in the range 1000 to 20000, and smoothness either not set or set to around 100.

Note though that my previous experience with these options is with my Perl code, where I have typically done short runs (of around 10 minutes), and the initialization cost for high values of 'check' can be prohibitive. The C code has a much lower initialization cost, and you are probably doing runs much longer than 10 minutes, so it is probably worth trying a lower ratio (maybe 1.0001 or 1.0002) and higher 'check' (perhaps in the range 50000-100000).

[Huz]

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

Ah ok, as I said above: some experimentation will be needed.

Further on this, there are three things to consider: the initialization, the runtime cost, and the runtime benefit.

The initialization cost is small for the cases I've tested, so I haven't attempted to optimize this. If you find that are still getting runtime benefits for check or check_chunk values high enough that the initialization cost becomes significant - minutes rather than seconds - let me know, and I'll look into the possibility of making the initialization faster.

The runtime cost has two parts: calculating the modular value, which involves dividing a bigint by a 32-bit integer to find the remainder; and looking up whether that remainder is permitted, for which the cost is determined by the length of the bit-vector, and thus the extent to which the on-chip cache lines get flushed. (You could also say there is a third part, the probability that the check is wasted because this value is not rejected, which is a function of the check ratio.)

The runtime benefit is that we save the average cost of rejecting a value through the existing primality/factorization tests. You can approximate this from existing data by looking at the '367' log line at the end of a run: for the normal case where almost all of the time is spent in linear search, the average cost to reject a value is close to the total runtime divided by the "walkc" count shown here.

To optimize the settings by experiment, I would suggest picking a min/max range that you know will take about 10s to run, and trying various settings to see which runs fastest. When it gets difficult to distinguish true improvements from noise, increase the range by a factor of 6-10 for fine-tuning; and if necessary do the same again for ultra-fine tuning.

[EUgeneUS]

Huz
Thank you for the clarification! When this software is available under Windows, I'll try some experiments with new keys. Then more questions will likely arise.

[Huz]

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

Note that I am working on a further improvement, but it is not ready yet.
[...]
It will add new options -c<n> ('check', default 0), -cp<n> ('check_prime', default 0), -cr<d> ('check_ratio', default 1.0), -cc<n> ('check_chunk', default 'check').

After a long bout of debugging, this is working correctly for A309981 and giving good improvements, so I tested it with A292580; it appears to work correctly there too, but is not currently giving any improvements (tested on $D(12,9)$).

I suspect that this is because at the moment it looks for constraints first, and with A292580 there are few constraints to find until we select a batch and apply it - with A309981 the divisor counts are not all the same, so there is much more opportunity to find useful constraints a priori. So the next step is to modify the code to look for constraints only after a batch has been applied, which will involve some more tricky reworking of the code.

For now I plan to have it do this only for those cases where a single batch is selected with -b; I'll consider later whether it makes sense to do it repeatedly for a run over all batches or over a range of batches.

[EUgeneUS]

Цитата:

Ах, не солгали пpедчувствия мне
Да мне глаза не солгали
Лебедем белым скользя по волне
Плавно навстpечу идёт паpоход

$T(6,14)$ ($D(12,14)$) улучшено более чем в 10 раз!

Цепочка начинается с числа $182417228439838813052353038969945$
Цепочка найдена DemIS'ом с помощью pcoul.