Максимальные интервалы между взаимно простыми числами

[Dmitriy40]

vicvolf в сообщении #1539572 писал(а):

Наверно все-таки минимальный простой делитель равен 11.

Да, конечно минимальный, это оговорка. Спасибо, сейчас поправлю.

vicvolf в сообщении #1539572 писал(а):

Хочу еще обратить внимание, что данные вычеты ПСВ$p_n$# являются произведением только простых чисел, одно из которых $p_n$, а остальные от $p_n$ и больше, таких, что их произведение не превосходит $p_n$#.

Да. Только даже количество таких простых чисел уже почти экспоненциально по $p_n$ (собственно это все простые в диапазоне $\sqrt{p_n\#}-p_n^2=O(\sqrt{p_n\#})$), а уж количество вариантов их комбинаций ещё больше (ограничение $<p_n\#$ понижает степень количества комбинаций с факториала до чуть менее квадрата оставляя в результате почти $O(p_n\#)$).

Ну и чисто по программистки, намного проще взять и с постоянным шагом перебрать числа, чем перебирать все комбинации с ограничением на величину произведения. Регулярность первого подхода позволяет легче распараллелить вычисления, не только по ядрам (это можно и во втором подходе), а и используя векторные возможности каждого ядра. Ну и код существенно проще, ведь перебирать достаточно лишь комбинации $\pi(p_n)=n$ простых чисел, а не $\pi(\sqrt{p_n\#})-n \gg n$.
Для ручного счёта для малых $n$ "лёгкость" может быть и обратной, перебрать комбинации проще кучи делений с остатком. Но случаи малых $n$ неинтересны (разве что для отладки программ/алгоримов).

[vicvolf]

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

Ну и чисто по программистки, намного проще взять и с постоянным шагом перебрать числа, чем перебирать все комбинации с ограничением на величину произведения.

Проще не значит быстрее. Вы с постоянным шагом по вычетам запускаете программу вычислений на определенное количество операций. Общее количество вычислений определяется, как произведение количества запусков программы на количество операций в программе. Поэтому количество запусков программы имеет большое значение.

В нашем примере Вы запускаете программу с шагом 11. А я предлагаю запускать программу с изменяемым шагом:

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

Список:

? forstep(p=11^2,2310,11, if(factor(p)[1,1]==11, print1(p,", ")))
121, 143, 187, 209, 253, 319, 341, 407, 451, 473,
517, 583, 649, 671, 737, 781, 803, 869, 913, 979,
1067, 1111, 1133, 1177, 1199, 1243, 1331, 1397, 1441, 1507,
1529, 1573, 1639, 1661, 1727, 1793, 1837, 1859, 1903, 1969,
1991, 2057, 2101, 2123, 2167, 2189, 2299,

от 22 до 110. Есть разница?

Это при $p_n=11$. При больших $p_n$ разница в количестве вычислений значительно больше.

[Dmitriy40]

vicvolf в сообщении #1539616 писал(а):

При больших $p_n$ разница в количестве вычислений значительно больше.

Не столь уж значительно: как подсчитал выше выигрыш для $p_n\#$ не превышает $p_n-1$ раз. Что в самом наилучшем случае позволит за то же время посчитать лишь на один примориал дальше. Вот весь выигрыш, всего один примориал. Реальное измерение скорости подтверждает эту зависимость. Конечно и это очень неплохо, но посчитать даже $59\#$ не поможет.
Что тут спорить, берите считайте, кто против то.

[vicvolf]

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

Ну и чисто по программистки, намного проще взять и с постоянным шагом перебрать числа, чем перебирать все комбинации с ограничением на величину произведения.

Разве это сложный код?
[code]? forstep(p=11^2,2310,11, if(factor(p)[1,1]==11, print1(p,", ")))

[Dmitriy40]

vicvolf в сообщении #1539677 писал(а):

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

Ну и чисто по программистки, намного проще взять и с постоянным шагом перебрать числа, чем перебирать все комбинации с ограничением на величину произведения.

Разве это сложный код?
[code]? forstep(p=11^2,2310,11, if(factor(p)[1,1]==11, print1(p,", ")))

Нет, это не сложный (если забыть про сложность факторизации!), но покажите здесь перебор вариантов произведений простых? Здесь как раз проход по диапазону с постоянным шагом, о чём я и сказал что это проще. И здесь факторизация вызывается уже не 47 раз для 11#, а 210 (или 105 если шаг удвоить) раз, 47 раз вызывается лишь анализ интервала, который здесь заменён на print.
И для любого $p_n\#$ ускорение здесь не превысит величины $p_n$ относительно проверки всех нечётных, потому что очевидно что факторизация проводится с шагом $2p_n$, а нечётные идут с шагом $2$, их отношение и даёт ускорение максимум в $p_n$ раз (реально ниже так как при проверке интервала будет факторизироваться не одно число, а и соседние с ним).

[vicvolf]

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

Нет, это не сложный (если забыть про сложность факторизации!), но покажите здесь перебор вариантов произведений простых? Здесь как раз проход по диапазону с постоянным шагом, о чём я и сказал что это проще. И здесь факторизация вызывается уже не 47 раз для 11#, а 210 (или 105 если шаг удвоить) раз, 47 раз вызывается лишь анализ интервала, который здесь заменён на print.

Все просто. Вместо команды print может стоять вызов программы вычислений.

[Dmitriy40]

vicvolf

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

но покажите здесь перебор вариантов произведений простых?

А банальностями отвечать не нужно, судя по Вашим ответам я их понимаю гораздо лучше.

[vicvolf]

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

судя по Вашим ответам я их понимаю гораздо лучше.

Я занимался программированием больше 30 лет. Надоело Правда занимался не вычислениями, а информационными системами. Сейчас на пенсии могу позволить себе заняться чистой математикой.

[Dmitriy40]

vicvolf в сообщении #1539727 писал(а):

Я занимался программированием больше 30 лет. Надоело Правда занимался не вычислениями, а информационными системами.

Ну положим стаж программирования у нас сравнимый и мне не надоело, так что не аргумент. И я занимался как раз в том числе вычислениями и их оптимизацией, так что тем более не аргумент. И знаю много примеров когда утверждения

vicvolf в сообщении #1539616 писал(а):

Проще не значит быстрее. Вы с постоянным шагом по вычетам запускаете программу вычислений на определенное количество операций. Общее количество вычислений определяется, как произведение количества запусков программы на количество операций в программе. Поэтому количество запусков программы имеет большое значение.

верны лишь для достаточно больших $n$, а при небольших они неверны — просто из-за сложности кода и соответственно большой константе внутри $t=O(f(n))$. И граница где уже верны а где ещё нет сильно зависит от кода и от аппаратуры. Иногда получается что они верны лишь для нереально больших $n$, а для всех практически применимых нет, неверны, и более эффективный на бесконечности алгоритм на практике оказывается неэффективным, проигрывая более простым даже с большим количеством выполнения циклов.

Но дело не в стаже и не в сфере деятельности. Я сказал "проход с постоянным шагом наиболее прост", Вы в ответ привели мой же код и спросили в чём его сложность. Ни в чём разумеется. Сложность в другом коде, с перебором произведений простых, о котором Вы говорите. Указание на его отсутствие в ответе Вы "не заметили" и ответили банальностью (фактически лишь перефразировав уже и так мною сказанное) совершенно на другое. И притом игнорируете мою оценку максимально возможного ускорения, выведенную кажется тремя разными способами и даже подтверждённую прямым экспериментом. Вот как это называется? Ну так чтоб без оскорблений и ярлыков? Вырыванием фактов из контекста? Игнорированием "неудобных" фактов? Можете не отвечать.

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

[vicvolf]

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

И притом игнорируете мою оценку максимально возможного ускорения, выведенную кажется тремя разными способами и даже подтверждённую прямым экспериментом.

Я с нею согласен, поэтому не пишу, так как нет замечаний.

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

Сложность в другом коде, с перебором произведений простых, о котором Вы говорите.

Я под сложностью понимаю сложность написания кода. В этом коде [code]? forstep(p=11^2,2310,11, if(factor(p)[1,1]==11, print1(p,", "))) перебор произведения простых реализован в одной операции factor(p)[1,1]==11, т.е. нахождении чисел, имеющих в разложении на простые значение 11. Сложность здесь минимальна. Другое дело, что сама такая операция требует времени $t=f(n)$, как Вы правильно заметили.

[Dmitriy40]

vicvolf в сообщении #1539742 писал(а):

перебор произведения простых реализован в одной операции factor(p)[1,1]==11, т.е. нахождении чисел, имеющих в разложении на простые значение 11.

Во-первых в factor()==x реализован вовсе не перебор произведений простых.
Во-вторых, factor() выполняется не 47 раз как должно быть для перебора произведений простых с ограничением, а 105 раз (да, с шагом $2p_n$).
В-третьих, скорость работы factor() уменьшается с ростом величины чисел. В отличие от возможной замены её на мой код проверяющий делимость на простые до $p_n$.
В-четвёртых, для больших чисел factor() применяет продвинутые методы поиска делителей, не просто тупо их перебор. Что резко замедляет поиск минимального простого делителя для больших чисел.
В-пятых, factor() всегда доводит разложение до конца, чего нам не нужно, нам достаточно проверить лишь малые простые по $p_n$. Да, её можно ограничить этим диапазоном, но нельзя заставить искать лишь наименьший простой делитель, а не все по $p_n$, что совершенно лишнее.
В-шестых, PARI/GP сильно медленный язык, разве что wrest придёт и скомпилит программу в exe файл, но вроде и тогда скорость медленнее реализации сразу на C/C++.
В-седьмых, я умею проверять делимость серии чисел любого размера одновременно на 32 разных небольших простых, factor же такого явно не умеет. Потому мой код будет быстрее даже скомпилированного в exe кода на PARI/GP.
В-восьмых, проверять делимость можно и без операций деления, без которых в factor() не обойтись и которые страшно медленные (в 30-100 раз медленнее всех прочих, кроме умножения, для которого деление медленнее всего в 8-20 раз).
В-девятых, на других языках программирования может и не оказаться функции разложения на множители и придётся её реализовать самому, что усложняет код.

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

vicvolf в сообщении #1539742 писал(а):

Я под сложностью понимаю сложность написания кода.

Сложность написания мало кого волнует и обычно все в таких случаях борются за скорость выполнения кода, а не его написания. Во всяком случае для кода, который будет работать намного дольше его написания. Для интервалов в примориале работа кода превышает его написание уже для 23#...41# (на PARI/GP поменьше, на C/C++/asm побольше).
И в данном случае сложность написания и сложность самого кода вполне коррелируют: если при проверке всех нечётных достаточно просто помнить левую границу и всё, то при проверке с шагом $2p_n$ надо ещё искать обе границы (влево и вправо), плюс корректно обрабатывать случаи перекрытия интервалов, когда объединяются три и более интервала. Это всё гарантированно сложнее писать. А перебор вариантов произведений простых ещё сложнее простого прохода диапазона с постоянным шагом.
Итого алгоритм подразумевает двойное усложнение кода, причём именно написания кода (особенно когда нет такой удобной и медленной factor()).
Я конечно не буду утверждать что написание кода усложнится невероятно, но точно сложнее, от полутора раз, до нескольких раз, смотря сколько всяких тонких моментов проверять в программе, а не глазками после. И на мой взгляд усложнение написания не стоит получаемого выигрыша.

[wrest]

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

В-шестых, PARI/GP сильно медленный язык, разве что wrest придёт и скомпилит программу в exe файл, но вроде и тогда скорость медленнее реализации сразу на C/C++.

Убыстряет на 20-30%, обычно не больше (не в разы), так что эта овчинка, кмк, выделки особо не стоит.

PARI/GP не для скоростных узкоспецифичных вычислений. Да и GMP напрямую (которая и используется в PARI/GP), кмк, тоже. Но это не точно.

Единственно, если вы, скажем, не умеете параллелить, а PARI/GP собрана под многопоточность, и использовать parfor, то дополнительно будет выигрыш некоторый у PARI/GP по сравнению с ней же однопоточной, но все равно конечно недостаточный. Там на многопоточность как я понял неслабые оверхеды, то есть время просто на количество потоков не поделить.

vicvolf в сообщении #1539742 писал(а):

Я под сложностью понимаю сложность написания кода. В этом коде

? forstep(p=11^2,2310,11, if(factor(p)[1,1]==11, print1(p,", ")))

перебор произведения простых реализован в одной операции factor(p)[1,1]==11, т.е. нахождении чисел, имеющих в разложении на простые значение 11. Сложность здесь минимальна.

Я там не вчитывался о чем у вас эта тема, но если вы хотите определить, является ли 11 наименьшим простым делителем, я б делал не так, а поделил бы сперва на 2,3,7 (с немедленным уходом из цикла если делится).
Т.е. заменой
if(factor(p)[1,1]==11
на
if(p%2==0, next(), if(p%3==0,next(),if(p%5==0,next(),if(p%7==0, next(), if(p%11==0,print1(p,",
"))))))
скобки не считал
Во всяком случае, если перебрать примерно 10 миллионов чисел (без печати подошедших канеш, только с подсчетом) то получается так

? cnt=0; forstep(p=11^2,10^8,11, if(factor(p)[1,1]==11, cnt++)); print(cnt)
2077920
? ##
  ***   last result computed in 9,460 ms.

? cnt=0;forstep(p=11^2,10^8,11, if(p%2==0, next(), if(p%3==0,next(),if(p%5==0,next(),if(p%7==0, next(), if(p%11==0,cnt++))))));print(cnt)
2077920
? ##
  ***   last result computed in 2,308 ms.
?

Т.е. примерно в 4 раза быстрее.
Кстати,просто протийсь циклом и ничего не делать -- около секунды тут.

? cnt=0; forstep(p=11^2,10^8,11, cnt++); print(cnt)
9090899
? ##
  ***   last result computed in 928 ms.

То есть, вычитая эту секунду на оверхеды, получаем "чистое" сокращение по времени в 8 раз, примерно.

[Dmitriy40]

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

Убыстряет на 20-30%, обычно не больше (не в разы), так что эта овчинка, кмк, выделки особо не стоит.

Спасибо, тогда это вообще ни о чём — ровно на этой же задаче я получал скорость более чем в сотню раз выше, 1.47с вместо 226с. Правда там asm+AVX2.

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

Единственно, если вы, скажем, не умеете параллелить, а PARI/GP собрана под многопоточность, и использовать parfor, то дополнительно будет выигрыш некоторый у PARI/GP по сравнению с ней же однопоточной, но все равно конечно недостаточный. Там на многопоточность как я понял неслабые оверхеды, то есть время просто на количество потоков не поделить.

Я где-то не так давно это проверял, получилось вместо 4х всего лишь 3х, при 100% загрузке всех 4-х ядер. Если запустить 4 отдельных потока, то скорость как и положено 4х.

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

Я там не вчитывался о чем у вас эта тема, но если вы хотите определить, является ли 11 наименьшим простым делителем, я б делал не так, а поделил бы сперва на 2,3,7 (с немедленным уходом из цикла если делится).

Я именно так и делал, когда нужны были большие простые делители. И да, выигрыш был явный. А вот для малых простых делителей, когда они гарантированно не больше пары-тройки десятков (если больше то считаем число неподходящим), этот подход выигрыша почти не даёт, как и замена factor(x,p+1) на gcd(x,p#), скорости примерно одинаковы:

? forstep(x=23^2,10^9,46, if(factor(x)[1,1]==23, cnt++););
time = 26,785 ms.
? forstep(x=23^2,10^9,46, if(x%3>0 && x%5>0 && x%7>0 && x%11>0 && factor(x)[1,1]==23, cnt++););
time = 19,923 ms.
? forstep(x=23^2,10^9,46, if(factor(x,24)[1,1]==23, cnt++););
time = 11,451 ms.
? forstep(x=23^2,10^9,46, if(x%3>0 && x%5>0 && x%7>0 && x%11>0 && factor(x,24)[1,1]==23, cnt++););
time = 11,654 ms.
? pp=vecprod(primes([1,23]));
? forstep(x=23^2,10^9,46, if(gcd(x,pp)==23, cnt++););
time = 9,563 ms.

И это ещё числа маленькие, а вот если взять скажем $10^{19}$, то разница будет уже весьма заметна:

? forstep(x=23^14,23^14+10^9,46, if(factor(x)[1,1]==23, cnt++););
time = 6943,600 ms.
? forstep(x=23^14,23^14+10^9,46, if(x%3>0 && x%5>0 && x%7>0 && x%11>0 && factor(x)[1,1]==23, cnt++););
time = 3455,600 ms.
? forstep(x=23^14,23^14+10^9,46, if(factor(x,24)[1,1]==23, cnt++););
time = 29,625 ms.
? forstep(x=23^14,23^14+10^9,46, if(x%3>0 && x%5>0 && x%7>0 && x%11>0 && factor(x,24)[1,1]==23, cnt++););
time = 19,859 ms.
? pp=vecprod(primes([1,23]));
? forstep(x=23^14,23^14+10^9,46, if(gcd(x,pp)==23, cnt++););
time = 10,093 ms.

[wrest]

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

? forstep(x=23^2,10^9,46, if(x%3>0 && x%5>0 && x%7>0 && x%11>0 && factor(x)[1,1]==23, cnt++););

Тут не очень ясно насколько жадно в pari вычисляется условие и как оно вычислется вообще -- слева-направо или в случайном порядке и т.п., кстати. Вдруг там factor() вычисляется каждый раз? Ну я по крайней мере не в курсе. Поэтому писал явно.

-- 18.11.2021, 23:33 --

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

Спасибо, тогда это вообще ни о чём — ровно на этой же задаче я получал скорость более чем в сотню раз выше, 1.47с вместо 226с. Правда там asm+AVX2.

Ну так оно и понятно: произвольная точность pari и gmp (числа в каких-то обёртках -- там наверное что-то вроде строк?) против фиксированных типов (длин типов).

-- 18.11.2021, 23:42 --

Dmitriy40
Кстати. У вас что-то все-таки не то с компом, имхо.

(Оффтоп)

У вас
? forstep(x=23^2,10^9,46, if(factor(x)[1,1]==23, cnt++););
time = 26,785 ms.
У меня на андроид планшете со snapdragon 855:
? forstep(x=23^2,10^9,46, if(factor(x)[1,1]==23, cnt++););
? ##
*** last result computed in 18,131 ms.

[Dmitriy40]

wrest
Нет, простые типы устроены странно хитро: пока значение не превышает величину uint на машине ($2^{32}-1$ или $2^{64}-1$) число хранится как 3 uint (видимо тип объекта, размер в словах, значение), в сумме 12 байтов на x86 и 24 байтов на x64. При увеличении числа его размер в байтах растёт кратно размеру uint (4 или 8 байтов). Это легко проверить командой sizebyte(x).

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

Тут не очень ясно насколько жадно в pari вычисляется условие и как оно вычислется вообще -- слева-направо или в случайном порядке и т.п., кстати.

Нет, вполне ясно — жадно, как и обычно в С/С++ (цитата из User's Guide, стр.31):

Цитата:

Priority 3
&&: logical and.
||: logical (inclusive) or.
Any sequence of logical or and and operations is evaluated from left to right, and aborted as soon as the final truth value is known. Thus, for instance,
x == 0 || test(1/x)
will never produce an error since test(1/x) is not even evaluated when the first test is true (hence the final truth value is true). Similarly
type(p) == "t_INT" && isprime(p)
does not evaluate isprime(p) if p is not an integer.

Впрочем да, помнить это всё муторно, проще написать больше кода, тут я с Вами согласен, сам вечно расставляю кучи скобок чтобы не запоминать приоритеты операций.

-- 19.11.2021, 00:14 --

wrest
Ага, что-то не так — это Вы ещё не видели вот этого на gp64:

? forstep(x=23^2,10^9,46, if(factor(x)[1,1]==23, cnt++););
time = 45,959 ms.