Algoritmo di Kaprekar
 
 
L'algoritmo di Kaprekar é stato scoperto da D.R. Kaprecar nel 1949 relativamente a numeri di 4 cifre e può essere generalizzato a numeri di k cifre.
Dato un intero n l'algoritmo prevede di ordinare le cifre in ordine crescente (n' ) e in ordine decrescente (n'' ). Quindi si calcola N(n) = n' - n'' e si itera il procedimento.
L'algoritmo raggiunge il valore 0, una costante oppure termina in un ciclo in relazione al valore di n e al numero k delle sue cifre.
Nel caso di un numero n = ab di 2 cifre dove, per comodità consideriamo i numeri costituiti dalla sola cifra delle unità come preceduti da uno zero ( 5 = 05 ) si ottiene:
n' = ab = 10a + b  con a > b,  n'' = ba = 10b + a da cui N(n) = n' - n''  = 9(a - b).
Se a = b  N(n) = 0 e l'algoritmo si arresta; se a e b sono distinti dopo la prima iterazione si ottiene un numero di due cifre multiplo di 9. I numeri aventi queste caratteristiche sono 10 e possono essere raggruppati a coppie in modo tale che la loro somma risulti 99: (90,09), (81,18), (63,36), (72,27), (54,45). In ogni coppia un numero si ottiene permutando le cifre dell'altro ed iterando la procedura si osserva che l'algoritmo entra in un ciclo.
Se n = abc ha tre cifre, a > b > c,  allora n' = abc = 100a+10b+c e 
n'' = cba = 100c+10b+a  da cui N(n) = n'-n'' = 99(a - c). Per a = c  N(n) = 0 e l'algoritmo si arresta. In caso contrario N(n) é un numero di tre cifre multiplo di 99. I numeri che soddisfano questa condizione sono dieci e possono essere raggruppati a coppie; in ogni coppia la somma vale 1089 e un numero si ottiene dall'altro permutandone le cifre: (990,099), (891,198), (792,297), (693,396), (594,495). Iterando, dopo un certo numero di passi, l'algoritmo si arresta al valore 495 in quanto N(495) = 495.

Si può osservare come i dieci numeri trovati si possono scrivere tutti nella forma

n = 100a + 90 + (9 - a) = 99(a+1).

  • Se a = 5, 6, 7, 8, 9 allora n' = 100(9 - a) + 10a + 9,  n'' = 900 + 10a + (9 - a) quindi N(n) = 99a ed iterando la successione degli N(n) assume i valori 99(a - 1), ... , 99×5 = 495.
  • Se  a = 0, 1, 2, 3, 4 allora n' = 100a + 10(9 - a) + 9,  n'' = 900 + 10(9 - a) + a quindi N(n) = 99(9 - a) e si torna ai numeri considerati nel caso precedente.