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

[Huz]

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

Hugo, now I checked all my text, Google quite clearly translated it into English, in some places the terms are incorrect (the replacement of "prime numbers" with something else is especially incomprehensible), but the context is clear.

In the preliminary remarks I was confused by the phrase "in the first degree" ("In the first it remains to find only one large prime in the first degree") which sounds like a technical term indicating a type of prime, but I suspect is actually a non-mathematical phrase similar to the English "in the first place". And I guess that "the simplicity of a large number" actually meant "the primality of a large number". I missed where it is specified, but I assume that a number of prime powers are being assigned to the elements, and the "coefficient" $v_i$ is the product of assigned prime powers for each element.

It is not clear how the prime powers are chosen, nor how many must be assigned. Since my own code is for minimization, I recursively try every possibility until all odd factors of $n$ (the number of divisors) have been accounted for in each element. (I use a heuristic to break the recursion early when that would be faster.)

Everything else up to the first code fragment is clear, I still need to study what follows in more detail.

Цитата:

About books, I use Intel official documentation and materials of Agner Fog

Thanks, I'll take a look at those. I have some assembler experience (mostly Z80, 6502, 6800, 68000, 80x86, SPARC and ARM), and usually prefer the technical documentation.

-- 07.06.2022, 13:42 --

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

PS: T(36,11) <= 8807537694598756405759232050726160223249927395349997820

Thanks!

[EUgeneUS]

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

"in the first degree" ("In the first it remains to find only one large prime in the first degree")

It's translator artefact. Must be "in the first power" ($p^1$).
Russian word "степень" may be translate as "degree" and as "power" (2nd case - only in the math context).

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

And I guess that "the simplicity of a large number" actually meant "the primality of a large number".

Yes, you'r right.

-- 07.06.2022, 17:18 --

mathematician123

(детали по работам Беннетта)

ИМХО, Вы и сами это уже знаете, но на всякий случай соберу в одном месте.
1. По ссылке, приведенной на mathoverflow.net есть работа Беннета "Rational approximation to algebraic numbers of small height: the Diophantine equation $|a x^n - b y^n|=1$, By Michael A. Bennett at Princeton". По ссылке, конечно, не "настоящее" место публикации, но выходные данные статьи есть на титульном листе pdf-ки.

2. Теоремы 1.1. оттуда вполне достаточно.

3. Однако, перед формулировкой этой теоремы Беннетт пишет:

Цитата:

Recently, B. M. M. de Weger and the author [BdW] (see also [Mi]) strengthened
Domar's theorem by showing that, if $ab \ne 0$; $n \ge 3$ and $c \pm 1$, then (1.2) has at most one
solution in positive integers $(x; y)$, except possibly for those $(a; b; n)$ (where, without loss of
generality, we assume that $b > a \ge 1$) with

$$ \text{(1.3) } b = a + 1; 2 \le a \le \min \left\lbrace 0.3n; 83\right\rbrace \text{ and } 17 \le n \le 347$$

4. В нашем случае $b=2$, $a=1 < 2$, так что под второе условие не попадаем, и этого результата тоже хватает.

5. В библиографии эта работа (от 1998 года) указана так:

Цитата:

[BdW] M. Bennett and B. M. M. de Weger, On the Diophantine equation $|a x^n - b y^n|=1$, Math. Comp. 67 (1998), 413-438.

[mathematician123]

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

(детали по работам Беннетта)

5. В библиографии эта работа (от 1998 года) указана так:

Цитата:

[BdW] M. Bennett and B. M. M. de Weger, On the Diophantine equation $|a x^n - b y^n|=1$, Math. Comp. 67 (1998), 413-438.

(Оффтоп)

Эту работу можно скачать здесь.

[Yadryara]

Поздравляю всех с находками!

Huz, а Вы можете запостить здесь Ваш исходный код на C(++) для самого простого случая? Например, для 12 делителей.

[EUgeneUS]

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

It is not clear how the prime powers are chosen, nor how many must be assigned.

It's basing on technique for finding "long runs" proposed by Vladimir.
In general.
1. It needs to place "very small" primes (such as $2, 3, 5$ and so on, it depends on length of the run) in the run considering Chinese remainder theorem.
2. Then we place a "small" primes (such as $11, 13, 17$ and so on), may be in powers more then one - as it demand factorisation.
3. Now we must find for each number in the run or one "big" prime, or product of the two "big" primes.
4. The permutations of the "small" primes bring to many variants (we call them "patterns"). F.e. there was 1448 46080 "patterns" for finding upper bound for $T(6, 15)$
5. Dmitriy compiles own accelarator for each "pattern". It accerates finding from some hunderds to one thousand times vs PARI/GP without accelarators.

[Yadryara]

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

F.e. there was 1448 "patterns" for finding upper bound for $T(6, 15)$

46080 patterns for each subclass.

[EUgeneUS]

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

46080 patterns for each subclass.

of course,
1448, AFAIR, was for other run.

[VAL]

mathematician123 в сообщении #1556702 писал(а):

ос. Как правильно: Михайлеску или Михэйлеску?

Я привык писать через "а". Что вовсе не означает, что это истина в последней инстанции.
К счастью, для нас это вопрос не актуальный

[Dmitriy40]

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

"in the first degree"

Yes, it surprised me too, it's more correct "in first power", but I didn't fix it anymore, I hoped it would be clear and so.
EUgeneUS has already answered everything for me.

[Huz]

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

Huz, а Вы можете запостить здесь Ваш исходный код на C(++) для самого простого случая? Например, для 12 делителей.

My code is more general than that. The primary tool I've been using is the perl program oul ("oneseq upper limit"). When targetting T(n/2, k), the first levels of recursion are for primes $p \le k$ via the forcep function, which iterates over all sets of powers $p^x: (x+1) \mid n$ for each element; the remaining levels of recursion occur via the recurse function, which first decides which element to target next, then iterates over available powers, within which it iterates over primes $p > k$.

Each level of recursion assigns a prime power to some element, where the product of assignments to element $i$ is stored as $q_i$; the main recurse function concentrates on satisfying the highest odd prime dividing $t_i = n / \tau(q_i)$. When there are no more odd factors to satisfy in any element (or in some cases earlier), the recursion terminates with a call to the walk_v function.

There are special cases for walking those cases where some $t_i = 1$, or where one or more $t_i \equiv 1 \pmod{2}$, but the core case loops over this:

        if (all { gcd($o[$_], $q[$_]) == 1 } 0 .. $k - 1) {
            if ($print) {
                print STDERR $o[0] * $q[0], "\n";
            } else {
                return $o[0] * $q[0] if all { is_tau($o[$_], $t[$_] } 0 .. $k - 1;
            }
        }

In similar fashion to dmitry40's code, we have $q_i$ as the product of allocated prime powers for each $v_i$, $v_i = v_0 + i$, $a_q = \lcm(q_i: 0 \le i < k)$, $v_0 \equiv m \pmod{a_q}$ calculated by CRT, $o_i = (v_i + i)/q_i$. So for each $v_0 = m + x a_q$ we check first via gcd() that we will not supply a higher power of any fixed prime, then check whether $\tau(o_i) = t_i$ for all $i$.

The $print option in the above is there for those cases where the values are too large to factorize in the order we encounter them, such as for T(46,7). In this case I can print out all the candidates, then separately sort them and check in ascending order (using code that I have not yet tested).

If you'd like more information about specific parts of the code, feel free to ask more specific questions. :)

-- 07.06.2022, 22:51 --

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

$a_q = \lcm(q_i: 0 \le i < k)$

That is supposed to say "$a_q$ = lcm(...)", not sure how to make it say that.

[Yadryara]

Huz, Большое Спасибо.

Кто-нибудь понимает, как работает программа Huz ?

Специально просил объяснить на простейшем примере. Как было найдено вот это число?

https://oeis.org/A292580/a292580_2.txt писал(а):

T(6,8) 18652995711772 Hugo van der Sanden 2022-01-12

[Huz]

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

Специально просил объяснить на простейшем примере. Как было найдено вот это число?

https://oeis.org/A292580/a292580_2.txt писал(а):

T(6,8) 18652995711772 Hugo van der Sanden 2022-01-12

Ah, that was found by a different program gtauseq. This program uses a different approach: it analyses the specific case requested to find as many modular constraints as possible, then sequentially tests all cases that satisfy those constraints until it finds a solution.

This program has a number of options to control its behaviour. A separate program harness aims to find intelligent ways to invoke it to find new solutions across the space of all unresolved $(n,k)$. This code was originally written to find values for A165500 and A165501 (type "tauseq", option "-yt"), and later extended for other sequences such as this one (type "oneseq", option "-yo").

Having found a set of modular constraints, represented as bit vectors of width $m$, the core loop of this program (in Constraint.pm) is C code searching for the next element consistent with the known constraints:

        /* for each x, try v_0 = base + xm */
        for (; scl->iter < scl->limit; ++scl->iter) {
            found = 1;
            /* for each constraint, test if this x is valid */
            for (i = 0; i < scl->len; ++i) {
                scmod* scm = &scl->sc[i];
                ++count_tests;
                modval = ((scl->iter % scm->mod) * scm->multmod + scm->basemod) % scm->mod;
                off = modval >> 3;
                if ((off < scl->sc[i].veclen)
                        && (scl->sc[i].vec[off] & (1 << (modval & 7)))) {
                    ++count_skipped;
                    found = 0;
                    break;
                }
            }
            if (found) {
                /* return base + iter * mult */
                ...

Sadly, while there are lots of interesting things to say about A165500/1 for composite $n$, it is mostly uninteresting (and very hard to solve) for prime $n$ - it is currently known only up to $n < 23$. A future project will be to adapt oul to search for "tauseq" solutions: for composite $n \le 100$, it remains to prove minimal values for $n \in \{ 60, 72, 84, 90 \}$ and to demonstrate existence of expected solutions for $n \in \{ 77, 91 \}$.

If it is of interest, I can write separately about the various constraints gtauseq knows to discover for "oneseq" (A292580).

[Yadryara]

Huz, благодарю. Надеюсь уважаемый Dmitriy40, который вроде бы знает С, это прокомментирует.

Я понимаю как работают программы VAL, как работают программы Dmitriy40, но не Ваши.

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

say about A165500

Вы не заметили, что у нас на форуме есть специальный тег [oeis][/oeis]? Гораздо удобнее, если написано не A165500, а A165500. Можно навести указатель мыши и прочитать краткую инфу, а можно кликнуть и сразу перейти к самой последовательности.

Уважаемый Huz, а Вы читали вот этот пост?

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

А я тем временем ошибку у Хьюго нашёл. В том самом а-файле:

https://oeis.org/A292580/a292580_2.txt писал(а):

T(3,5) 10093613546512321 Jon E. Schoenfield 2017-09-19

[VAL]

mathematician123 в сообщении #1556702 писал(а):

Есть два доказательства. Первое: $M(2pq) \le 3$ для любых простых $p, q > 5$. Второе: если $d \equiv \pm 2 \pmod{12}$ и $gcd(p_i-1) > 2$, где $p_i$ - нечётные простые делители $d$, то $M(d) \le 3$.

Мне представляется, что наши новые (основанные на старых чужих работах ) оценки для $k \equiv \pm 2 \pmod{12}$ должны почти автоматически переноситься на случай $k \equiv 6 \pmod{12}$, в смысле доказательства $M(k)\le 5$. Ведь там тоже все крутится вокруг неуживчивости $n_0$ и $n_2$.
Денис, Евгений... посмотрите свежим взглядом. Это действительно так?

PS: Еще раз об обозначениях (крик души).
Я открыл для себя эту тематику, когда придумал задачу MM77 (т.е 16 лет назад).
Развитие последовало, когда я предложил эту тематику для исследовательской работы Василия Дзюбенко (в ту далекую пору еще школьника).
В процессе дальнейшего развития темы я опубликовал 3 статьи (2 совместно с Василием) и главу в книжке. Я неоднократно пытался привлечь внимание к данной тематике на здешнем форуме (последний раз, во многом благодаря Антону, успешно) и разместил сотни постов про последовательные числа с равными количествами делителей.
И во ВСЕХ этих постах, статьях, книгах, проектах, таблицах, письмах... количество делителей последовательных чисел ВСЕГДА обозначалось буквой $k$, а буква $k$ ВСЕГДА обозначала количество делителей.

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

[mathematician123]

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

Денис, Евгений... посмотрите свежим взглядом. Это действительно так?

Ваше доказательство $M(90) \le 5$ можно обобщить. При фиксированных $p, q$ доказательство $M(6pq) \le 5$ сводится к конечному перебору. Далее будут использованы обозначения из теоремы 1 Вашей статьи. Аналогичными рассуждениями получается, что $2^3 \cdot 3^2 \cdot 5 \mid n_0$. Так как $\tau(n_0)=6pq$, то $n_0$ имеет не более 4 различных простых делителей. Случай, когда этих делителей 3, сводится к конечному перебору. Во втором случае $n_0 = r_1r_2^2r_3^{p-1}r_4^{q-1}$, где $\{r_1, r_2, r_3, r_4\} = \{2, 3, 5, r^*\}$, $r^* > 5$ - некоторое простое число. Тогда из $n_2 = 2x^2$ получаем, что $2(x+1)(x-1) = n_0$. Тогда $x +1$ или $x-1$ не делится на $r^*$. А это значит, что этот случай также сводится к конечному перебору.

В итоге, доказательство $M(6pq) \le 5$ свелось к рассмотрению некоторого количества экспоненциальных диофантовых уравнений. Аналогичная ситуация была и в доказательстве $M(2pq) \le 3$. Там эти уравнения удалось решить с помощью соображений делимости и теории уравнений Пелля. Думаю, что и здесь это получится.