Новый генератор простых чисел

[sceptic]

В Journal of Integer Sequences (2008, vol. 11, issue 2) опубликована статья Эрика Роуланда (Eric S. Rowland) "A Natural Prime-Generating Recurrence".
В ней Роуланд построил рекуррентную последовательность, состоящую лишь из 1 простых чисел. Вот она:
$a_1 = 7$ и для всех $n > 1, a_n = a_{n-1} + НОД(n,a_{n-1})$.
Далее, для $n > 1$ определим: $b_n = a_n - a_{n-1}$.
Роуланд доказывает, что последовательность $\left\{ b_n | n = 2,3,...\right\}$ состоит лишь из 1 и простых чисел.
Сама статья.

[Руст]

Вещь забавная. Только чтобы исполнять указания генератора нельзя не прибегая к другой программе $gcd(n,a_{n-1})$. Порождаются простые не подряд и много раз повторяются, особенности 1. К тому же не понятно какие простые порождаются, а какие нет?

[sceptic]

Полагаю, будет активно исследоваться.

[Руст]

sceptic писал(а):

Полагаю, будет активно исследоваться.

Да нет тут ничего интересного. По сути это есть последовательность образованная следующим образом. Берём нечётное число $b_1$ находим его минимальный простой делитель $p_1$. Делаем рекуренцию $b_{n+1}=b_n+p_n-1,p_{n+1}$ - минимальный простой делитель числа $b_{n+1}$. Чего тут изучать?

[hurtsy]

Руст

Цитата:

Да нет тут ничего интересного. ...

Мне нравится, как Вы четко перешли от оценки забавно, к окончательной. Так что тема завершена, или можно ждать новых генераторов.А нельзя ли здесь же обсудить результат американского математика Дэниела Голдстона и турецкого математика Сима Иилдирима о простых-близнецах, или узнать Ваше окончательное мнение? С уважением,

[Руст]

hurtsy писал(а):

А нельзя ли здесь же обсудить результат американского математика Дэниела Голдстона и турецкого математика Сима Иилдирима о простых-близнецах, или узнать Ваше окончательное мнение? С уважением,

Тут не все такие просвящённые как вы. Вы хотя бы дайте ссылки на эти работы. Тогда можно и обсуждать.

[sceptic]

Руст писал(а):

По сути это есть последовательность образованная следующим образом. Берём нечётное число $b_1$ находим его минимальный простой делитель $p_1$. Делаем рекуренцию $b_{n+1}=b_n+p_n-1,p_{n+1}$ - минимальный простой делитель числа $b_{n+1}$. Чего тут изучать?

Задачи нахождения НОД и нахождения простого делителя (пусть и наименьшего) - задачи с совершенно разными оценками сложности. Как Вы ухитрились трансформировать алгоритм, где наиболее трудоемкая операция - нахождение НОД, в алгоритм, где приходится искать делители числа? Расскажите поподробнее, пожалуйста.

Спрашивая о Дэниеле Голдстоне и Симе Иилдириме, hurtsy, по-видимому имеет ввиду их результат:

$$ \liminf_{n\to\infty}{p_{n+1}-p_n\over\log p_n}=0, $$

где $p_n$ означает $n$-е простое число.
Их работы по этой теме можно найти в arhiv.org.

[Руст]

sceptic писал(а):

Руст писал(а):

По сути это есть последовательность образованная следующим образом. Берём нечётное число $b_1$ находим его минимальный простой делитель $p_1$. Делаем рекуренцию $b_{n+1}=b_n+p_n-1,p_{n+1}$ - минимальный простой делитель числа $b_{n+1}$. Чего тут изучать?

Задачи нахождения НОД и нахождения простого делителя (пусть и наименьшего) - задачи с совершенно разными оценками сложности. Как Вы ухитрились трансформировать алгоритм, где наиболее трудоемкая операция - нахождение НОД, в алгоритм, где приходится искать делители числа? Расскажите поподробнее, пожалуйста.

По сути это изложено в самой статье.

[hurtsy]

sceptic писал(а):

Спрашивая о Дэниеле Голдстоне и Симе Иилдириме, hurtsy, по-видимому имеет ввиду их результат:

$$ \liminf_{n\to\infty}{p_{n+1}-p_n\over\log p_n}=0, $$

где $p_n$ означает $n$-е простое число.
Их работы по этой теме можно найти в arhiv.org.

Да. Я был уверен, что этот результат Вам известен. У меня вопрос, что в этом результате решающего для проблеммы бесконечности простых чисел близнецов? С уважением,

[Narn]

Этот результат не опровергает гипотезу о бесконечности близнецов. Конечно, он ее и не доказывает. Вот если бы доказали, что нижний предел строго больше 0, то гипотеза была бы опровергнута.

[hurtsy]

Narn писал(а):

Вот если бы доказали, что нижний предел строго больше 0, то гипотеза была бы опровергнута.

Согласен.А цитируемое утверждение гипотеза, или Вы видите путь для доказательства. С уважением,

[Narn]

Я гений! Я вижу путь для доказательства!

Пусть

$$ \liminf_{n\to\infty}{p_{n+1}-p_n\over\log p_n}=c>0, $$

, тогда, начиная с какого-то номера выполняется неравенство

${p_{n+1}-p_n\over\log p_n}>c/2$, или ${p_{n+1}-p_n}>c\log p_n /2 > c\log n /2$ то есть разность между двумя соседними простыми числами растет быстрее логарифма (и не может быть равной 1 для бесконечно многих $n$).

[MaximKat]

разность между двумя соседними простыми числами равна 1 только для одного $n$

[Narn]

MaximKat писал(а):

разность между двумя соседними простыми числами равна 1 только для одного $n$

,

Н-да. То есть "ой", или даже "тьфу, черт". Имелось в виду не 1, а одно из четных простых чисел (угадайте какое).

[Руст]

На самом деле они это

$$ \liminf_{n\to\infty}{p_{n+1}-p_n\over\log p_n}=0, $$

не доказали.
Но давно доказано, что

$$\limsup_{n\to\infty}\frac{p_{n+1}-p_n}{\log p_n}=\infty.$$