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

[wrest]

Dmitriy40
Истинно вам говорю: да активируйте wsl (у вас же win10?) и установите например ubuntu (там только cli будет, но ведь только оно и надо) прям из майкрософт стора. Оно то и в жизни иногда пригождается, я вот например тут недавно wifi домашний траблшутил -- iperf гонял с ноута на планшет/телефон или спидтест который есть для линуксовой командной строки.
"Вендовая" pari/gp всё одно обернута в mingw... А тут будет хоть и виртуализация, но без лишнего стороннего слоя. И x64 и многопоточность будет, все дела короче...

[vicvolf]

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

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

Это другое дело. В этом случае приобретает значение время работы программы определения длин интервалов, в найденных таким образом вычетах ПСВ.

[Dmitriy40]

А на больших числах ещё забавнее:

? forstep(p=43^11,43^11+10^9,86, if(factor(p,44)[1,1]==43, cnt++););
time = 15,960 ms.
? forstep(p=43^11,43^11+10^9,86, if(p%3>0 && p%5>0 && p%7>0 && p%11>0 && p%13>0 && p%17>0 && p%19>0 && p%23>0 && p%29>0 && p%31>0 && p%37>0 && p%41>0, cnt++););
time = 7,769 ms.
? forstep(p=43^11,43^11+10^9,86, if(1, cnt++););
time = 7,630 ms.

Типа длинный if аж в сто раз быстрее простой factor!

Кстати для больших примориалов даже на малых числах уже и не так уж быстрее:

? cnt=0; forstep(p=59^2,10^9,2, if(factor(p)[1,1]==59, cnt++););
time = 15min, 38,611 ms.
? cnt=0; forstep(p=59^2,10^9,2, if(factor(p,60)[1,1]==59, cnt++););
time = 3min, 11,851 ms.
? cnt=0; forstep(p=59^2,10^9,2, if(p%3>0 && p%5>0 && p%7>0 && p%11>0 && p%13>0 && p%17>0 && p%19>0 && p%23>0 && p%29>0 && p%31>0 && p%37>0 && p%41>0 && p%43>0 && p%47>0 && p%53>0, cnt++););
time = 5min, 26,449 ms.
? cnt=0; forstep(p=59^2,10^9,59, if(factor(p)[1,1]==59, cnt++););
time = 15,414 ms.
? cnt=0; forstep(p=59^2,10^9,59, if(factor(p,60)[1,1]==59, cnt++););
time = 8,330 ms.
? cnt=0; forstep(p=59^2,10^9,59, if(p%3>0 && p%5>0 && p%7>0 && p%11>0 && p%13>0 && p%17>0 && p%19>0 && p%23>0 && p%29>0 && p%31>0 && p%37>0 && p%41>0 && p%43>0 && p%47>0 && p%53>0, cnt++););
time = 11,217 ms.
? cnt=0; forstep(p=59^2,10^9,59*2, if(factor(p)[1,1]==59, cnt++);); cnt
time = 9,126 ms.
%1 = 2306411
? cnt=0; forstep(p=59^2,10^9,59*2, if(factor(p,60)[1,1]==59, cnt++);); cnt
time = 4,806 ms.
? cnt=0; forstep(p=59^2,10^9,59*2, if(p%3>0 && p%5>0 && p%7>0 && p%11>0 && p%13>0 && p%17>0 && p%19>0 && p%23>0 && p%29>0 && p%31>0 && p%37>0 && p%41>0 && p%43>0 && p%47>0 && p%53>0, cnt++););
time = 5,600 ms.
\\Измерение оверхеда цикла
? cnt=0; forstep(p=59^2,10^9,59*2, cnt++);
time = 5,538 ms.
? cnt=0; forstep(p=59^2,10^9,59*2, if(1, cnt++);); cnt
time = 5,819 ms.
%2 = 8474547
? cnt=0; forstep(p=59^2,10^9,59*2, if(cnt<2306411, cnt++);); cnt
time = 2,076 ms.
%3 = 2306411

Вот они, погрешности методики измерений, кратное увеличение числа инкрементов пересиливает пустоту if-а.
wrest, как видите в последнем запуске правильное значение оверхеда почти втрое ниже.

[Yury_rsn]

Все данные уже есть в статье Зиллера, оказывается. https://arxiv.org/pdf/1611.03310.pdf
(К статье приложены файлы с результатами расчетов. Например, перестановки https://arxiv.org/src/1611.03310v2/anc/permutations.txt
Очень хороши видны "разветвления".)

Правда, они там представлены слегка в другом виде, что сначала сбило с толку.
Любой интервал они представляют в виде последовательности остатков по каждому простому числу из праймориала - по логике китайской теоремы об остатках (если я ничего не перепутал).
Описано в "Proposition 1.5."
По мелочам кое-что неясно, но это как-нибудь потом.

Ну и в свете последних обсуждений о скорости работы программ, интересно будет вот это глянуть:

Цитата:

3.2 Computation time
All algorithms except ILP were implemented and executed on a common PC with an i7 processor at boosted 3.9 GHz in a single thread application. For solving the respective integer linear programs according to the equations 2.2, however, we utilised SYMPHONY software [18, 14] which used all threads in parallel. The corresponding time needs were enlarged by an empirically estimated factor to make them comparable.

[Dmitriy40]

Yury_rsn в сообщении #1540014 писал(а):

Любой интервал они представляют в виде последовательности остатков по каждому простому числу из праймориала - по логике китайской теоремы об остатках (если я ничего не перепутал).

Да, это удобно, числа маленькие (вместо одного сверхбольшого), у вас ровно они же в столбце D таблицы.
Кстати в файле moduli.txt ровно минимальные простые делители нечётных чисел, чем я постоянно пользуюсь и Вам тоже несколько раз менял под это программу.

Yury_rsn в сообщении #1540014 писал(а):

Ну и в свете последних обсуждений о скорости работы программ, интересно будет вот это глянуть:

Ну, смысла мало: у нас тут скорость на много порядков хуже/меньше, у них ILP для 101# занял порядка пары дней, у меня (на асме! не PARI и даже не С) вычисление 37# заняло 11100с, соответственно 101# займёт порядка $10^{20\ldots22}$ лет.

-- 21.11.2021, 15:52 --

Кстати программка PARI/GP для восстановления нечётного числа по остаткам в v[] на простые от трёх и далее:

? v=[1,3,2,5,6]; t=Mod(1,2); for(i=1,#v, t=chinese(t, Mod(v[i], prime(i+1)))); t
%1 = Mod(17803, 30030)
? v=[1,3,2,5,6]; t=Mod(1,2); for(i=1,#v, t=chinese(t, Mod(v[i], prime(i+1)))); lift(t)
%2 = 17803
? forstep(a=17803,17803+22,2, print1(factor(a)[1,1],", "))
19, 3, 17807, 11, 3, 47, 5, 3, 103, 71, 3, 5,
\\Интервал получился неправильный, не знаю почему, правильный вот такой:
? v=[1,4,3,1,1]; t=Mod(1,2); for(i=1,#v, t=chinese(t, Mod(v[i], prime(i+1)))); t
%3 = Mod(9439, 30030)
? v=[1,4,3,1,1]; t=Mod(1,2); for(i=1,#v, t=chinese(t, Mod(v[i], prime(i+1)))); lift(t)
%4 = 9439
? forstep(a=9439,9439+22,2, print1(factor(a)[1,1],", "))
9439, 3, 7, 5, 3, 11, 13, 3, 5, 7, 3, 9461,

[Yury_rsn]

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

у нас тут скорость на много порядков хуже/меньше, у них ILP для 101# занял порядка пары дней, у меня (на асме! не PARI и даже не С) вычисление 37# заняло 11100с,

Расскажите, плиз, где у них преимущество?
Он же пишет, что почти всё было посчитано на обычном компьютере.
ILP - это что?

[Dmitriy40]

Yury_rsn в сообщении #1540076 писал(а):

Расскажите, плиз, где у них преимущество?

Разве не этому посвящена вся их статья?! Весь раздел 2, 15 страниц математики ... Я вообще-то их не изучал.

Yury_rsn в сообщении #1540076 писал(а):

ILP - это что?

Если не ошибаюсь то один из алгоритмов вычисления чего-то там, встречается на стр.11 сразу после формулы (2.1). Но я даже не смотрел что это такое.
Если не нравится ILP, возьмите DSA (алгоритм со стр.16), они примерно сравнимы. Про варианты GPA вообще молчу-молчу.
Если не ошибаюсь, то у меня (и тут в теме везде) использован вариант алгоритма BSA или близкий к нему.

[Yury_rsn]

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

Разве не этому посвящена вся их статья?! Весь раздел 2, 15 страниц математики ... Я вообще-то их не изучал.

А, ага.
А я подумал, что вы говорите о каких-то вариантах "железа". Типа, у них круче.

[Dmitriy40]

У них круче, но на такую малость, которая исчезает уже на следующем же примориале (частота чуть выше, ядер вдвое больше, да и всё в общем). Выигрыша на десятки порядков не даст никакое железо, максимум в тысячу-миллион раз, ну может миллиарды если распределённые вычисления использовать (они не использовали вроде бы).
Но даже по графику времени счёта у них прекрасно видно что дело не в железе — скорость роста другая, а для улучшения железа она должна быть той же. На улучшение железа можно списать (если бы не было других данных кроме этого графика) переход от BSA к BPA и RPA на графике — скорость роста практически та же, только сама скорость выше. Математически это выражается $O(bn^a)=O(n^a)$, для разного железа $a$ (надеюсь всем понятно что это фактически наклон графика) будет ровно той же, другой будет лишь константа $b$, которая съедается $O()$. А другая $a$ говорит об изменении алгоритма.

[Yury_rsn]

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

У них круче, но на такую малость, которая исчезает уже на следующем же примориале (частота чуть выше, ядер вдвое больше, да и всё в общем). Выигрыша на десятки порядков не даст никакое железо, максимум в тысячу-миллион раз, ну может миллиарды если распределённые вычисления использовать (они не использовали вроде бы).
Но даже по графику времени счёта у них прекрасно видно что дело не в железе — ...

Хорошо. А те примеры алгоритмов, которые они привели в статье - их можно использовать для аналогичных подсчётов?
Или это только наброски для демонстрации идеи?(концепции)

Для чего? Там посчитаны интервалы максимальной, Якобсталевской длины для каждого праймориала. А хочется получить расчеты и по интервалам меньшей длины.

[Dmitriy40]

Yury_rsn в сообщении #1540161 писал(а):

А те примеры алгоритмов, которые они привели в статье - их можно использовать для аналогичных подсчётов?

Наверняка можно: надо всего лишь внимательно в них разобраться, переписать на любом используемом языке и довести до стадии выполняемого кода. Они же справились, почему нельзя ещё кому-то ... Реализовать уже придуманный алгоритм всегда проще чем придумать новый (лучше известных).

[Yury_rsn]

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

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

Всего лишь

[Dmitriy40]

Да, Вы поняли правильно.

[vorvalm]

Пытался найти начальное число интервала d = 282, в котором я поменял
местами цепочки 97 и 89. Но последнее сравнение WolframAlpha решить
не может. Вот оно.
13060740112619398671967+2097862499496067927075453x mod 381099389413219=0

Есть ли возможность его решить ?

[Dmitriy40]

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

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

Могу и по минимальным простым делителям (для нечётных чисел, заодно и величину примориала выдаёт):

? v=[3, 7, 5, 3, 11, 13, 3, 5, 7, 3]; t=Mod(1,2); for(i=1,#v, t=chinese(t, Mod(v[i]-i*2, v[i]))); t
%1 = Mod(9439, 30030)
? forstep(a=9439,9439+22,2, print1(factor(a)[1,1],", "))
9439, 3, 7, 5, 3, 11, 13, 3, 5, 7, 3, 9461,

Yury_rsn
Вот кстати заметьте: если убрать тройки, то так легко восстановить не получится.

И сюда уже вполне можно подставлять числа из файла moduli.txt.