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

[Yadryara]

О, сколько народу подключилось!

wrest, теперь вижу Ваше время. Понял, что надо Ваш код не из консоли запускать (как обычно делаю). Запустил прямо из Пари, а потом дал такую же команду. Количество совпало, а время засёк по часам — 80 секунд.

У grisа всего лишь 34 секунды.

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

forprime(p=3,1e8/2, numdiv(2*p-1)==4 && numdiv(2*p+1)==4 && kpod++; );
что даёт время 3.9с!

А вот и настоящая крутизна

[Dmitriy40]

mihaild в сообщении #1702969 писал(а):

А можно кратко - что считаем?

Цепочки из последовательных натуральных чисел, имеющих строго k=4 делителей. Чисто для тестов/иллюстрации, их миллионы за минуты находятся.

-- 23.09.2025, 15:34 --

wrest
Yadryara
Время улучшилось до 1.4с.

-- 23.09.2025, 15:36 --

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

время засёк по часам — 80 секунд

В PARI есть команда ## - показать время выполнения последней команды. В данном случае - работы функции.

[wrest]

Dmitriy40
Предлагаю вместо isprime(round(2*p/3)) писать isprime((shift(p,1)+1)\3)

-- 23.09.2025, 15:40 --

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

Время улучшилось до 1.4с.

:( слишком быстро. Надо увеличить диапазон в 10 раз

[Dmitriy40]

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

Dmitriy40
Предлагаю вместо isprime(round(2*p/3)) писать isprime((shift(p,1)+1)\3)

Согласен: до 1e9 ускоряет с 16.5с до 14.2с.

[mihaild]

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

Цепочки из последовательных натуральных чисел, имеющих строго k=4 делителей

В смысле $a$ такие, что каждое из $a$, $a+1$, $a+2$ имеет ровно $4$ делителя? (т.е. является либо произведением двух различных простых, либо четвертой степенью простого)

[Yadryara]

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

Разве тройка может иметь в себе число кратное 4?

В данной задаче не может.

Dmitriy40, тогда надо на миллиард переходить. Вы меня сами учили, что результирующее время желательно иметь не менее 20 секунд.

Для сверки:

Интервал    Первонач   Полупрост         2         3        Троек
<=10^2             3           3         3         3            3
<=10^3            93          67        39        27           13
<=10^4          1429         732       291       197           71
<=10^5         18257        7321      2170      1505          379
<=10^6        214694       69811     16783     11546         2377
<=10^7       2419224      658013    130805     89606        15197
<=10^8      26538772     6186940   1049769    717517       103474
<=10^9     286024010    58236914   8636829   5885913       741791
<=10^10   3044160588   549561294  72353829  49179067      5492374

[wrest]

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

Понял, что надо Ваш код не из консоли запускать (как обычно делаю). Запустил прямо из Пари, а потом дал такую же команду.

Я обычно даю код законченной функции, которая не портит глобальные переменные и не создаёт своих, возвращает что надо (ну или печатает). Потом её запускать, да. Можно скомпилить в gp2c и потом запускать.

[Dmitriy40]

mihaild в сообщении #1702974 писал(а):

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

Цепочки из последовательных натуральных чисел, имеющих строго k=4 делителей

В смысле $a$ такие, что каждое из $a$, $a+1$, $a+2$ имеет ровно $4$ делителя? (т.е. является либо произведением двух различных простых, либо четвертой степенью простого)

Да, только с поправкой что в кубе, не в четвёртой степени. Показатель степени k у простого даёт множитель k+1 в количество делителей.

-- 23.09.2025, 16:06 --

Что интересно, добавление первым условия bittest(0x6816,p%15) программу уже замедляет, хотя казалось бы должно немного ускорять.
Как и эквивалентного (но ещё более медленного) условия setsearch([1,2,4,11,13,14],p%15).

[Yadryara]

mihaild, конечно, я же прямо на A039833 ссылку дал.

Хотя степень 3-я а не 4-я. Насколько помню, можно как-то быстро установить, что кубы в пролёте и остаются только бесквадратные полупростые или, как я их называю, куары.

wrest
Здорово! А я и не знал что ещё какой-то шифт есть...

Видимо, надо уже на 10, а то и на 100 ярдов переходить. А затем переделывать и на асм и на CUDA...

[wrest]

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

Здорово! А я и не знал что ещё какой-то шифт есть...

Ну по-хорошему умножение на два натурального числа $n$ и должно заменяться или шифтом или $n+n$
Деление целого на целое с последующим округлением до целого тоже не надо плавающей арифметикой делать если их много и важна скорость. Так что эти штуки вполне как бы очевидны :)
Шифт, к слову, есть даже в экселе

[Dmitriy40]

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

Насколько помню, можно как-то быстро установить, что кубы в пролёте и остаются только бесквадратные полупростые

issquarefree и forsquarefree.
Проверить же кубы простых до 1e9 легко - циклом forprime(p=2,1e9^(1/3), x=p^3; ...).

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

Деление целого на целое с последующим округлением до целого тоже не надо плавающей арифметикой делать

В PARI 2*p/3 вычисляется целочисленно (в рациональных числах). Вот если любое из трёх чисел сделать с точкой, то да, будет плавающая точка.

[wrest]

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

Согласен: до 1e9 ускоряет с 16.5с до 14.2с.

Не устаю удивляться прогрессу гаджетов. У меня в телефоне 2023 года выпуска, до 1е9 считается 10.4с, в планшете 2022 года выпуска -- 13.4с

-- 23.09.2025, 16:43 --

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

В PARI 2*p/3 вычисляется целочисленно (в рациональных числах).

А, точно!

[Yadryara]

Спасибо. Лет 100 Экселем не пользовался.

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

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

Причём надо помнить, что простые $p$ конечно различны, как и простые $q$ и $r$, но обычно это не указывается индексами, ибо длинные цепочки тогда трудно изобразить. Мировой рекорд — аж 20 последовательных натуральных чисел.

Кстати, в графе "Полупрост" я как раз считаю количество куаров.

[wrest]

Yadryara
Вы выражаетесь очень как бы это сказать... загадочно (cryptic).
В частности, я считываю "2p" как "два умножить на p" и сходу не понимаю как числа 2p и 3p могут идти одно за другим кроме случая p=1, но в этом случае я уже не понимаю как перед числами 2,3 может быть какое-то число qr кроме как если q=1, r=1.
Так что я далее игнорирую тут сутевую чссть, если мне сразу непонятно кто на ком стоял, как и в темах про кортежи, включая обсуждение как пристроить первую гипотезу Харди-Литтлвуда для их поиска.
Просто сообщаю, для вашего сведения так сказать.

[Yadryara]

wrest

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

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

В частности, я считываю "2p" как "два умножить на p" и сходу не понимаю как числа 2p и 3p могут идти одно за другим кроме случая p=1,

Вот, болдом и шрифтом выделяю:

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

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

То есть подразумевается более корректная запись: $2p_1$ и $3p_2$.