Батороев
Да, похоже я упустил что числа всего лишь взаимно простые и взял обычные простые.
![Sad :-(](./images/smilies/icon_sad.gif)
Беру свои слова обратно, sorry.
Ничего страшного, ведь тема и о тех, и о других!
Как я понял идею топик-стартера, то рассматривая зону от
![$n^2$ $n^2$](https://dxdy-01.korotkov.co.uk/f/0/2/1/021273d50c6ff03efebda428e9e42d7782.png)
до
![$(n+1)^2$ $(n+1)^2$](https://dxdy-01.korotkov.co.uk/f/c/d/4/cd48333c76e4ce29484fd1d9633ed51c82.png)
, он хочет доказать, что интервалы между взаимнопростыми в примориале
![$p_r\#$ $p_r\#$](https://dxdy-03.korotkov.co.uk/f/a/f/0/af06f55c0c99a1d270ec9464eeda56e782.png)
(где
![$p_r$ $p_r$](https://dxdy-01.korotkov.co.uk/f/0/e/7/0e753bef3d72f8d3a9e7812f141d732982.png)
- максимальное простое число, не превосходящее
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
) меньше числа
![$2n+1$ $2n+1$](https://dxdy-02.korotkov.co.uk/f/5/d/6/5d687fe5b944a0bd07cbd7de02ff983082.png)
... но в данном интервале указанные взаимнопростые являются простыми числами (т.к. первое взаимнопростое данному примориалу, но не простое число не входит в указанный интервал (
![${p_{r+1}}^2>(n+1)^2$ ${p_{r+1}}^2>(n+1)^2$](https://dxdy-03.korotkov.co.uk/f/e/e/c/eecccd6e774f296e91132d1bef47eb7582.png)
).
Может быть ошибаюсь, но, кажется, это наблюдение не всегда задает самые большие вычеркиваемые интервалы.
Единственная ошибка заключается в том, что Вы думаете, что это мое утверждение, а не просто пример... того, как два интервала могут сливаться. ))
Если использовать (как Вы в предпоследнем тосте) линейки, то нам потребутся "резиновые".
Берем большую числовую ось (например, максимальную для Вашего мат.пакета).
Разбиваем ее на примориалы
![$3\#$ $3\#$](https://dxdy-04.korotkov.co.uk/f/3/7/7/377e69bcce26e1c13612b70d4c8e322182.png)
. Отмечаем в каждом из них взаимнопростые с этим примориалом (
![$\varphi_{3\#}=2$ $\varphi_{3\#}=2$](https://dxdy-04.korotkov.co.uk/f/7/9/4/7944229b503b820741a97865d74507ee82.png)
числа:
![$1$ $1$](https://dxdy-01.korotkov.co.uk/f/0/3/4/034d0a6be0424bffe9a6e7ac9236c0f582.png)
-е и
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
-е).
В сторонке берем первый примориал
![$3\#$ $3\#$](https://dxdy-04.korotkov.co.uk/f/3/7/7/377e69bcce26e1c13612b70d4c8e322182.png)
и расстягиваем его в
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
раз. Числа, бывшие в примориале
![$3\#$ $3\#$](https://dxdy-04.korotkov.co.uk/f/3/7/7/377e69bcce26e1c13612b70d4c8e322182.png)
взаимнопростыми, также расстягиваются и "элегантно превращаются" в числа, кратные
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
(
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
числа:
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
и
![$25$ $25$](https://dxdy-04.korotkov.co.uk/f/7/a/c/7acc185115b9ffabc044e2079b245b8d82.png)
).
Оставшиеся числа являются взаимнопростыми примориалу
![$5\#$ $5\#$](https://dxdy-03.korotkov.co.uk/f/e/3/6/e3674d513b6c04dd59391f5db07b108682.png)
. Таких чисел
![$\varphi_{5\#}=8$ $\varphi_{5\#}=8$](https://dxdy-01.korotkov.co.uk/f/c/1/f/c1f85dc3e04a813e1676b75cdaa2e12682.png)
.
Покрываем числовую ось такими линеками с обозначенными кратными.
И т.д.
p.s. Как мне видится, такой алгоритм вполне программируем.