Генератор псевдослучайных чисел без повторов

Ni+1 = Ni*q - [Ni*q/P]*P

квадратные скобки здесь обозначают выделение целой части
P - простое число, задающее границу диапазона
q = P - 3^m  (выбирается близкое к P/2)

При P=101, m=3, q=74, получаем псевдослучайную последовательность чисел в диапазоне 1-100 без повторов.
Данная формула использовалась в программе "Морской бой" для программируемого калькулятора MK-54, опубликовано в журнале "Техника молодежи" 1986 №10
Отсутствие повторов позволяло полностью перебрать все клетки поля 10x10 псевдослучайным образом.

К сожалению, данная формула не является универсальной.
Нельзя выбрать произвольный диапазон, т.к. P должно быть простым, а q должно быть достаточно близким к P/2.
Отсутствие повторов не гарантировано, при соблюдении условий обычно получаем достаточно большое кольцо, но не факт что оно будет полностью покрывать все множество (1,P-1).

Пример кода на Python

def rand(N):
  return N*q-int(N*q/P)*P

P=101
m=3
q=P-3**m

R=rand(37)
print(R)
for i in range(100):
  R=rand(R)
  print(R)

Кольца псевдослучайных последовательностей

(просто рассуждение, не является строгим математическим доказательством)

• Пусть rand(n) функция генерирующая псевдослучайные числа в диапазоне [1,N], где n также принадлежит этому диапазону.
• Псевдослучайное, означает вычисляемое, т.е. мы не можем получить различные резултаты при одних и тех же исходных данных.
• Из этого следует, что Ni+1=rand(Ni) будет генерировать замкнутую последовательность чисел (кольцо) в рамках заданного диапазона.
• Все множество натуральных чисел в заданном диапазоне будет разделяться на не пересекающиеся подмножества (кольца).
• Объединение всех колец будет полностью покрывать все множество диапазона.
• Количество и состав колец будет определяться только особенностями алгоритма вычисления псевдослучайных чисел.
• В частности, потенциально возможен алгоритм, который будет порождать только одно кольцо, покрывающее весь диапазон.
• Если не получается получить одно кольцо, то в каждом частном случае диапазона можно получить все кольца и определить точки входа в них, тогда можно встроить в алгоритм условие при завершении прохода по любому кольцу переходить на точку входа следующего
• последовательность чисел в каждом кольце выдаваемая алгоритмом будет всегда фиксирована, чтобы построить другую последовательность придется менять алгоритм или его параметры, что будет менять структуру формируемых колец