Рекурсивный алгоритм построения функции Дирихле

Abstract

Рассмотрена задача определения общего количества рациональных дробей, значения которых одинаковы и равны x. Продемонстрирована важность данной задачи для процедуры обработки статистических данных, представляющих собой соотношение двух дискретных величин с переменным знаменателем. Установлено, что искомое количество дробей равно значению функции Дирихле в точке x, для построения которой предложено оригинальное порождающее правило, имеющее простую геометрическую интерпретацию. Предложен вариант реализации данного алгоритма, показана его вычислительная эффективность, отмечена его важность в задачах, требующих генерации взаимно простых чисел.