En teoría de números , la rutina de Kaprekar es un algoritmo iterativo que, con cada iteración, toma un número natural en una base numérica dada , crea dos nuevos números clasificando los dígitos de su número en orden descendente y ascendente, y resta el segundo del primero. para obtener el número natural para la siguiente iteración. Lleva el nombre de su inventor, el matemático indio D. R. Kaprekar .
Definición y propiedades
El algoritmo es como sigue:
- Elija cualquier número natural en una base numérica dada . Este es el primer número de la secuencia.
- Crea un nuevo número por clasificación de los dígitos de en orden descendente, y otro número nuevo ordenando los dígitos de en orden ascendente. Estos números pueden tener ceros a la izquierda, que se descartan (o, alternativamente, se conservan). Sustraer para producir el siguiente número de la secuencia.
- Repita el paso 2.
La secuencia se llama secuencia de Kaprekar y la función es el mapeo de Kaprekar . Algunos números se asignan a sí mismos; estos son los puntos fijos del mapeo de Kaprekar, [1] y se denominan constantes de Kaprekar . Zero es una constante de Kaprekar para todas las bases, por lo que se llama constante de Kaprekar trivial . Todas las demás constantes de Kaprekar son constantes de Kaprekar no triviales .
Por ejemplo, en base 10 , comenzando con 3524,
con 6174 como constante de Kaprekar.
Todas las secuencias de Kaprekar alcanzarán uno de estos puntos fijos o darán como resultado un ciclo repetitivo. De cualquier manera, el resultado final se alcanza en un número bastante pequeño de pasos.
Tenga en cuenta que los números y tienen la misma suma de dígitos y, por lo tanto, el mismo resto módulo. Por lo tanto, cada número en una secuencia de Kaprekar de base números (que no sean posiblemente el primero) es un múltiplo de .
Cuando se retienen los ceros iniciales, solo los repdigitos conducen a la constante trivial de Kaprekar.
Familias de las constantes de Kaprekar
En base 4 , se puede mostrar fácilmente que todos los números de la forma 3021, 310221, 31102221, 3 ... 111 ... 02 ... 222 ... 1 (donde la longitud de la secuencia "1" y la la longitud de la secuencia "2" es la misma) son puntos fijos del mapeo de Kaprekar.
En base 10 , se puede mostrar fácilmente que todos los números de la forma 6174, 631764, 63317664, 6 ... 333 ... 17 ... 666 ... 4 (donde la longitud de la secuencia "3" y la longitud de la secuencia "6" son los mismos) son puntos fijos del mapeo de Kaprekar.
b = 2 k
Se puede demostrar que todos los números naturales
son puntos fijos del mapeo de Kaprekar en una base uniforme para todos los números naturales .
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 | 5B6, 65BB56, 665BBB556, 6665BBBB5556 ... |
7 | 14 | 6D7, 76DD67, 776DDD667, 7776DDDD6667 ... |
8 | dieciséis | 7F8, 87FF78, 887FFF778, 8887FFFF7778 ... |
9 | 18 | 8H9, 98HH89, 998HHH889, 9998HHHH8889 ... |
Constantes y ciclos de Kaprekar del mapeo de Kaprekar para base b específica
Todos los números se expresan en base , usando A − Z para representar valores de dígitos del 10 al 35.
Base | Longitud de dígitos | Constantes de Kaprekar no triviales (distintas de cero) | Ciclos |
---|---|---|---|
2 | 2 | 01 [nota 1] | |
3 | 011 [nota 1] | ||
4 | 0111, [nota 1] 1001 | ||
5 | 01111, [nota 1] 10101 | ||
6 | 011111, [nota 1] 101101, 110001 | ||
7 | 0111111, [nota 1] 1011101, 1101001 | ||
8 | 01111111, [nota 1] 10111101, 11011001, 11100001 | ||
9 | 011111111, [nota 1] 101111101, 110111001, 111010001 | ||
3 | 2 | ||
3 | 022 → 121 → 022 [nota 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 | |
4 | 2 | 03 → 21 → 03 [nota 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 | ||
5 | 2 | 13 | |
3 | 143 → 242 → 143 | ||
4 | 3032 | ||
6 | 2 | 05 → 41 → 23 → 05 [nota 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 | |
7 | 2 | ||
3 | 264 → 363 → 264 | ||
4 | 3054 → 5052 → 5232 → 3054 | ||
8 | 2 | 25 | 07 → 61 → 43 → 07 [nota 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 | |
9 | 2 | 17 → 53 → 17 | |
3 | 385 → 484 → 385 | ||
4 | 3076 → 7252 → 5254 → 3076 5074 → 7072 → 7432 → 5074 | ||
10 [2] | 2 | 09 → 81 → 63 → 27 → 45 → 09 [nota 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 | |
11 | 2 | 37 | |
3 | 4A6 → 5A5 → 4A6 | ||
4 | 3098 → 9452 → 7094 → 9272 → 7454 → 3098 5096 → 9092 → 9632 → 7274 → 5276 → 5096 | ||
12 | 2 | 0B → A1 → 83 → 47 → 29 → 65 → 0B [nota 1] | |
3 | 5B6 | ||
4 | 3BB8 → 8284 → 6376 → 3BB8 4198 → 8374 → 5287 → 6196 → 7BB4 → 7375 → 4198 | ||
5 | 83B74 | 64B66 → 6BBB5 → 64B66 | |
6 | 65BB56 | 420A98 → A73742 → 842874 → 642876 → 62BB86 → 951963 → 860A54 → A40A72 → A82832 → 864654 → 420A98 | |
7 | 962B853 | 841B974 → A53B762 → 971B943 → A64B652 → 960BA53 → B73B741 → A82B832 → 984B633 → 863B754 → 841B974 | |
8 | 873BB744, A850A632 | 4210AA98 → A9737422 → 87428744 → 64328876 → 652BB866 → 961BB953 → A8428732 → 86528654 → 6410AA76 → A92BB822 → 9980A323 → A7646542 → 8320A984 → A7537642 → 8430A874 → 8630A874 A54728832 A | |
13 | 2 | 1B → 93 → 57 → 1B | |
3 | 5C7 → 6C6 → 5C7 | ||
14 | 2 | 49 | 2B → 85 → 2B 0D → C1 → A3 → 67 → 0D [nota 1] |
3 | 6D7 | ||
15 | 2 | ||
3 | 6E8 → 7E7 → 6E8 | ||
16 [3] | 2 | 2D → A5 → 4B → 69 → 2D 0F → E1 → C3 → 87 → 0F [nota 1] | |
3 | 7F8 | ||
4 | 3FFC → C2C4 → A776 → 3FFC A596 → 52CB → A596 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 |
- ^ a b c d e f g h i j k l m n o p Se conservaron los ceros iniciales.
Constantes de Kaprekar en base 10
Números de cuatro dígitos de longitud
En 1949, el DR Kaprekar descubrió [4] que si el proceso anterior se aplica a números de base 10 de 4 dígitos, la secuencia resultante casi siempre convergerá al valor 6174 en un máximo de 8 iteraciones, excepto por un pequeño conjunto de números iniciales que convergen. en lugar de 0. El número 6174 es la primera constante de Kaprekar que se descubre y, por lo tanto, a veces se conoce como constante de Kaprekar . [5] [6] [7]
El conjunto de números que convergen a cero depende de si se retienen los ceros iniciales (la formulación habitual) o se descartan (como en la formulación original de Kaprekar).
En la formulación habitual, hay 77 números de cuatro dígitos que convergen a cero, [8] por ejemplo 2111. Sin embargo, en la formulación original de Kaprekar se retienen los ceros iniciales y solo repdigits como 1111 o 2222 se asignan a cero. Este contraste se ilustra a continuación:
descartar ceros a la izquierda | retener ceros iniciales |
---|---|
2111-1112 = | 2111-1112 = 0999 |
A continuación se muestra un diagrama de flujo. Los ceros iniciales se conservan, sin embargo, la única diferencia cuando se descartan los ceros iniciales es que en lugar de 0999 conectando con 8991, obtenemos 999 conectando con 0.
Números de tres dígitos de longitud
Si la rutina de Kaprekar se aplica a números de 3 dígitos en base 10, la secuencia resultante casi siempre convergerá al valor 495 en un máximo de 6 iteraciones, excepto por un pequeño conjunto de números iniciales que convergen en su lugar a 0. [5]
El conjunto de números que convergen a cero depende de si los ceros iniciales se descartan (la formulación habitual) o se retienen (como en la formulación original de Kaprekar). En la formulación habitual, hay 60 números de tres dígitos que convergen a cero, [9] por ejemplo 211. Sin embargo, en la formulación original de Kaprekar se retienen los ceros a la izquierda, y sólo repdigits como 111 o 222 se asignan a cero.
A continuación se muestra un diagrama de flujo. Los ceros iniciales se conservan, sin embargo, la única diferencia cuando se descartan los ceros iniciales es que en lugar de 099 conectando con 891, obtenemos 99 conectando con 0.
Otras longitudes de dígitos
Para longitudes de dígitos que no sean tres o cuatro (en base 10), la rutina puede terminar en uno de varios puntos fijos o puede ingresar uno de varios ciclos en su lugar, dependiendo del valor inicial de la secuencia. [5] Consulte la tabla en la sección anterior para conocer los puntos fijos y los ciclos de base 10 .
El número de ciclos aumenta rápidamente con longitudes de dígitos más grandes, y todos, excepto un pequeño puñado de estos ciclos, tienen una longitud de tres. Por ejemplo, para números de 20 dígitos en base 10, hay catorce constantes (ciclos de longitud uno) y noventa y seis ciclos de longitud mayor que uno, todos menos dos de los cuales son de longitud tres. Las longitudes de dígitos impares producen menos resultados finales diferentes que las longitudes de dígitos pares. [10] [11]
Ejemplo de programación
El siguiente ejemplo implementa el mapeo de Kaprekar descrito en la definición anterior para buscar las constantes y ciclos de Kaprekar en Python .
Ceros iniciales descartados
def get_digits ( x , b ): dígitos = [] mientras que x > 0 : dígitos . añadir ( x % b ) x = x // b devolver dígitos def form_number ( digits , b ): result = 0 for i in range ( 0 , len ( digits )): result = result * b + digits [ i ] return resultdef kaprekar_map ( x , b ): descendente = form_number ( ordenado ( get_digits ( x , b ), reverse = True ), b ) ascendente = form_number ( ordenado ( get_digits ( x , b )), b ) retorno descendente - ascendente def kaprekar_cycle ( x , b ): x = int ( str ( x ), b ) visto = [] mientras que x no está en visto : visto . añadir ( x ) x = kaprekar_map ( x , b ) ciclo = [] mientras que x no está en ciclo : ciclo . append ( x ) x = kaprekar_map ( x , b ) ciclo de retorno
Se conservan los ceros a la izquierda
def digit_count ( x , b ): count = 0 while x > 0 : count = count + 1 x = x // b return count def get_digits ( x , b , init_k ): k = digit_count ( x , b ) dígitos = [] mientras que x > 0 : dígitos . añadir ( x % b ) x = x // b para i en el rango ( k , init_k ): dígitos . añadir ( 0 ) dígitos de retorno def form_number ( digits , b ): result = 0 for i in range ( 0 , len ( digits )): result = result * b + digits [ i ] return result def kaprekar_map ( x , b , init_k ): descendente = número_de_forma ( ordenado ( get_digits ( x , b , init_k ), reverse = True ), b ) ascendente = número_de_forma ( ordenado ( get_digits ( x , b , init_k )), b ) volver descendente - ascendente def kaprekar_cycle ( x , b ): x = int ( str ( x ), b ) init_k = digit_count ( x , b ) visto = [] mientras que x no está en visto : visto . añadir ( x ) x = kaprekar_map ( x , b , init_k ) ciclo = [] mientras que x no está en ciclo : ciclo . append ( x ) x = kaprekar_map ( x , b , init_k ) ciclo de retorno
Ver también
- Dinámica aritmética
- Número de Dudeney
- Factorion
- Feliz numero
- Número de Kaprekar
- Número de Meertens
- Número narcisista
- Perfecta invariante de dígito a dígito
- Invariante digital perfecto
- Número de producto suma
- Algoritmo de clasificación
Referencias
- ^ (secuencia A099009 en la OEIS )
- ^ [1]
- ^ [2]
- ^ Kaprekar DR (1955). "Una propiedad interesante del número 6174". Scripta Mathematica . 15 : 244–245.
- ^ a b c Weisstein, Eric W. "Rutina de Kaprekar" . MathWorld .
- ^ Yutaka Nishiyama , misterioso número 6174
- ^ Kaprekar DR (1980). "Sobre los números de Kaprekar". Revista de matemáticas recreativas . 13 (2): 81–82.
- ^ (secuencia A069746 en la OEIS )
- ^ (secuencia A090429 en la OEIS )
- ^ [3]
- ^ [4]
enlaces externos
- Bowley, Rover. "6174 es la constante de Kaprekar" . Numberphile . Universidad de Nottingham : Brady Haran . Archivado desde el original el 23 de agosto de 2017 . Consultado el 1 de abril de 2013 .
- Código de muestra (Perl) para caminar cualquier número de cuatro dígitos a la constante de Kaprekar