to
maxal
В том топике, в частности, я просил книгу "Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, 1987" - и Вы не нашли ее тогда. Прошло два с лишком года - книга появилась (если интересует - в гигапедии: из 3-х линков лучшее качество предлагают первые 2).
Добавлено спустя 1 час 6 минут 43 секунды:
to
p-h-o-e-n-i-x: знать предыдущие простые необязательно
p-h-o-e-n-i-x писал(а):
можно ли доказать, что упомянутое выше определение простых чисел, из которого вытекает необходимость знать все предыдущие простые для получения следующего, единственно и не существует ни какого другого определения, дающего ту же последовательность простых чисел
Собственно, машина Конвея предоставляет алгоритм получения из простого числа

следующего за ним простого

:
1. Берем

.
2. Умножаем

на числа

и определяете

— первое из них, для которого число

— целое.
3. Проверяем, не является ли это число степенью двойки:
если

, то

и есть искомое следующее простое

- в этом случае алглритм заканчивает работу;
если не является, то переобозначаем

и отправляемся на пункт 2.
Конвей гарантирует, что этот алгоритм обязательно остановится и выдаст искомое следующее простое число. Как видите, для вычисления следующего простого числа (за простым

) знать предыдущие простые (до

) необязательно.
Алгоритм, правда, страшно неэффективен. Но это не столь важно, не правда ли?
Любопыто, в выше упомянутой книге Конвей строит аналогичную машину, генерирующую по номеру

-ую цифру (десятичную) числа

после десятичной точки.