Как писать быстрые программы

[Dmitriy40]

Можно и без индексов, благо простых пока что мало (три последовательных натуральных числа):
3q 2p rt
rt 2p 3q
где все числа p,q,r,t простые.
Ну или так:
$a=3q, a+1=2p, a+2=rt$
$a=rt, a+1=2p, a+2=3q$

В принципе вместо rt может стоять r^3 (простое в кубе), но таковые проверяются гораздо легче (перебор до кубического корня вместо квадратного) отдельно и обычно можно не учитывать.

[waxtep]

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

Мировой рекорд — аж 20 последовательных натуральных чисел.

А меня честно говоря, вот это озадачило. Двадцать чего, ведь не последовательных полупростых же?

[Yadryara]

waxtep в сообщении #1702992 писал(а):

Двадцать чего, ведь не последовательных полупростых же?

Двадцать последовательных натуральных чисел ровно по 48 делителей каждое.

[Dmitriy40]

waxtep в сообщении #1702992 писал(а):

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

Мировой рекорд — аж 20 последовательных натуральных чисел.

А меня честно говоря, вот это озадачило. Двадцать чего, ведь не последовательных полупростых же?

Двадцать последовательных натуральных чисел (начиная с указанного), каждое из которых имеет ровно 48 делителей.

Последовательных полупростых не может быть длиннее 3-х так как иначе среди них встретится число 4p (p тут может быть и составным), которое точно не полупростое.

-- 23.09.2025, 18:11 --

waxtep
Посмотрите первое сообщение темы «Пентадекатлон мечты», особенно табличку и поясняющий текст перед ней.

-- 23.09.2025, 18:15 --

Yadryara
Опишите пожалуйста коротко смысл данной темы, какие именно быстрые программы Вы хотите писать (и на каком языке или языках), а то мы как-то резко ударились в PARI по совсем частному вопросу ... Он конечно интересный, но PARI и скорость не всегда совместимы.

[waxtep]

Yadryara, Dmitriy40, спасибо!

[Yadryara]

Да, пока можно разными. Но впс в этом плане ещё был получше кое-кого. Ибо, например Вы, порой обозначали не $p$ и $qr$, а $p$ и $pq$, хотя это не короче. Вот, начиная с этого поста, где сноску сделали:

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

Понятно что все $p$ и $q$ тут и далее разные.

Да, нам это было понятно и не сильно мешало. Но вот люди разные и ухитряются не понимать. А причина банальна: невнимательность при чтении.

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

число 4p (p тут может быть и составным)

Даже $4а$ или $4x$ и то лучше. А через $p$ обозначать именно одиночное простое.

Впрочем, спорить об обозначениях можно годами:

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

Да, между словами "обозначение" и "мучение" не такая уж большая разница. Трудно придумать во всех отношениях удобные обозначения.

[wrest]

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

То есть я специально отдельно оговорил, что числа различны и на индексах экономим, а Вы это спокойно проигнорили ?

С первого раза - да, проигнорировал. Потом-то я понял, что среднее обязательно четное и по крайней мере одно из крайних делится на три. Потому что это раньше уже написано было :)

[Yadryara]

Пытался найти матзапрет на кубы. Пока не нашёл.

Но если $a$ нечётное число, то среди огромного количества чисел вида $\frac{a^3 \pm 1}2$ не встречается ни одного простого. И не только кубов это касается.

Уточню: нечётный куб должен иметь остаток от деления на 12 не 3 и не 9.

Ещё вот это не понял:

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

Удиивтельно что LLM выдал достаточно хороший код, действительно внезапно ...

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

Ну а то что ИИ смог написать работающую прогу - не удивительно,

Почему в одном случае удивительно, а в другом — нет.

[Yadryara]

Да, матзапрет на кубы есть и совершенно тривиальный.

То есть если удвоить простое число, то оно никогда не окажется вплотную к нечётному кубу, если он не имеет остаток 3 от деления на 12.

У нас-то куб может иметь остаток только 1 или 11. То есть запрет этот с запасом.

Достаточно просто разложить $a^3 \pm 1$ в произведение двух чисел и посмотреть что подходит. Собственно, лишь один-единственный куб может быть — $27$.

-- 24.09.2025, 08:22 --

wrest в сообщении #1703003 писал(а):

Потом-то я понял, что среднее обязательно четное и по крайней мере одно из крайних делится на три.

Только не по крайней мере, а ровно одно из крайних делится на три.

Другое крайнее не делится на три и кубом простого не является.

[Yadryara]

Есть ещё идеи. Вот например такая замена двух проверок по numdiv на одну:

forprime(p=5,1e9/2, isprime((shift(p,1)+1)\3) && numdiv(2*p+(-1)^((2*p)%6/2))==4 && kpod++);

Времена и результаты у меня на компе:

Dmitr:    round(2*p/3)       <=10^9   741791        12,587 ms

wrest: (shift(p,1)+1)\3      <=10^9   741791        10,560 ms

Уadr:  (-1)^((2*p)%6/2)      <=10^9   741791         9,099 ms

[Yadryara]

Только сейчас заметил вопрос ко мне.

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

Опишите пожалуйста коротко смысл данной темы, какие именно быстрые программы Вы хотите писать (и на каком языке или языках)

Ну в практическом смысле, например, поиск 21-к вроде актуален, причём сразу в нескольких смыслах. Вот же только что писал:

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

Человечеству не известно ни одного кортежа, симметричной 21-ки из последовательных простых чисел.

Человечеству не известно ни одной 21-ки из последовательных чисел с одинаковым количеством делителей.

Так что логично было пока что рассмотреть цепочку попроще.

На любых доступных языках, лишь бы быстрее было.

-- 24.09.2025, 12:20 --

Ну вот ещё ускорить удалось, сделав цикл по тому простому которое с 3-кой:

forprime(p=5,1e9/3, isprime((3*p-2+p%4)\2) && numdiv(3*p-2*(2-p%4))==4 && kpod++);

<=10^9   741791         8,552 ms

[wrest]

Не даёт мне покоя гениальное

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

isprime(round(2*p/3))

Тут мы одним замахом проверяем что какой-то из двух соседей числа $2p$ (т.е. либо $2p-1$ либо $2p+1$) точно явяется полупростым и при этом делится на 3. Но не знаем какой. А дальше уже проверяем их обоих на полупростоту. Где-то тут можно ещё срезать угол.

-- 24.09.2025, 12:59 --

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

Ну вот ещё ускорить удалось, сделав цикл по тому простому которое с 3-кой:

Ну да, вроде что-то такое напрашивалось, что раз крайнее из тройки делится на 3, то проверять его соседей - ($3p+1$ и $3p-1$) на чётность и затем полупростоту, и если да, то проверять соседа соседа (соответсвенно $3p+2$ или $3p-2$) на полупростоту уже numdiv-ом.

[Yadryara]

wrest в сообщении #1703079 писал(а):

А дальше уже проверяем их обоих на полупростоту. Где-то тут можно ещё срезать угол.

Ещё срезать можно? Уже после того, как я срезал?

Вижу как ещё можно чуть упростить проверку в том варианте:

forprime(p=5,1e10/2, isprime((shift(p,1)+1)\3) && numdiv(2*p+(-1)^(p%3))==4 && kpod++);

Но вариант с циклом до трети пока всё равно быстрее чем с половинкой:

1/2:          <=10^10    5492374       1min, 32,241 ms
1/3:          <=10^10    5492374       1min, 28,645 ms

[wrest]

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

Ещё срезать можно? Уже после того, как я срезал?

Не, мой комментарий про срезать писался до вашего срезания. Я пока не въехал что вы сделали, но похоже что-то хорошее.

upd. Да, вот это прям хорошо: numdiv(2*p+(-1)^(p%3))==4
Мы уже знаем что какое-то из $2p-1$ или $2p+1$ делится на три и является полупростым. Ну конечно, если $2p \mod 3=1$, то известное полупростое $2p+1$ и проверить осталось только $2p-1$, а если $2p \mod 3 = 2$, то полупростое $2p-1$ и проверить надо $2p+1$. Гениально!

[Yadryara]

wrest в сообщении #1703090 писал(а):

Я пока не въехал что вы сделали,

Ну вот я же неслучайно ещё и самую правую колонку расписал:

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

Структура троек получается такой:

  1-e   2-e   3-e       qr mod 12
   qr    2p    3p               1
   3p    2p    qr              11

Причём надо помнить, что простые $p$ конечно различны, как и простые $q$ и $r$