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

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

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

9981 - 1899 = 8082

8820 - 0288 = 8532

8532 - 2358 = 6174

7641 - 1467 = 6174

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

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

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

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

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

Например, в десятичной системе счисления , начиная с 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 как константой Капрекара.

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

Обратите внимание, что цифры $\alpha$ и $\beta$ имеют одинаковую сумму цифр и, следовательно, одинаковый остаток по модулю $b-1$ . Следовательно, каждое число в последовательности Капрекара с основанием $b$ числа (кроме, возможно, первого) кратны $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 к

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

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 = 2 k$ для всех натуральных чисел $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...$

Константы Капрекара и циклы отображения Капрекара для конкретной базы b

Все числа выражаются в системе счисления $b$ с использованием A-Z для обозначения значений цифр от 10 до 35.

База $б$	Длина цифры	Нетривиальные (ненулевые) константы Капрекара	Циклы
2	2	01 ^{[ примечание 1 ]}	∅
	3	011 ^{[ примечание 1 ]}	∅
	4	0111, ^{[ примечание 1 ]} 1001	∅
	5	01111, ^{[ примечание 1 ]} 10101	∅
	6	011111, ^{[ примечание 1 ]} 101101, 110001	∅
	7	0111111, ^{[ примечание 1 ]} 1011101, 1101001	∅
	8	01111111, ^{[ примечание 1 ]} 10111101, 11011001, 11100001	∅
	9	011111111, ^{[ примечание 1 ]} 101111101, 110111001, 111010001	∅
	10	0111111111, ^{[ примечание 1 ]} 1011111101, 1101111001, 1110110001, 1111000001	∅
3	2	∅	∅
	3	∅	022 → 121 → 022 ^{[ примечание 1 ]}
	4	∅	1012 → 1221 → 1012
	5	20211	∅
	6	∅	102212 → 210111 → 122221 → 102212
	7	2202101	2022211 → 2102111 → 2022211
	8	21022111	∅
	9	222021001	220222101 → 221021101 → 220222101 202222211 → 210222111 → 211021111 → 202222211
	10	2210221101	1022222212 → 2102222111 → 2111011111 → 1222222221 → 1022222212
4	2	∅	03 → 21 → 03 ^{[ примечание 1 ]}
	3	132	∅
	4	3021	1332 → 2022 → 1332
	5	∅	20322 → 23331 → 20322
	6	213312, 310221, 330201	∅
	7	3203211	∅
	8	31102221, 33102201, 33302001	22033212 → 31333311 → 22133112 → 22033212
	9	221333112, 321032211, 332032101	∅
	10	3111022221, 3220332111, 3311022201, 3331022001, 3333020001	∅
5	2	13	∅
	3	∅	143 → 242 → 143
	4	3032	∅
	5	∅	30432 → 40431 → 42411 → 32412 → 30432
	6	∅	214423 → 320322 → 304432 → 414421 → 331212 → 214423
	7	∅	3204322 → 4104331 → 4314211 → 3314212 → 3204322
	8	∅	30444432 → 42103321 → 42144221 → 33144212 → 33103312 → 32203222 → 30444432
	9	432043211	∅
	10	∅	3044444432 → 4210443321 → 4331033111 → 4222122221 → 3044444432
6	2	∅	05 → 41 → 23 → 05 ^{[ примечание 1 ]}
	3	253	∅
	4	∅	1554 → 4042 → 4132 → 3043 → 3552 → 3133 → 1554
	5	41532	31533 → 35552 → 31533
	6	325523, 420432, 530421	205544 → 525521 → 432222 → 205544
	7	∅	4405412 → 5315321 → 4405412
	8	43155322, 55304201	31104443 → 43255222 → 33204323 → 41055442 → 54155311 → 44404112 → 43313222 → 31104443 42104432 → 43204322 → 42104432 53104421 → 53304221 → 53104421
	9	332555223	441054412 → 533153221 → 441054412
	10	4321044322, 4421553312, 5331044221, 5553042001	4211044432 → 4332043222 → 4211044432 5311044421 → 5333042221 → 5311044421 5531044201 → 5533042201 → 5531044201
7	2	∅	∅
	3	∅	264 → 363 → 264
	4	∅	3054 → 5052 → 5232 → 3054
	5	∅	40653 → 61641 → 54612 → 52632 → 42633 → 40653
	6	∅	320544 → 520542 → 531432 → 416643 → 526632 → 441423 → 320544
	7	∅	5306532 → 6316431 → 5506512 → 6426321 → 5416422 → 5316432 → 5306532
	8	∅	42166443 → 54066522 → 64305321 → 64166421 → 55366212 → 54314322 → 42166443
	9	∅	530666532 → 643164321 → 552065412 → 643263321 → 541666422 → 544065222 → 633164331 → 550666512 → 653666211 → 554263212 → 533164332 → 530666532
	10	∅	5316666432 → 5433053322 → 5316666432 5431055322 → 5431664322 → 5431055322 5440665222 → 6432663321 → 5440665222
8	2	25	07 → 61 → 43 → 07 ^{[ примечание 1 ]}
	3	374	∅
	4	∅	1776 → 6062 → 6332 → 3774 → 4244 → 1776 3065 → 6152 → 5243 → 3065
	5	∅	42744 → 47773 → 42744 51753 → 61752 → 63732 → 52743 → 51753
	6	437734, 640632	310665 → 651522 → 532443 → 310665
	7	6417532	5407633 → 7317541 → 6617512 → 6537322 → 5417533 → 6217552 → 6427432 → 5407633 6407632 → 7427431 → 6507622 → 7437331 → 6407632
	8	75306421	31106665 → 65515222 → 53324443 → 31106665 64106632 → 65406322 → 64306432 → 64106632
	9	443777334	543076433 → 732076541 → 764175311 → 665175212 → 654274322 → 543076433 644076332 → 743076431 → 763076411 → 765274211 → 664274312 → 644076332 651076622 → 754373321 → 652076522 → 744274331 → 651076622
	10	7753064201	3111066665 → 6555152222 → 5333244443 → 3111066665 6411066632 → 6554063222 → 6433064432 → 6411066632 6431066432 → 6541066322 → 6543064322 → 6431066432 7531066421 → 7553064221 → 7533064421 → 7531066421
9	2	∅	17 → 53 → 17
	3	∅	385 → 484 → 385
	4	∅	3076 → 7252 → 5254 → 3076 5074 → 7072 → 7432 → 5074
	5	62853	52854 → 60873 → 83841 → 74832 → 63843 → 52854
	6	∅	308876 → 850731 → 861621 → 753432 → 520764 → 740742 → 748832 → 652533 → 421665 → 540744 → 708872 → 858821 → 762522 → 542544 → 308876
	7	∅	6518633 → 7328552 → 6518633
	8	65288533	65407433 → 73188652 → 76407422 → 75388432 → 65407433
	9	753186532	641888643 → 754186432 → 753087532 → 854186431 → 773087512 → 865384321 → 763186522 → 754285432 → 652087633 → 853285531 → 762186622 → 754384432 → 641888643
	10	6632885523	5288888854 → 6432885543 → 6531077533 → 7632166522 → 6444164443 → 5288888854 6441886443 → 7521886632 → 7653075322 → 7542166432 → 6441886443
10 ^{[ 4 ]}	2	∅	09 → 81 → 63 → 27 → 45 → 09 ^{[ примечание 1 ]}
	3	495	∅
	4	6174	∅
	5	∅	53955 → 59994 → 53955 61974 → 82962 → 75933 → 63954 → 61974 62964 → 71973 → 83952 → 74943 → 62964
	6	549945, 631764	420876 → 851742 → 750843 → 840852 → 860832 → 862632 → 642654 → 420876
	7	∅	7509843 → 9529641 → 8719722 → 8649432 → 7519743 → 8429652 → 7619733 → 8439552 → 7509843
	8	63317664, 97508421	43208766 → 85317642 → 75308643 → 84308652 → 86308632 → 86326632 → 64326654 → 43208766 64308654 → 83208762 → 86526432 → 64308654
	9	554999445, 864197532	865296432 → 763197633 → 844296552 → 762098733 → 964395531 → 863098632 → 965296431 → 873197622 → 865395432 →753098643 → 954197541 → 883098612 → 976494321 → 874197522 → 865296432
	10	6333176664, 9753086421, 9975084201	8655264432 → 6431088654 → 8732087622 → 8655264432 8653266432 → 6433086654 → 8332087662 → 8653266432 8765264322 → 6543086544 → 8321088762 → 8765264322 8633086632 → 8633266632 → 6433266654 → 4332087666 → 8533176642 → 7533086643 → 8433086652 → 8633086632 9775084221 → 9755084421 → 9751088421 → 9775084221
11	2	37	∅
	3	∅	4А6 → 5А5 → 4А6
	4	∅	3098 → 9452 → 7094 → 9272 → 7454 → 3098 5096 → 9092 → 9632 → 7274 → 5276 → 5096
	5	∅	72А74 → 82А73 → 84А53 → 73А64 → 72А74
	6	∅	531876 → 740964 → 931872 → 863643 → 531876
	7	∅	631А875 → 951А852 → 972А732 → 873А633 → 753А654 → 730А974 → А62А741 → 982А722 → 875А433 → 752А754 → 831А873 → 954А552 → 84ААА53 → 764А544 → 631А875 751А854 → 941А862 → 973А632 → 863А643 → 751А854
	8	74318764	53218876 → 76409644 → 93218872 → 86636443 → 53218876 75218854 → 762AA744 → 86309743 → 95418652 → 861AA843 → 97418632 → 86418643 → 75218854
	9	9751A8532	871AAA833 → 9770A9332 → A763A6431 → 9741A8632 → 9752A7532 → 8741A8633 → 9552A7552 → 871AAA833
	10	∅	5322188876 → 7664096444 → 9322188872 → 8666364443 → 5322188876 7432188764 → 7643187644 → 7432188764 7631AA8744 → 9743097632 → 9744186632 → 8642188643 → 7652188544 → 7631AA8744 8621AA8843 → 9854186522 → 8661AA8443 → 9743AA6632 → 8762AA7433 → 8753097533 → 9543AA6652 → 8751099533 → 9853AA6522 → 8863097423 → 9654186542 → 8621AA8843
12	2	∅	0B → A1 → 83 → 47 → 29 → 65 → 0B ^{[ примечание 1 ]}
	3	5Б6	∅
	4	∅	3BB8 → 8284 → 6376 → 3BB8 4198 → 8374 → 5287 → 6196 → 7BB4 → 7375 → 4198
	5	83Б74	64B66 → 6BBB5 → 64B66
	6	65BB56	420A98 → A73742 → 842874 → 642876 → 62BB86 → 951963 → 860A54 → A40A72 → A82832 → 864654 → 420A98
	7	962Б853	841B974 → A53B762 → 971B943 → A64B652 → 960BA53 → B73B741 → A82B832 → 984B633 → 863B754 → 841B974
	8	873ББ744, А850А632	4210AA98 → A9737422 → 87428744 → 64328876 → 652BB866 → 961BB953 → A8428732 → 86528654 → 6410AA76 → A92BB822 → 9980A323 → A7646542 → 8320A984 → A7537642 → 8430A874 → A5428762 → 8630A854 → A540X762 → A830A832 → A8546632 → 8520A964 → A740A742 → A8328832 → 86546654
	9	665BBB556	8620BA954 → B852B8631 → A952B8622 → 9872B8433 → 9653B7653 → 8620BA954 8640BA754 → B641B9751 → AA51B9612 → A983B7322 → 9864B6533 → 8640BA754 9630BA853 → B762B8541 → A941B9722 → A874B6432 → 9742B8743 → 9642B8753 → 9641B9753 → A651B9652 → A840BA732 → B873B7431 → A852B8632 → 9852B8633 → 9652B8653 → 9630BA853
	10	8843BB7734	64310AA876 → A952BB8622 → 9984197323 → 8765286544 → 64310AA876 87650A6544 → A4310AA872 → A985286322 → 87650A6544 A8510AA632 → A9850A6322 → A8750A6432 → A8530A8632 → A8550A6632 → A8510AA632
13	2	∅	1Б → 93 → 57 → 1Б
	3	∅	5C7 → 6C6 → 5C7
	4	∅	30BA → B652 → 90B4 → B472 → 9294 → 7476 → 30BA 50Б8 → Б292 → 9654 → 50Б8 5298 → 7296 → 70B6 → B0B2 → B832 → 9474 → 5298
	5	∅	83C85 → 92C94 → A4C73 → 95C64 → 83C85
	6	951А74	∅
	7	∅	951CA74 → B63C862 → A81CA43 → B75C652 → A61CA63 → B73C852 → A82C943 → A74C753 → 961CA64 → B62C962 → A92C933 → A75C653 → 951CA74 972C954 → A53C873 → 972C954 A71CA53 → B74C752 → A71CA53
	8	9541А874	641CCA87 → B840B842 → B9438832 → 96538764 → 641CCA87
	9	∅	9620CBA64 → C962C9631 → BA62C9622 → A982C9433 → A764C7653 → 9620CBA64 A751CA753 → B751CA752 → B951CA732 → B973C8532 → A862C9643 → A751CA753 A861CA643 → B761CA652 → B950CB732 → C983C8431 → B963C8632 → A861CA643
	10	95441A8874	86661A6665 → 92CCCCCC94 → A832CC9943 → A9750B7533 → B7621AA652 → A881CCA443 → B965CC6632 → A962CC9633 → A973299533 → 86661A6665 99650B7634 → B651CCA762 → BA640B8622 → B983CC8432 → A984CC7433 → 99650B7634 A8630B9643 → B763CC8652 → A9620BA633 → B875CC6542 → A8630B9643
14	2	49	2Б → 85 → 2Б 0D → C1 → A3 → 67 → 0D ^{[ примечание 1 ]}
	3	6Д7	∅
	4	∅	61Б8 → А1Б4 → А574 → 61Б8
	5	∅	75Д77 → 7ДДД6 → 75Д77 93D95 → A3D94 → A5D74 → 94D85 → 93D95
	6	76ДД67	530CA9 → C73962 → A60C74 → C60C72 → CA0C32 → CA6632 → A6DD64 → 973965 → 640C98 → C51B82 → B92A43 → 974865 → 530CA9 A40C94 → C64872 → A40C94 A80C54 → C62A72 → A80C54
	7	∅	A62DA74 → B63D973 → A82DA54 → B64D873 → A71DB64 → C73D962 → B92DA43 → B85D753 → A62DA74
	8	CA70C632	7550C887 → C32DDAA2 → BB8DD423 → BA72A633 → 9770C665 → C410CC92 → CBA48322 → A9739644 → 7550C887 A410CC94 → CB648722 → A940C944 → C6548872 → A430CA94 → C7648762 → A410CC94 A810CC54 → CB62A722 → A980C544 → C652A872 → A830CA54 → C762A762 → A810CC54
	9	776ДДД667, Б852ДА853	A731DBA64 → C863D9752 → B941DB943 → C874D8652 → B831DBA53 → C884D8552 → B832DAA53 → B874D8653 → A731DBA64
15	2	∅	∅
	3	∅	6Е8 → 7Е7 → 6Е8
	5	А4Е95	∅
	6	∅	41EECB → DA0D42 → DB5832 → B82B64 → 971C76 → B2EEB4 → C9EE43 → BA2B44 → 975876 → 41EECB 960D86 → D31CB2 → CA7643 → 960D86
	7	∅	A62EB85 → C63EA83 → B93EA54 → B74E974 → A71EC75 → D72EB72 → CB3EA33 → B97E654 → A62EB85 B70ED74 → E93EA51 → DB4E932 → CA6E743 → B83EA64 → B73EA74 → B72EB74 → C73EA73 → B92EB54 → C75E873 → B70ED74
	8	А94ЕЕ955	8640DA87 → D620DC82 → 8640DA87
	9	C962EB853	A742EBA75 → C752EB973 → C961EC853 → D972EB752 → CB61EC833 → D994E9552 → C943EAA53 → B964E9854 → A742EBA75 B862EB864 → C751EC973 → D971EC752 → DB71EC732 → DB93EA532 → CA84E9643 → B862EB864
	10	АА54ЕЕ9945	96660D8886 → D3221CCCB2 → CAAA764443 → 96660D8886 B761EEC874 → DA640DA842 → DB661C8832 → CA821CC643 → BA961C8544 → B7641CA874 → B761EEC874
16 ^{[ 5 ]}	2	∅	2D → A5 → 4B → 69 → 2D 0F → E1 → C3 → 87 → 0F ^{[ примечание 1 ]}
	3	7F8	∅
	4	∅	3FFC → C2C4 → A776 → 3FFC А596 → 52СВ → А596 E0E2 → EB32 → C774 → 7FF8 → 8688 → 1FFE → E0E2 E952 → C3B4 → 9687 → 30ED → E952
	5	∅	86F88 → 8FFF7 → 86F88 A3FB6 → C4FA4 → B7F75 → A3FB6 A4FA6 → B3FB5 → C5F94 → B6F85 → A4FA6
	6	87FF78	310EED → ED9522 → CB3B44 → 976887 → 310EED 532CCB → A95966 → 532CCB 840EB8 → E6FF82 → D95963 → A42CB6 → A73B86 → 840EB8 A80E76 → E40EB2 → EC6832 → C91D64 → C82C74 → A80E76 C60E94 → E82C72 → CA0E54 → E84A72 → C60E94
	7	C83FB74	B62FC95 → D74FA83 → C92FC64 → D85F973 → C81FD74 → E94FA62 → DA3FB53 → CA5F954 → B74FA85 → B62FC95 B71FD85 → E83FB72 → DB3FB43 → CA6F854 → B73FB85 → C63FB94 → C84FA74 → B82FC75 → D73FB83 → CA3FB54 → C85F974 → B71FD85
	8	∅	3110EEED → EDD95222 → CBB3B444 → 97768887 → 3110EEED 5332CCCB → A9959666 → 5332CCCB 7530ECA9 → E951DA62 → DB52CA43 → B974A865 → 7530ECA9 A832CC76 → A940EB66 → E742CB82 → CA70E854 → E850EA72 → EC50EA32 → EC94A632 → C962C964 → A832CC76 C610EE94 → ED82C722 → CBA0E544 → E874A872 → C610EE94 C630EC94 → E982C762 → CA30EC54 → E984A762 → C630EC94 C650EA94 → E852CA72 → CA50EA54 → E854AA72 → C650EA94 CA10EE54 → ED84A722 → CB60E944 → E872C872 → CA10EE54
	9	887FFF778, DA72FC853	C851FDA74 → E972FC862 → DC61FD933 → EAA5F9552 → D954FAA63 → C953FBA64 → C863FB974 → C851FDA74 C862FC974 → D861FD973 → EA71FD852 → EC82FC732 → DC94FA633 → CA83FB754 → C862FC974 CA40FEB54 → FA85F9751 → EA51FDA52 → EC84FA732 → DB82FC743 → DA83FB753 → CA62FC954 → D873FB873 → CA40FEB54

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Ведущие нули сохранены.

Константы Капрекара по основанию 10.

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

В 1949 году доктор Капрекар открыл ^{[ 6 ]} что если описанный выше процесс применить к четырехзначным числам по основанию 10 , последовательность сходится к 6174 за семь итераций или, что реже, сходится к 0. Число 6174 является первой открытой константой Капрекара, и поэтому иногда его называют как постоянная Капрекара . ^{[ 7 ]}^{[ 8 ]}^{[ 9 ]}

Набор чисел, сходящихся к нулю, зависит от того, отбрасываются ли ведущие нули (обычная формулировка) или сохраняются (как в исходной формулировке Капрекара). В обычной формулировке имеется 77 четырёхзначных чисел, сходящихся к нулю: ^{[ 10 ]} например, 2111. Однако в исходной формулировке Капрекара ведущие нули сохраняются, и только повторяющиеся цифры, такие как 1111 или 2222, сопоставляются с нулем. Этот контраст проиллюстрирован ниже:

отбросить ведущие нули	сохранять ведущие нули
2111 − 1112 = 999 999 − 999 = 0	2111 − 1112 = 0999 9990 − 0999 = 8991 9981 − 1899 = 8082 8820 − 0288 = 8532 8532 − 2358 = 6174

Ниже приведена блок-схема. Ведущие нули сохраняются, однако единственная разница при их удалении состоит в том, что вместо 0999, соединяющегося с 8991, мы получаем 999, соединяющуюся с 0.

Последовательность преобразований Капрекара, заканчивающаяся на 6174.

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

Если процедура Капрекара применяется к числам из трех цифр по основанию 10, результирующая последовательность почти всегда будет сходиться к значению 495 не более чем за шесть итераций, за исключением небольшого набора исходных чисел, которые вместо этого сходятся к 0. ^{[ 7 ]}

Набор чисел, сходящихся к нулю, зависит от того, отбрасываются ли ведущие нули (обычная формулировка) или сохраняются (как в исходной формулировке Капрекара). В обычной формулировке имеется 60 трёхзначных чисел, сходящихся к нулю: ^{[ 11 ]} например, 211. Однако в исходной формулировке Капрекара ведущие нули сохраняются, и только повторяющиеся цифры, такие как 111 или 222, сопоставляются с нулем.

Ниже приведена блок-схема. Ведущие нули сохраняются, однако единственная разница при удалении ведущих нулей заключается в том, что вместо 099, соединяющегося с 891, мы получаем 99, соединяющиеся с 0.

Последовательность трехзначных преобразований Капрекара, заканчивающаяся на 495

Другая длина цифр

Для длин цифр, отличных от трех или четырех (по основанию 10), программа может завершиться в одной из нескольких фиксированных точек или вместо этого может войти в один из нескольких циклов, в зависимости от начального значения последовательности. ^{[ 7 ]} См. таблицу в разделе выше для по основанию 10 фиксированных точек и циклов .

Количество циклов быстро увеличивается с увеличением длины цифр, и все эти циклы, за исключением небольшой группы, имеют длину три. Например, для 20-значных чисел с основанием 10 существует четырнадцать констант (циклов длиной один) и девяносто шесть циклов длиной больше единицы, все из которых, кроме двух, имеют длину три. Нечетная длина цифр дает меньше разных конечных результатов, чем четная длина цифр. ^{[ 12 ]}^{[ 13 ]}

Иногда эти числа (495, 6174 и их аналоги с другой длиной цифр или с основанием, отличным от 10) называют «константами Пейюша» в честь Пейюша Дикшита, который решил эту задачу в рамках своего IMO 2000 (Международная математическая олимпиада, 2000 год). ) диссертация. ^{[ 14 ]}

Пример программирования

В приведенном ниже примере реализуется отображение Капрекара, описанное в определении выше, для поиска констант и циклов Капрекара в Python .

import string
from collections import deque
from collections.abc import Sequence, Generator


BASE36_DIGITS = f"{string.digits}{string.ascii_uppercase}"


def digit_count(x: int, /, base: int = 10) -> int:
    count = 0
    while x > 0:
        count += 1
        x //= base
    return count


def get_digits(x: int, /, base: int = 10, init_k: int = 0) -> str:
    if init_k > 0:
        k = digit_count(x, base)
    digits = deque()
    while x > 0:
        digits.appendleft(BASE36_DIGITS[x % base])
        x //= base
    if init_k > 0:
        for _ in range(k, init_k):
            digits.appendleft("0")
    return "".join(digits)


def kaprekar_map(x: int, /, base: int = 10, init_k: int = 0) -> int:
    digits = "".join(sorted(get_digits(x, base, init_k)))
    descending = int("".join(reversed(digits)), base)
    ascending = int(digits, base)
    return descending - ascending


def kaprekar_cycle(
    x: int | str | bytes | bytearray, /, base: int = 10
) -> list[int | str]:
    """
    Return Kaprekar's cycles as list

    >>> kaprekar_cycle(8991)
    [6174]
    >>> kaprekar_cycle(865296432)
    [865296432, 763197633, 844296552, 762098733, 964395531, 863098632, 965296431, 873197622, 865395432, 753098643, 954197541, 883098612, 976494321, 874197522]
    >>> kaprekar_cycle('09')
    [9, 81, 63, 27, 45]
    >>> kaprekar_cycle('0F', 16)
    ['0F', 'E1', 'C3', '87']
    >>> kaprekar_cycle('B71FD85', 16)
    ['B71FD85', 'E83FB72', 'DB3FB43', 'CA6F854', 'B73FB85', 'C63FB94', 'C84FA74', 'B82FC75', 'D73FB83', 'CA3FB54', 'C85F974']

    """
    leading_zeroes_retained = not isinstance(x, int)
    init_k = len(x) if leading_zeroes_retained else 0
    x = int(x) if base == 10 else int(x, base)
    seen = []
    while x not in seen:
        seen.append(x)
        x = kaprekar_map(x, base, init_k)
    cycle = []
    while x not in cycle:
        cycle.append(x)
        x = kaprekar_map(x, base, init_k)
    return cycle if base == 10 else [get_digits(x, base, init_k) for x in cycle]


if __name__ == "__main__":
    import doctest

    doctest.testmod()

См. также

Цитаты

^ Ганновер, 2017 , с. 1, Обзор.
^ Ганновер, 2017 , с. 3. Методология.
^ (последовательность A099009 в OEIS )
^ «Образец серии Капрекар» .
^ «Образец серии Капрекар для шестнадцатеричных чисел» .
^ Капрекар Д.Р. (1955). «Интересное свойство числа 6174». Математическое письмо . 15 : 244–245.
^ Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Рутина Капрекара» . Математический мир .
↑ Ютака Нисияма , Загадочное число 6174.
^ Капрекар Д.Р. (1980). «О числах Капрекара». Журнал развлекательной математики . 13 (2): 81–82.
^ (последовательность A069746 в OEIS )
^ (последовательность A090429 в OEIS )
^ «Образец серии Капрекар» .
^ «Игра с цифрами» .
^ Ганновер, 2017 , с. 14, Операции.

Ссылки

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

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

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

[retained-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д Ведущие нули сохранены.

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

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

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

[sourceforge_dec-5] «Образец серии Капрекар» .

[sourceforge_hex-6] «Образец серии Капрекар для шестнадцатеричных чисел» .

[Kaprekar1955-7] Капрекар Д.Р. (1955). «Интересное свойство числа 6174». Математическое письмо . 15 : 244–245.

[mathworld-8] Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Рутина Капрекара» . Математический мир .

[9] Ютака Нисияма , Загадочное число 6174.

[Kaprekar1980-10] Капрекар Д.Р. (1980). «О числах Капрекара». Журнал развлекательной математики . 13 (2): 81–82.

[11] (последовательность A069746 в OEIS )

[12] (последовательность A090429 в OEIS )

[13] «Образец серии Капрекар» .

[14] «Игра с цифрами» .

[IMO2000-15] Ганновер, 2017 , с. 14, Операции.

[ 1 ]

[ 2 ]

[ 3 ]

[ примечание 1 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]