Распорядок дня Капрекара

Итеративный алгоритм

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

В качестве примера возьмем число 8991 в десятичной системе счисления :

9981 – 1899 = 8082

8820 – 0288 = 8532

8532 – 2358 = 6174

7641 – 1467 = 6174

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

Определение и свойства

Алгоритм следующий: ^[2]

1. Выберите любое натуральное число в данной системе счисления . Это первое число последовательности. ${\displaystyle n}$ ${\displaystyle b}$
2. Создайте новое число , отсортировав цифры в порядке убывания, и еще одно число , отсортировав цифры в порядке возрастания. Эти числа могут иметь ведущие нули, которые можно игнорировать. Вычтите, чтобы получить следующее число последовательности. ${\displaystyle \alpha }$ ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle n}$ ${\displaystyle \alpha -\beta }$
3. Повторите шаг 2.

Последовательность называется последовательностью Капрекара, а функция — отображением Капрекара. Некоторые числа отображаются сами на себя; это неподвижные точки отображения Капрекара, ^[3] и называются константами Капрекара. Ноль является константой Капрекара для всех базисов , и поэтому называется тривиальной константой Капрекара. Все остальные константы Капрекара являются нетривиальными константами Капрекара. ${\displaystyle K_{b}(n)=\alpha -\beta }$ ${\displaystyle b}$

Например, в десятичной системе счисления , начиная с 3524,

${\displaystyle K_{10}(3524)=5432-2345=3087}$

${\displaystyle K_{10}(3087)=8730-378=8352}$

${\displaystyle K_{10}(8352)=8532-2358=6174}$

${\displaystyle K_{10}(6174)=7641-1467=6174}$

с 6174 в качестве константы Капрекара.

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

Обратите внимание, что числа и имеют одинаковую сумму цифр и, следовательно, одинаковый остаток по модулю . Таким образом, каждое число в последовательности Капрекара базовых чисел (кроме, возможно, первого) является кратным . ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle b-1}$ ${\displaystyle b}$ ${\displaystyle b-1}$

При сохранении ведущих нулей только повторные цифры приводят к тривиальной константе Капрекара.

Семейства констант Капрекара

В системе счисления с основанием 4 можно легко показать, что все числа вида 3021, 310221, 31102221, 3...111...02...222...1 (где длина последовательности «1» и длина последовательности «2» одинаковы) являются неподвижными точками отображения Капрекара.

В системе счисления с основанием 10 можно легко показать, что все числа вида 6174, 631764, 63317664, 6...333...17...666...4 (где длина последовательности «3» и длина последовательности «6» одинаковы) являются неподвижными точками отображения Капрекара.

б= 2к

Можно показать, что все натуральные числа

${\displaystyle m=(k)b^{2n+3}\left(\sum _{i=0}^{n-1}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b\left(\sum _{i=0}^{n-1}b^{i}\right)+(k)}$

являются неподвижными точками отображения Капрекара в четном основании b = 2k для всех натуральных чисел n .

Доказательство

${\displaystyle \alpha =(2k-1)b^{2n+2}\left(\sum _{i=0}^{n}b^{i}\right)+(k)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)\left(\sum _{i=0}^{n}b^{i}\right)}$

${\displaystyle \beta =(k-1)b^{2n+2}\left(\sum _{i=0}^{n}b^{i}\right)+(k)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(2k-1)\left(\sum _{i=0}^{n}b^{i}\right)}$

${\displaystyle {\begin{aligned}K_{b}(m)&=\alpha -\beta \\&=((2k-1)-(k-1))b^{2n+2}\left(\sum _{i=0}^{n}b^{i}\right)+(k-k)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+((k-1)-(2k-1))\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+2}\left(\sum _{i=0}^{n}b^{i}\right)-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+b^{2n+2}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k)b^{2n+1}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{2n+1}+b^{2n+1}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{2n+1-1}\left(\sum _{i=0}^{1}b^{i}\right)+b^{2n+1-1}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{2n+1-n}\left(\sum _{i=0}^{n}b^{i}\right)+b^{2n+1-n}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+b^{n+1}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(2k)b^{n}-k\left(\sum _{i=0}^{n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+kb^{n}-k\left(\sum _{i=0}^{n-1}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{n+1-1}+b^{n+1-1}-k\left(\sum _{i=0}^{n-n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{n+1-n}\left(\sum _{i=0}^{n}b^{i}\right)+b^{n+1-n}-k\left(\sum _{i=0}^{n-n}b^{i}\right)\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b\left(\sum _{i=0}^{n}b^{i}\right)+b-k\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b\left(\sum _{i=0}^{n}b^{i}\right)+2k-k\\&=kb^{2n+3}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b^{2n+2}+(2k-1)b^{n+1}\left(\sum _{i=0}^{n}b^{i}\right)+(k-1)b\left(\sum _{i=0}^{n}b^{i}\right)+k\\&=m\\\end{aligned}}}$

Смотрите также

• Арифметическая динамика
• гипотеза Коллатца
• Число Дьюдени
• Факторион
• Счастливое число
• Число Капрекара
• Число Меертенса
• Нарциссическое число
• Совершенный инвариант от цифры к цифре
• Совершенный цифровой инвариант
• Сумма-произведение числа
• Алгоритм сортировки

Цитаты

1. Ганновер 2017, стр. 1, Обзор.
2. Ганновер 2017, стр. 3, Методология.
3. (последовательность A099009 в OEIS )

Ссылки

• Хановер, Дэниел (2017). «Зависимое от базы поведение рутины Капрекара: теоретическое и вычислительное исследование, раскрывающее новые закономерности». Международный журнал чистой и прикладной математики . arXiv : 1710.06308 .

Внешние ссылки

• Боули, Роджер (5 декабря 2011 г.). «6174 — константа Капрекара». Numberphile . Ноттингемский университет : Брэди Харан . Получено 17.01.2024 .
• Рабочая ссылка на YouTube
• Пример (Perl) кода для преобразования любого четырехзначного числа в константу Капрекара
• Пример кода (Python) для преобразования любого четырехзначного числа в константу Капрекара