YadryaraЕсли я где-то не уследил за языком и какие-то слова оказались слишком резкими — приношу свои извинения, это вышло не специально.
1. Замена
![$p \to pq$ $p \to pq$](https://dxdy-01.korotkov.co.uk/f/8/8/d/88d88a8aae235bb28bc4afeb2120c68982.png)
или обратная в одной позиции влияет на время счета других позиций только постольку, поскольку изменяет разрядность искомых чисел.
На время проверки да, на вероятность/частоту что такая проверка вообще будет производиться - нет, не только этим.
3. То, что число проверяется в два (и более) проходов (условно: быстрый тест для фильтрации и медленная окончательная проверка) - это влияет на решение о замене, но это учитывается во временах, которые используются в критерии - должны браться средние времена проверок.
4. Так же, через средние времена, должны учитываться и возможные выбросы времени проверки (конкретной позиции).
Тут получается усреднение не только по времени проверки конкретного места, а и по вероятности вообще дохода проверки до него. И последняя зависит от множества других мест, не только от этого конкретного.
Давайте на примере: возьмём L паттерн
![$pq,pq,pq,p,p,p,pq,p,p,pq,pq$ $pq,pq,pq,p,p,p,pq,p,p,pq,pq$](https://dxdy-01.korotkov.co.uk/f/0/3/f/03f67e9878c0fae8a541488c4679160182.png)
и рассмотрим когда будет проверяться место
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
, сначала с порогом простых
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
, для этого должны выполниться условия:
1. Все
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
должны быть простыми.
2. На месте
![$n+2$ $n+2$](https://dxdy-01.korotkov.co.uk/f/0/1/4/014ae02bf2b677c4c225a7dfd00b842082.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
3. На месте
![$n+1$ $n+1$](https://dxdy-04.korotkov.co.uk/f/3/f/1/3f18d8f60c110e865571bba5ba67dcc682.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
Пока ещё вроде просто. Но теперь рассмотрим условия что это самое место
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
будет проверяться дольше, повторно, уже с порогом по простым
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
:
1. Все
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
должны быть простыми.
2. На месте
![$n+2$ $n+2$](https://dxdy-01.korotkov.co.uk/f/0/1/4/014ae02bf2b677c4c225a7dfd00b842082.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
.
3. На месте
![$n+1$ $n+1$](https://dxdy-04.korotkov.co.uk/f/3/f/1/3f18d8f60c110e865571bba5ba67dcc682.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
.
4. На месте
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
5. На искомом месте
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
должно быть составное без делителей меньше
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
Заметьте, добавилось условие на место
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
, а пороги в условиях для разных мест разные.
Посмотрим условия что проверка места
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
займёт секунды (до 5 максимум):
1. Все
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
должны быть простыми.
2. На месте
![$n+2$ $n+2$](https://dxdy-01.korotkov.co.uk/f/0/1/4/014ae02bf2b677c4c225a7dfd00b842082.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или
неразложимое за 5с составное.
3. На месте
![$n+1$ $n+1$](https://dxdy-04.korotkov.co.uk/f/3/f/1/3f18d8f60c110e865571bba5ba67dcc682.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или
неразложимое за 5с составное.
4. На месте
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
должно быть или сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
.
5. На искомом месте
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
должно быть составное без делителей меньше
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
.
Причём чётко формализовать понятие "неразложимое за 5с составное" я не смогу, не знаю как
factor() ищет простые в разложении когда не указываешь порог, там точно не последовательный перебор, очень часто находит "средние" простые (десяток и более цифр) очень быстро. Плюс даже если и не разложилось, но нашёлся хоть один делитель, не важно какого размера (но понятно больше
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
проверенных ранее), то такое место уже не будет "неразложимым за 5с составным" и условие окажется невыполненным так как станет точно известно что там гарантированно не
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
. Про возможность быть простым не в первой степени не упоминаю, это слишком редко случается, но всё же случается и в условия должно бы входить (в программе учитывается).
Как Вы собрались из этой кучи вытащить лишь среднее время проверки места
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
я не понимаю. Попытаться усреднить по реальной статистики конечно можно, но результат этой попытки будет сильно зависеть не только от паттерна и самого места
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
, но и от множества других условий (мест
![$p, n+1, n+2, n+6$ $p, n+1, n+2, n+6$](https://dxdy-04.korotkov.co.uk/f/b/c/a/bcaa5f58f10a5234fc780c7d5b2486a482.png)
и соответственно конкретной величины
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
). У меня в логах например место
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
проверялось скорее всего вообще лишь однажды, в найденной 9-ке, больше не проверялось ни разу из 1100 цепочек. И потому непонятно зачем вообще учитывать время проверки места
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
если оно практически никак не влияет на общее время работы (5с против двух суток). Да, на другие места условия чуть проще (кстати не на все), но всё равно все они зависят как минимум от всех мест
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
и от
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
(для L паттернов, для R будет
![$n+4$ $n+4$](https://dxdy-01.korotkov.co.uk/f/0/b/4/0b4d5127685208697dd9a6b7c7b2393882.png)
).
Возможно возразите что на
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
можно и плюнуть, ладно, распишу условия на время проверки места
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
, которое проверяется хоть как-то почти всегда (только для L паттернов, для R всё будет зеркально):
1. Если не все
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
простые, то дальше не проверять.
2. Проверить места
![$n+2,n+6$ $n+2,n+6$](https://dxdy-02.korotkov.co.uk/f/1/a/f/1af4df1ea255af3114ee570b2d57c4fa82.png)
с порогом
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
3. Если на
![$n+2$ $n+2$](https://dxdy-01.korotkov.co.uk/f/0/1/4/014ae02bf2b677c4c225a7dfd00b842082.png)
сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
, то проверить
![$n+1$ $n+1$](https://dxdy-04.korotkov.co.uk/f/3/f/1/3f18d8f60c110e865571bba5ba67dcc682.png)
с порогом
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
4. Если на
![$n+1$ $n+1$](https://dxdy-04.korotkov.co.uk/f/3/f/1/3f18d8f60c110e865571bba5ba67dcc682.png)
сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
, то проверить
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
с порогом
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
5. Если на
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
, то проверить
![$n+9$ $n+9$](https://dxdy-01.korotkov.co.uk/f/0/9/e/09e9d37f36d4b8e99165e8436a514e7882.png)
с порогом
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
6. Если на
![$n+9$ $n+9$](https://dxdy-01.korotkov.co.uk/f/0/9/e/09e9d37f36d4b8e99165e8436a514e7882.png)
сразу
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
или составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
, то проверить
![$n+10$ $n+10$](https://dxdy-03.korotkov.co.uk/f/e/0/5/e05f7d24f062c910301a4ef4122d00c082.png)
с порогом
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
.
7. Если на местах
![$n+2,n+9$ $n+2,n+9$](https://dxdy-02.korotkov.co.uk/f/d/6/a/d6ab76d1fb813ff9b329f35da4e131e682.png)
или на местах
![$n+1,n+2$ $n+1,n+2$](https://dxdy-01.korotkov.co.uk/f/8/d/a/8da447437c7f562f19c8ffabbb1b13d882.png)
или на местах
![$n+9,n+10$ $n+9,n+10$](https://dxdy-01.korotkov.co.uk/f/0/e/6/0e6ca0838357afa359339418a94754a782.png)
или на искомом месте
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
оказалось не
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
и не составное без делителей менее
![$2^{15}$ $2^{15}$](https://dxdy-01.korotkov.co.uk/f/8/d/3/8d3203d46499cc7ef903faf73bea630582.png)
, то дальше ничего не проверять.
8. Повторить пункты 2-7 с порогом
![$2^{25}$ $2^{25}$](https://dxdy-04.korotkov.co.uk/f/b/8/6/b863d2fb9715d78a43675cd9dc446b0e82.png)
, при этом места с 60-ю делителями пропускать и заново не проверять.
9. Повторить пункты 2-7 с порогом в 5с (со всеми оговорками выше про "неразложимость за 5с"), при этом места с 60-ю делителями пропускать и заново не проверять.
Как легко заметить тут условия существенно сложнее/запутаннее (точнее они простые, сложно их формально записать словами). И они
другие чем для
![$n+0$ $n+0$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d4e54980a19452f12bbf9d548579be82.png)
и зависят от других позиций в цепочке. Фактически время проверки места
![$n+6$ $n+6$](https://dxdy-04.korotkov.co.uk/f/7/e/f/7efdbf58021f7ff5b0bbe23d72f9e63e82.png)
зависит от факторизации всех остальных мест
![$pq$ $pq$](https://dxdy-01.korotkov.co.uk/f/4/5/4/45448f736dff1ed4d20005287b78bdb582.png)
в цепочке. Ну и как его усреднять независимо от остальных ...