Число Капрекара - Kaprekar number

Не путать с Постоянная Капрекара.

В математика, а натуральное число в данном база чисел это ${\displaystyle p}$-Число Капрекара если изображение его квадрата в этой основе можно разделить на две части, где вторая часть имеет ${\displaystyle p}$ цифры, которые в сумме составляют исходное число. Номера названы в честь Д. Р. Капрекар.

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

Позволять ${\displaystyle n}$ быть натуральным числом. Мы определяем Функция Капрекара для базы ${\displaystyle b>1}$ и власть ${\displaystyle p>0}$ ${\displaystyle F_{p,b}:\mathbb {N} \rightarrow \mathbb {N} }$ быть следующим:

${\displaystyle F_{p,b}(n)=\alpha +\beta }$,

куда ${\displaystyle \beta =n^{2}{\bmod {b}}^{p}}$ и

${\displaystyle \alpha ={\frac {n^{2}-\beta }{b^{p}}}}$

Натуральное число ${\displaystyle n}$ это ${\displaystyle p}$-Число Капрекара если это фиксированная точка за ${\displaystyle F_{p,b}}$, что происходит, если ${\displaystyle F_{p,b}(n)=n}$. ${\displaystyle 0}$ и ${\displaystyle 1}$ находятся тривиальные числа Капрекара для всех ${\displaystyle b}$ и ${\displaystyle p}$, все остальные числа Капрекара равны нетривиальные числа Капрекара.

Например, в база 10, 45 - это 2-число Капрекара, потому что

${\displaystyle \beta =n^{2}{\bmod {b}}^{p}=45^{2}{\bmod {1}}0^{2}=25}$

${\displaystyle \alpha ={\frac {n^{2}-\beta }{b^{p}}}={\frac {45^{2}-25}{10^{2}}}=20}$

${\displaystyle F_{2,10}(45)=\alpha +\beta =20+25=45}$

Натуральное число ${\displaystyle n}$ это общительный номер Капрекара если это периодическая точка за ${\displaystyle F_{p,b}}$, куда ${\displaystyle F_{p,b}^{k}(n)=n}$ для положительного целое число ${\displaystyle k}$ (куда ${\displaystyle F_{p,b}^{k}}$ это ${\displaystyle k}$th повторять из ${\displaystyle F_{p,b}}$) и образует цикл периода ${\displaystyle k}$. Число Капрекара - это общительное число Капрекара с ${\displaystyle k=1}$, а мирное число Капрекара это общительное число Капрекара с ${\displaystyle k=2}$.

Количество итераций ${\displaystyle i}$ необходимо для ${\displaystyle F_{p,b}^{i}(n)}$ достичь фиксированной точки - это функция Капрекара упорство из ${\displaystyle n}$, и undefined, если он никогда не достигает фиксированной точки.

Есть только конечное число ${\displaystyle p}$-Числа Капрекара и циклы для заданной базы ${\displaystyle b}$, потому что, если ${\displaystyle n=b^{p}+m}$, куда ${\displaystyle m>0}$ тогда

${\displaystyle {\begin{aligned}n^{2}&=(b^{p}+m)^{2}\\&=b^{2p}+2mb^{p}+m^{2}\\&=(b^{p}+2m)b^{p}+m^{2}\\\end{aligned}}}$

и ${\displaystyle \beta =m^{2}}$, ${\displaystyle \alpha =b^{p}+2m}$, и ${\displaystyle F_{p,b}(n)=b^{p}+2m+m^{2}=n+(m^{2}+m)>n}$. Только тогда, когда ${\displaystyle n\leq b^{p}}$ существуют ли числа и циклы Капрекара.

Если ${\displaystyle d}$ есть любой делитель ${\displaystyle p}$, тогда ${\displaystyle n}$ также ${\displaystyle p}$-Номер Капрекара для базы ${\displaystyle b^{p}}$.

В базе ${\displaystyle b=2}$, все даже идеальные числа - числа Капрекара. В более общем смысле, любые числа в форме ${\displaystyle 2^{n}(2^{n+1}-1)}$ или же ${\displaystyle 2^{n}(2^{n+1}+1)}$ для натурального числа ${\displaystyle n}$ числа Капрекара в база 2.

Теоретико-множественное определение и унитарные делители

Мы можем определить множество ${\displaystyle K(N)}$ для данного целого числа ${\displaystyle N}$ как набор целых чисел ${\displaystyle X}$ для которых существуют натуральные числа ${\displaystyle A}$ и ${\displaystyle B}$ удовлетворение Диофантово уравнение^[1]

${\displaystyle X^{2}=AN+B}$, куда ${\displaystyle 0\leq B<N}$

${\displaystyle X=A+B}$

An ${\displaystyle n}$-Номер Капрекара для базы ${\displaystyle b}$ тогда тот, который лежит в множестве ${\displaystyle K(b^{n})}$.

Показан в 2000 г.^[1] что есть биекция между унитарные делители из ${\displaystyle N-1}$ и набор ${\displaystyle K(N)}$ определено выше. Позволять ${\displaystyle {\text{Inv}}(a,c)}$ обозначить мультипликативный обратный из ${\displaystyle a}$ по модулю ${\displaystyle c}$, а именно наименьшее положительное целое число ${\displaystyle m}$ такой, что ${\displaystyle am=1{\bmod {c}}}$, и для каждого унитарного делителя ${\displaystyle d}$ из ${\displaystyle N-1}$ позволять ${\displaystyle e={\frac {N-1}{d}}}$ и ${\displaystyle \zeta (d)=d\ {\text{Inv}}(d,e)}$. Тогда функция ${\displaystyle \zeta }$ является биекцией из множества унитарных делителей ${\displaystyle N-1}$ на съемочную площадку ${\displaystyle K(N)}$. В частности, ряд ${\displaystyle X}$ находится в наборе ${\displaystyle K(N)}$ если и только если ${\displaystyle X=d\ {\text{Inv}}(d,e)}$ для некоторого унитарного делителя ${\displaystyle d}$ из ${\displaystyle N-1}$.

Цифры в ${\displaystyle K(N)}$ встречаются в дополнительных парах, ${\displaystyle X}$ и ${\displaystyle N-X}$. Если ${\displaystyle d}$ является унитарным делителем ${\displaystyle N-1}$ тогда так ${\displaystyle e={\frac {N-1}{d}}}$, и если ${\displaystyle X=d\ {\text{Inv}}(d,e)}$ тогда ${\displaystyle N-X=e\ {\text{Inv}}(e,d)}$.

Числа Капрекара для ${\displaystyle F_{p,b}}$

б = 4k + 3 и п = 2п + 1

Позволять ${\displaystyle k}$ и ${\displaystyle n}$ быть натуральными числами, основание числа ${\displaystyle b=4k+3=2(2k+1)+1}$, и ${\displaystyle p=2n+1}$. Потом:

• ${\displaystyle X_{1}={\frac {b^{p}-1}{2}}=(2k+1)\sum _{i=0}^{p-1}b^{i}}$ является числом Капрекара.

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

Позволять

${\displaystyle {\begin{aligned}X_{1}&={\frac {b^{p}-1}{2}}\\&={\frac {b-1}{2}}\sum _{i=0}^{p-1}b^{i}\\&={\frac {4k+3-1}{2}}\sum _{i=0}^{2n+1-1}b^{i}\\&=(2k+1)\sum _{i=0}^{2n}b^{i}\\\end{aligned}}}$

Потом,

${\displaystyle {\begin{aligned}X_{1}^{2}&=\left({\frac {b^{p}-1}{2}}\right)^{2}\\&={\frac {b^{2p}-2b^{p}+1}{4}}\\&={\frac {b^{p}(b^{p}-2)+1}{4}}\\&={\frac {(4k+3)^{2n+1}(b^{p}-2)+1}{4}}\\&={\frac {(4k+3)^{2n}(b^{p}-2)(4k+4)-(4k+3)^{2n}(b^{p}-2)+1}{4}}\\&={\frac {-(4k+3)^{2n}(b^{p}-2)+1}{4}}+(k+1)(4k+3)^{2n}(b^{p}-2)\\&={\frac {-(4k+3)^{2n-1}(b^{p}-2)(4k+4)+(4k+3)^{2n-1}(b^{p}-2)+1}{4}}+(k+1)b^{2n}(b^{2n+1}-2)\\&={\frac {(4k+3)^{2n-1}(b^{p}-2)+1}{4}}+(k+1)b^{2n}(b^{p}-2)-(k+1)b^{2n-1}(b^{2n+1}-2)\\&={\frac {(4k+3)^{p-2}(b^{p}-2)+1}{4}}+\sum _{i=p-2}^{p-1}(-1)^{i}(k+1)b^{i}(b^{p}-2)\\&={\frac {(4k+3)^{p-2}(b^{p}-2)+1}{4}}+(b^{p}-2)(k+1)\sum _{i=p-2}^{p-1}(-1)^{i}b^{i}\\&={\frac {(4k+3)^{1}(b^{p}-2)+1}{4}}+(b^{p}-2)(k+1)\sum _{i=1}^{p-1}(-1)^{i}b^{i}\\&={\frac {-(b^{p}-2)+1}{4}}+(b^{p}-2)(k+1)\sum _{i=0}^{p-1}(-1)^{i}b^{i}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)+{\frac {-b^{2n+1}+3}{4}}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)+{\frac {-4b^{2n+1}+3b^{2n+1}+3}{4}}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}+{\frac {3b^{2n+1}+3}{4}}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}+{\frac {3(4k+3)^{p-2}+3}{4}}+3(k+1)\sum _{i=p-2}^{p-1}(-1)^{i}b^{i}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}+{\frac {3(4k+3)^{1}+3}{4}}+3(k+1)\sum _{i=1}^{p-1}(-1)^{i}b^{i}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}+{\frac {-3+3}{4}}+3(k+1)\sum _{i=0}^{p-1}(-1)^{i}b^{i}\\&=(b^{p}-2)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)+3(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}\\&=(b^{p}-2+3)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}\\&=(b^{p}+1)(k+1)\left(\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)-b^{p}\\&=(b^{p}+1)\left(-1+(k+1)\sum _{i=0}^{2n}(-1)^{i}b^{i}\right)+1\\&=(b^{p}+1)\left(k+(k+1)\sum _{i=1}^{2n}(-1)^{i}b^{i}\right)+1\\&=(b^{p}+1)\left(k+(k+1)\sum _{i=1}^{n}b^{2i}-b^{2i-1}\right)+1\\&=(b^{p}+1)\left(k+(k+1)\sum _{i=1}^{n}(b-1)b^{2i-1}\right)+1\\&=(b^{p}+1)\left(k+\sum _{i=1}^{n}((k+1)b-k-1)b^{2i-1}\right)+1\\&=(b^{p}+1)\left(k+\sum _{i=1}^{n}(kb+(4k+3)-k-1)b^{2i-1}\right)+1\\&=(b^{p}+1)\left(k+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)+1\\&=b^{p}\left(k+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)+\left(k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)\\\end{aligned}}}$

Два числа ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ находятся

${\displaystyle \beta =X_{1}^{2}{\bmod {b}}^{p}=k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}}$

${\displaystyle \alpha ={\frac {X_{1}^{2}-\beta }{b^{p}}}=k+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}}$

и их сумма

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

Таким образом, ${\displaystyle X_{1}}$ является числом Капрекара.

• ${\displaystyle X_{2}={\frac {b^{p}+1}{2}}=X_{1}+1}$ является числом Капрекара для всех натуральных чисел ${\displaystyle n}$.

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

Позволять

${\displaystyle {\begin{aligned}X_{2}&={\frac {b^{2n+1}+1}{2}}\\&={\frac {b^{2n+1}-1}{2}}+1\\&=X_{1}+1\\\end{aligned}}}$

Потом,

${\displaystyle {\begin{aligned}X_{2}^{2}&=(X_{1}+1)^{2}\\&=X_{1}^{2}+2X_{1}+1\\&=X_{1}^{2}+2X_{1}+1\\&=b^{p}\left(k+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)+\left(k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)+b^{p}-1+1\\&=b^{p}\left(k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)+\left(k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}\right)\\\end{aligned}}}$

Два числа ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ находятся

${\displaystyle \beta =X_{2}^{2}{\bmod {b}}^{p}=k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}}$

${\displaystyle \alpha ={\frac {X_{2}^{2}-\beta }{b^{p}}}=k+1+\sum _{i=1}^{n}(kb+(3k+2))b^{2i-1}}$

и их сумма

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

Таким образом, ${\displaystyle X_{2}}$ является числом Капрекара.

б = м²k + м + 1 и п = мин + 1

Позволять ${\displaystyle m}$, ${\displaystyle k}$, и ${\displaystyle n}$ быть натуральными числами, основание числа ${\displaystyle b=m^{2}k+m+1}$, и мощность ${\displaystyle p=mn+1}$. Потом:

• ${\displaystyle X_{1}={\frac {b^{p}-1}{m}}=(mk+1)\sum _{i=0}^{p-1}b^{i}}$ является числом Капрекара.
• ${\displaystyle X_{2}={\frac {b^{p}+m-1}{m}}=X_{1}+1}$ является числом Капрекара.

б = м²k + м + 1 и п = мин + м - 1

Позволять ${\displaystyle m}$, ${\displaystyle k}$, и ${\displaystyle n}$ быть натуральными числами, основание числа ${\displaystyle b=m^{2}k+m+1}$, и мощность ${\displaystyle p=mn+m-1}$. Потом:

• ${\displaystyle X_{1}={\frac {m(b^{p}-1)}{4}}=(m-1)(mk+1)\sum _{i=0}^{p-1}b^{i}}$ является числом Капрекара.
• ${\displaystyle X_{2}={\frac {mb^{p}+1}{4}}=X_{3}+1}$ является числом Капрекара.

б = м²k + м² - м + 1 и п = мин + 1

Позволять ${\displaystyle m}$, ${\displaystyle k}$, и ${\displaystyle n}$ быть натуральными числами, основание числа ${\displaystyle b=m^{2}k+m^{2}-m+1}$, и мощность ${\displaystyle p=mn+m-1}$. Потом:

• ${\displaystyle X_{1}={\frac {(m-1)(b^{p}-1)}{m}}=(m-1)(mk+1)\sum _{i=0}^{p-1}b^{i}}$ является числом Капрекара.
• ${\displaystyle X_{2}={\frac {(m-1)b^{p}+1}{m}}=X_{1}+1}$ является числом Капрекара.

б = м²k + м² - м + 1 и п = мин + м - 1

Позволять ${\displaystyle m}$, ${\displaystyle k}$, и ${\displaystyle n}$ быть натуральными числами, основание числа ${\displaystyle b=m^{2}k+m^{2}-m+1}$, и мощность ${\displaystyle p=mn+m-1}$. Потом:

• ${\displaystyle X_{1}={\frac {b^{p}-1}{m}}=(mk+1)\sum _{i=0}^{p-1}b^{i}}$ является числом Капрекара.
• ${\displaystyle X_{2}={\frac {b^{p}+m-1}{m}}=X_{3}+1}$ является числом Капрекара.

Числа Капрекара и циклы ${\displaystyle F_{p,b}}$ для конкретных ${\displaystyle p}$, ${\displaystyle b}$

Все числа в базе ${\displaystyle b}$.

Основание ${\displaystyle b}$	Мощность ${\displaystyle p}$	Нетривиальные числа Капрекара ${\displaystyle n\neq 0}$, ${\displaystyle n\neq 1}$	Циклы
2	1	10	${\displaystyle \varnothing }$
3	1	2, 10	${\displaystyle \varnothing }$
4	1	3, 10	${\displaystyle \varnothing }$
5	1	4, 5, 10	${\displaystyle \varnothing }$
6	1	5, 6, 10	${\displaystyle \varnothing }$
7	1	3, 4, 6, 10	${\displaystyle \varnothing }$
8	1	7, 10	2 → 4 → 2
9	1	8, 10	${\displaystyle \varnothing }$
10	1	9, 10	${\displaystyle \varnothing }$
11	1	5, 6, А, 10	${\displaystyle \varnothing }$
12	1	Б, 10	${\displaystyle \varnothing }$
13	1	4, 9, С, 10	${\displaystyle \varnothing }$
14	1	Д, 10	${\displaystyle \varnothing }$
15	1	7, 8, E, 10	2 → 4 → 2 9 → B → 9
16	1	6, А, Ж, 10	${\displaystyle \varnothing }$
2	2	11	${\displaystyle \varnothing }$
3	2	22, 100	${\displaystyle \varnothing }$
4	2	12, 22, 33, 100	${\displaystyle \varnothing }$
5	2	14, 31, 44, 100	${\displaystyle \varnothing }$
6	2	23, 33, 55, 100	15 → 24 → 15 41 → 50 → 41
7	2	22, 45, 66, 100	${\displaystyle \varnothing }$
8	2	34, 44, 77, 100	4 → 20 → 4 11 → 22 → 11 45 → 56 → 45
2	3	111, 1000	10 → 100 → 10
3	3	111, 112, 222, 1000	10 → 100 → 10
2	4	110, 1010, 1111, 10000	${\displaystyle \varnothing }$
3	4	121, 2102, 2222, 10000	${\displaystyle \varnothing }$
2	5	11111, 100000	10 → 100 → 10000 → 1000 → 10 111 → 10010 → 1110 → 1010 → 111
3	5	11111, 22222, 100000	10 → 100 → 10000 → 1000 → 10
2	6	11100, 100100, 111111, 1000000	100 → 10000 → 100 1001 → 10010 → 1001 100101 → 101110 → 100101
3	6	10220, 20021, 101010, 121220, 202202, 212010, 222222, 1000000	100 → 10000 → 100 122012 → 201212 → 122012
2	7	1111111, 10000000	10 → 100 → 10000 → 10 1000 → 1000000 → 100000 → 1000 100110 → 101111 → 110010 → 1010111 → 1001100 → 111101 → 100110
3	7	1111111, 1111112, 2222222, 10000000	10 → 100 → 10000 → 10 1000 → 1000000 → 100000 → 1000 1111121 → 1111211 → 1121111 → 1111121
2	8	1010101, 1111000, 10001000, 10101011, 11001101, 11111111, 100000000	${\displaystyle \varnothing }$
3	8	2012021, 10121020, 12101210, 21121001, 20210202, 22222222, 100000000	${\displaystyle \varnothing }$
2	9	10010011, 101101101, 111111111, 1000000000	10 → 100 → 10000 → 100000000 → 10000000 → 100000 → 10 1000 → 1000000 → 1000 10011010 → 11010010 → 10011010

Расширение до отрицательных целых чисел

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

Упражнение по программированию

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

def капрекарф(Икс: int, п: int, б: int) -> int:    бета = пау(Икс, 2) % пау(б, п)    альфа = (пау(Икс, 2) - бета) // пау(б, п)    y = альфа + бета    возвращаться ydef kaprekarf_cycle(Икс: int, п: int, б: int) -> Список[int]:    видимый = []    пока Икс < пау(б, п) и Икс нет в видимый:        видимый.добавить(Икс)        Икс = капрекарф(Икс, п, б)    если Икс > пау(б, п):        возвращаться []    цикл = []    пока Икс нет в цикл:        цикл.добавить(Икс)        Икс = капрекарф(Икс, п, б)    возвращаться цикл

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

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

Примечания

1. Яннуччи (2000 )

Рекомендации

• Д. Р. Капрекар (1980–1981). «О числах Капрекара». Журнал развлекательной математики. 13: 81–82.
• М. Чарош (1981–1982). «Некоторые приложения изгнания 999 ...». Журнал развлекательной математики. 14: 111–118.
• Ианнуччи, Дуглас Э. (2000). «Числа Капрекара». Журнал целочисленных последовательностей. 3: 00.1.2.