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

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

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

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

9981 - 1899 = 8082

8820 - 0288 = 8532

8532 - 2358 = 6174

7641 - 1467 = 6174

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

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

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

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

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

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

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

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

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

K_{10}(6174)=7641-1467=6174

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

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

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

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

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

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

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

б= 2к

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

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$ .

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

$\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)$

$\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)$

${\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$	$2$	$011, 101101, 110111001, 111011110001...$
$2$	$4$	$132, 213312, 221333112, 222133331112...$
$3$	$6$	$253, 325523, 332555223, 333255552223...$
$4$	$8$	$374, 437734, 443777334, 444377773334...$
$5$	$10$	$495, 549945, 554999445, 555499994445...$
$6$	$12$	$5Б6, 65ББ56, 665БББ556, 6665ББББ5556...$
$7$	$14$	$6Д7, 76ДД67, 776ДДД667, 7776ДДДД6667...$
$8$	$16$	$7F8, 87FF78, 887FFF778, 8887FFeFF7778...$
$9$	$18$	$8H9, 98HH89, 998HHH889, 9998HHHH8889...$

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

Цитаты

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

Ссылки

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

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

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

[FOOTNOTEHanover20171Overview-1] Ганновер 2017, стр. 1, Обзор.

[FOOTNOTEHanover20173Methodology-2] Ганновер 2017, стр. 3, Методология.

[A099009-3] (последовательность A099009 в OEIS )