Математика: Теория чисел.

Найти длину периода и сам период бесконечной степенной дроби по основанию Р, представляющей рациональное число N/M (для конечных дробей считать, что длина периода равна 1). M,N,P - целые десятичные числа, 0<N<M, 1<P.

Введем переменную N₁=N.

Пусть N₁ и M заданы в десятичной системе счисления. Переведем дробь N₁/M в систему счисления с основанием p:

Пусть в системе с основанием p искомая дробь 0.a(1)a(2)...

Получаем:

a(1)*p^-1+a(2)*p^-2+ ... =N₁/M.

Умножим правую и левую части равенства на p:

Выделяя целую часть выражений слева и справа от знака равенства, получаем

a(1) = целая часть (N₁*p/M).

Обозначим N₂ = N₁*p mod M; очевидным образом получаем

Домножая на p и находя целую часть, опять же имеем

a(2) = целая часть (N₂*p/M);

продолжая аналогично, определяем коэффициенты a(3),a(4) и т.д.

В ходе выделения цифр a_i мы можем получить различных значений Ni не более чем M (по алгоритму выше у нас всегда Ni<M).

Если вдруг какие-то два остатка совпадают: Ni=Nj, i<>j, то совпадают и цифры разложения: a_i+1=a_j+1, a_i+2=a_j+2, ... , т.е. цифры (a_i+1, ... ,a_j) образуют один из кратных периодов. Нам надо найти минимальную длину такой периодически повторяющейся последовательности, которая равна количеству цифр между двумя ближайшими повторяющимися остатками, и сами цифры.

Выделяем M цифр p-ичной дроби (исходя из вышесказанного, к этому моменту период уже обязан начаться). Запоминаем N_m, и ищем первый такой остаток N_k, k>m, что N_m=N_k. Величина k-m как раз и есть искомая длина периода.

Вверх по странице, к оглавлению и навигации.