не могу подобрать коэффициенты для Линейного конгруэнтного метода
Xₙ₊₁ = (a * Xₙ + c) mod N
необходимо параметры a и c подобрать с помощью теоремы 1 так, чтобы период последовательности был максимальным T = N. Сама теорема:
Линейная конгруэнтная последовательность, определенная числами N, a, c и x0, имеет период T = N тогда и только тогда, когда:
числа c и N взаимно простые;
b = a − 1 кратно p для каждого простого p, являющегося делителем N;
b кратно 4, если N кратно 4.
Подбираю:N=125480,a=62741,c=13 всем условиям удовлетворяет: у N простые делители 5 и 3137, b=62740 делится на оба. N и с взаимно простые 100%, b и N кратно 4. Но не работает. Начальный X(0) не совпадает с X(N+1). подскажите что не так делаю?
Ответы (1 шт):
Рассмотрим цикл из двух чисел. Нулевое - 1, следующее - 2, потом опять 1, опять 2...
Ваше N+1-е число - третье - равно 2 и не равно нулевому. Значит, последовательность 1 2 1 2 ... не циклична с периодом 2? Так?
Пояснять, где ошибка?
Какое расстояние между N+1-м и нулевым числами? Неужели N?
Так что сравнивайте все же X(0) и X(N), так оно логичнее...
long long X(long long x) { return (62741*x + 13)%125480; }
int main()
{
long long x = 100;
for(int i = 0; i < 125480; ++i) x = X(x);
cout << x;
}
Посмотрите, что даст этот код, тут: https://ideone.com/27FA63