Введение

Итеративный алгоритм
В теории чисел рутина Капрекара — это итеративный алгоритм, названный в честь его изобретателя, индийского математика Д. Р. Капрекара. Каждая итерация начинается с числа, цифры которого упорядочиваются по убыванию и по возрастанию, после чего вычисляется разность между полученными числами. Например, начнем с числа 8991 в десятичной системе счисления:

1 = 9981 – 1899 = 8082
1 = 8820 – 0288 = 8532
1 = 8532 – 2358 = 6174
1 = 7641 – 1467 = 6174

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

Семьи констант Капрекара

В системе счисления 4 можно легко показать, что все числа вида 3021, 310221, 31102221, 3 111 02 222 1 (где длина последовательности "1" и длина последовательности "2" равны) являются неподвижными точками преобразования Капрекара. В системе счисления 10 можно легко показать, что все числа вида 6174, 631764, 63317664, 6 333 17 666 4 (где длина последовательности "3" и длина последовательности "6" равны) являются неподвижными точками преобразования Капрекара.

Числа длиной в три цифры

Если капрекарская процедура применяется к трехузначным числам в десятичной системе счисления, полученная последовательность почти всегда сходится к значению 495 не более чем за шесть итераций, за исключением небольшого набора начальных чисел, которые вместо этого сходятся к 0, например, 211. Однако в оригинальной формулировке Капрекара сохраняются ведущие нули, и только числа, состоящие из одинаковых цифр, такие как 111 или 222, приводят к нулю. Ниже представлена блок-схема. Ведущие нули сохраняются, однако единственное отличие при отбрасывании ведущих нулей заключается в том, что вместо перехода 099 в 891, мы получаем переход 99 в 0.

Другие длины цифр

Для чисел, содержащих не три и не четыре цифры (в десятичной системе счисления), алгоритм может завершиться в одной из нескольких фиксированных точек или, вместо этого, попасть в один из нескольких циклов, в зависимости от начального значения последовательности. Иногда эти числа (495, 6174 и их аналоги для других длин чисел или систем счисления, отличных от десятичной) называют "константами Пейуша" в честь Пейуша Диксита, который решил эту задачу в рамках своей работы на Международной математической олимпиаде 2000 года (IMO 2000).