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

[Dmitriy40]

vicvolf
Проверил реальное ускорение.
Для $59\#$ миллиард чисел начиная с $61^2$ перебором подряд всех нечётных занял 226с, перебором лишь интервалов где $59$ реально является минимальным простым делителем заняло 20с.
Для $251\#$ миллиард чисел начиная с $257^2$ перебором подряд всех нечётных занял 217с, перебором лишь интервалов где $251$ реально является минимальным простым делителем заняло 5.7с.
Ускорение есть, в 11-38 раз, но смысла в нём мало: объём перебора увеличился почти на 80 порядков, а скорость выросла лишь вчетверо. Т.е. реализация Вашей идеи позволит посчитать лишь ещё один-два примориала, не более.

[vicvolf]

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

Для $59\#$ миллиард чисел начиная с $61^2$ перебором подряд всех нечётных занял 226с, перебором лишь интервалов где $59$ реально является минимальным простым делителем заняло 20с.

Большое спасибо! А нельзя сравнить на всем ПСВ праймориалов?

[Dmitriy40]

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

А нельзя сравнить на всем ПСВ праймориалов?

Можно, сравнивайте.
Мне же 7 миллионов лет счёта как-то немножко жалко.

[Yury_rsn]

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

Например. Задано число 23. Количество нечетных в интервале пусть будет 10.
Т.е., это будет - 25, 27, 29, 31, 33, 35, 37, 39, 41, 43.

Тогда программа должна вернуть такую строку:
5, 3, 1, 1, 3, 5, 1, 3, 1, 1.

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

[vicvolf]

Dmitriy40 Количество, отбрасываемых вычетов, делящихся на $p_n$ в $p_n$# обратно пропорциальна $p_n$, а длина праймориала $p_n$# прямо пропорциональна $p_n$, поэтому количество вычислений не должно существенно возрастать с ростом $p_n$. Проверьте, пожалуйста, на не больших ПСВ_$p_n$#, когда будет возможность.

[Dmitriy40]

Yury_rsn

? p=23; a=20332472-1;\\Не знаю почему у них числа чётные, интервал вправо будет определён автоматически по числу p
? print1(factor(a)[1,1]); b=a+2; while((f=factor(b)[1,1])<=p, print1(", ",f); b+=2); print(", ",f);
73, 3, 5, 11, 3, 13, 23, 3, 7, 19, 3, 17, 5, 3, 11, 7, 3, 5, 13, 3, 20332511

\\Другой вариант, с началом и длиной интервала
? d=40; a=20332472-1; forstep(x=a,a+d,2, print1(factor(x)[1,1], ", "));
73, 3, 5, 11, 3, 13, 23, 3, 7, 19, 3, 17, 5, 3, 11, 7, 3, 5, 13, 3, 20332511,

\\Вариант предыдущего кода с заменой неразложенных чисел на прочерки
? d=40; a=20332472-1; forstep(x=a,a+d,2, print1(if((f=factor(x)[1,1])>=a, "--", f), ", "));
73, 3, 5, 11, 3, 13, 23, 3, 7, 19, 3, 17, 5, 3, 11, 7, 3, 5, 13, 3, --, 

К сожалению factor для простых (т.е. если не найдёт делителей) возвращает сам аргумент, потому и 20332511 вместо 1, но думаю это не сильно принципиально, да и показал как заменить на что угодно.
Для очень больших чисел (типа 29# и более) рекомендую заменить factor(x) на factor(x,10^6), чтобы делители искались побыстрее, лишь до миллиона.

Yury_rsn
Имейте в виду на всякий случай что числа начала интервалов в https://oeis.org/A048670/a048670_5.txt вовсе не все являются минимально возможными, они таковы лишь по 29#. Далее примерно половина из них даже больше p#, чего для минимального числа никак быть не может. И даже взяв их по модулю p# правильного минимального числа всё равно не получается (во всяком случае далеко не ля всех).
Т.е. начала интервалов правильные, но не минимальные.

-- 15.11.2021, 12:18 --

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

Количество, отбрасываемых вычетов, делящихся на $p_n$ в $p_n$# обратно пропорциальна $p_n$, а длина праймориала $p_n$# прямо пропорциональна $p_n$, поэтому количество вычислений не должно существенно возрастать с ростом $p_n$.

Чушь: при переходе от $p_n$ к $p_{n+1}$ шаг проверяемых вычетов увеличивается на $p_{n+1}-p_n$, а размер интервала растёт в $p_{n+1}$ раз. Надеюсь Вы понимаете отличие сложения от умножения?
В $p_n\#$ проверяется $\frac{p_n\#}{p_n}=p_{n-1}\#$ вычетов (с точностью до небольшого коэффициента), т.е. количество проверяемых вычетов растёт практически пропорционально $p_n\#$ несмотря на увеличение расстояния между проверяемыми вычетами.
Почему Вы прежде чем спорить или что-то утверждать не проверите сами (хоть руками/калькулятором) хотя бы малые числа?! Ведь будет же видно уже на 5#, на 7#, на 11#, на 13#.

Кстати 13# последний примориал, у которого первый максимальный интервал ограничен простыми числами с обеих сторон. У всех дальше лишь не более чем с одной стороны.

[vicvolf]

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

Почему Вы прежде чем спорить или что-то утверждать не проверите сами (хоть руками/калькулятором) хотя бы малые числа?! Ведь будет же видно уже на 5#, на 7#, на 11#, на 13#.

Проверил вручную. У 5# всего 8 вычетов, 7 интервалов, по моему алгоритму проверяется 1 интервал. У 7# всего 48 вычетов, 47 интервалов, по моему алгоритму проверяется 7 интервалов. У 11# всего 480 вычетов, 479 интервалов, по моему алгоритму проверяется 40 интервалов. Отношение 47/7, 479/40 увеличивается.

[Dmitriy40]

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

У 11# всего 480 вычетов, 479 интервалов, по моему алгоритму проверяется 40 интервалов.

Тут скорее всего ошиблись, должно быть 47 интервалов. Ровно столько сколько было всего интервалов на предыдущем шаге. И да, я проверил программой, 47.

Отношение растёт. И что с того? Вот для 11# оно почти 10, для 13# почти 12, для 17# оно почти 16, для 19# почти 18, для 23# почти 22, для 29# почти 28, т.е. скорее всего стремится к $p_n-1$. Но ведь общее количество проверяемых интервалов всё равно растёт, и очень быстро, чуть медленнее чем примориал, но не сильно медленнее. Фактически используя алгоритм можно за то же время проверить лишь на один примориал больше. Да, это тоже неплохо, но ... не вижу особой разницы, на 41# надоедает ждать или на 43#.
И положение не спасёт даже то что вторую половину примориала можно и не проверять, т.е. интервалов вдвое меньше.

Кстати если не уменьшать количество интервалов на 1, то отношение станет всегда в точности равно $p_n-1$.

Данные моей программы (подсчёт проверяемых интервалов в ней честный, по factor(x), оптимизировано лишь остальное):

? p1=2; pp=6; forprime(p=5,29, pp*=p; p1*=p-1; n=0; forstep(x=p^2,pp,2*p, if(factor(x,p+1)[1,1]==p, n++)); print("p=",p,", p#=",pp,", k=",p1-1,"/",n,"=",(p1-1)/n*1.0));
p=5, p#=30, k=7/1=7.000000000000000000000000000
p=7, p#=210, k=47/7=6.714285714285714285714285714
p=11, p#=2310, k=479/47=10.19148936170212765957446809
p=13, p#=30030, k=5759/479=12.02296450939457202505219207
p=17, p#=510510, k=92159/5759=16.00260461885744052786942178
p=19, p#=9699690, k=1658879/92159=18.00018446380711596262980284
p=23, p#=223092870, k=36495359/1658879=22.00001265915114966191024180
p=29, p#=6469693230, k=1021870079/36495359=28.00000073982009602919647948
time = 1min, 31,558 ms.

-- 16.11.2021, 00:50 --

Неужели правда не насторожил переход $1 \to 7 \to 40$ вместо $5 \to 7 \to 11$? Ведь явно же что второй это сложение с небольшим числом, а первый это умножение. А умножение растёт на порядки быстрее сложения.

[Yury_rsn]

Dmitriy40
Дмитрий, спасибо за код.
Экспериментирую.

[vicvolf]

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

Тут скорее всего ошиблись, должно быть 47 интервалов.

Сейчас посмотрел внимательно. Мои вычеты находил следующим образом: $11^2$,$11 \cdot 13$,...$11 \cdot 199$, $11^3$, $11^2 \cdot 13$, $11^2 \cdot 17$, $11^2 \cdot 19$, $11 \cdot 13^2$, $13^3$ - получилось 46. Что пропустил?

[Dmitriy40]

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

Что пропустил?

Список:

? 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,

Похоже у Вас они ещё и лишние (например $13^3$).

Либо я опять как-то не так понимаю Ваши термины, я искал числа, у которых минимальный простой делитель равен в данном случае 11, именно эти числа объединяют два соседних интервала в один и эти интервалы и надо проверять. Случаи объединения трёх и более интервалов не учитывал, для малых простых их не бывает.

[vicvolf]

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,

Все правильно! Один из простых сомножителей здесь 11, а остальные простые в произведении, которое не превосходит 2310, не менее 11.

[Dmitriy40]

vicvolf
Т.е. Вы разобрались где 47 интервалов? Или мы всё ещё о разном?

[vicvolf]

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

Вы разобрались где 47 интервалов?

Да.

[vicvolf]

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

я искал числа, у которых максимальный простой делитель равен в данном случае 11

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

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