The Kaprekar process

 

(Best viewed on larger screens)

What is it?

Given the number of digits to maintain, and a starting positive integer i with no more than that many digits, the repettitive process continues:

1. Form the integer i1 from the (zero-extended) digits of i sorted from largest digit to smallest.
2. Form the integer i2 from the (zero-extended) digits of i sorted from smallest digit to largest.
3. Form a new, replacement i by subtracting the smallest from the largest: i = i1 - i2.

If any new i has already been seen then this latest i is termed the Kaprekar constant formed from the initial i and digits

Details

Zero extension

If we have i = 21; digits = 4 then zero extension to the given number of digits means that if the integer is normally written with fewer digits then extra zeroes are added as padding to the right of the number to fill in the right number of digits. i of 21 is treated as 0021 the hundreds and thousands digits are given as zero.

When sorted, i1 = int('2100') and i2 = int('0012') resulting in a new i = 2100 - 12 = 2088

i = 21; digits = 4
print(f"Zero-extend {i = } by {digits = } gives: {i = :0{digits}}")

Zero-extend i = 21 by digits = 4 gives: i = 0021

Sort

If we consider the digits of a number as characters then the normal Python sort returns the digits from smallest to largest, i.e. for i2.

i_l2r = ''.join(sorted(f"{i:0{digits}}"))  # digits sorted Left-to-Right

print(f"{i = }\nZero-extended and sorted digits for i2:", i_l2r)

print("Those same digits reverse-sorted for i1:", i_l2r[::-1])

new_i = int(i_l2r[::-1]) - int(i_l2r)

print(f"{new_i = }")

i = 21
Zero-extended and sorted digits for i2: 0012
Those same digits reverse-sorted for i1: 2100
new_i = 2088

The kaprekar constant

An Indian mathematician, Kaprekar, found that with four digits, starting with any number produced either a final value of

• 0, Zero for starting numbers that were palindromes. For example if i = 1111 then i1 == i2 == 1111 and the new i = i1 - i2 = 0.
• Or 6174 for all other numbers of four or less digits.

6174 is known as the Kaprekar constant.

Exploring the Kaprekar process

Now some code to find constants for differing numbers of digits, as well as an indication of how many starting integers in the range of that many digits loop on a particular constant.

from collections import defaultdict
def kaprekar1(digits: int=4):
    "kaprekar function."
    base = 10
    konstant2nums = defaultdict(int)  # how many times the constant is seen
    for i in range(base**digits):     # All ints expressable in digits
        i_start = i
        seen = set()  # numbers produced by the process so far
        while i not in seen:
            seen.add(i)
            i_l2r = ''.join(sorted(f"{i:0{digits}}"))  # digits sorted L-to-R
            i = int(i_l2r[::-1]) - int(i_l2r)  # new i
        konstant2nums[i] += 1  # this constant i, seen one more time from this i_start
    return dict(konstant2nums)
kaprekar1(4)

{0: 10, 6174: 9990}

That show that we get the constant 0 ten times for i = 0, 1111, ..., 9999.

We get the Kaprekar constant of 6174 for all other starting, foru-digit numbers.

Two digits

kaprekar1(2)

{0: 10, 9: 26, 63: 22, 27: 26, 45: 14, 81: 2}

With two digits we get the obvious constant 0 and five others: 9, 27, 45, 63, 81

No longer interested in constant frequencies

I'm only really interested in the keys of the returned dict so:

def kaprekar2(digits: int=4):
    "kaprekar function."
    base = 10
    konstant2nums = defaultdict(int)  # how many times the constant is seen
    for i in range(base**digits):     # All ints expressable in digits
        i_start = i
        seen = set()  # numbers produced by the process so far
        while i not in seen:
            seen.add(i)
            i_l2r = ''.join(sorted(f"{i:0{digits}}"))  # digits sorted L-to-R
            i = int(i_l2r[::-1]) - int(i_l2r)  # new i
        konstant2nums[i] += 1  # this constant i, seen one more time from this i_start
    return sorted(konstant2nums)  # Just the keys
kaprekar2(2)

[0, 9, 27, 45, 63, 81]

Optimisations

The code takes a minute to produce kaprekar1(6), and looking at the code I chuck away what is seen for every i_start.
What if a later i_start has an i that visits something seen for a previous i_start?

In this next version I keep track of everything seen earlier in seen2 which automatically maps to the ending constant found for all numbers of seen

def kaprekar3(digits: int=4):
    "Optimised"
    konstants = set()
    seen2 = {}  # Maps iterated i to final constant across all initial i's
    for i in range(10**digits):
        i_start = i
        seen = set()
        while i not in seen and i not in seen2:  # Short-cut via earlier i_starts too.
            seen.add(i)
            i_l2r = ''.join(sorted(f"{i:0{digits}}"))
            i = int(i_l2r[::-1]) - int(i_l2r)
        if i in seen2:
            i = seen2[i]  # then this was its final constant
        for s in seen:
            seen2[s] = i  # Accumulate data from this i_start
        konstants.add(i)
    return sorted(konstants)
kaprekar3(2)

[0, 9]

Whoa! different results

kaprekar2(2) gave [0, 9, 27, 45, 63, 81] ?

Lets work through one of the extra results for the digits = 2 ones a bit more:

81 -> 81 - 18 = 63
63 -> 63 - 36 = 27
27 -> 72 - 27 = 45
45 -> 54 - 45 =  9

So kaprekar1 and 2 did not finish their reductions! All the extra results reduce to the 9 given in kaprekar3(2).

Results for more digits

for d in range(7):
    print()
    %time print(f"{d = }; {kaprekar3(d) = }")

d = 0; kaprekar3(d) = [0]
CPU times: total: 0 ns
Wall time: 0 ns

d = 1; kaprekar3(d) = [0]
CPU times: total: 0 ns
Wall time: 0 ns

d = 2; kaprekar3(d) = [0, 9]
CPU times: total: 0 ns
Wall time: 0 ns

d = 3; kaprekar3(d) = [0, 495]
CPU times: total: 0 ns
Wall time: 4.99 ms

d = 4; kaprekar3(d) = [0, 6174]
CPU times: total: 46.9 ms
Wall time: 50 ms

d = 5; kaprekar3(d) = [0, 53955, 63954, 74943]
CPU times: total: 438 ms
Wall time: 444 ms

d = 6; kaprekar3(d) = [0, 549945, 631764, 851742]
CPU times: total: 4.91 s
Wall time: 4.93 s

Lets check those digits = 5 multiple values don't collapse to other constants.

def test_multiple_results(kaprekar_func, digits=4):
    print(f"TESTING {kaprekar_func.__name__}({digits}) KONSTANTS", end='')
    stated_konstants = kaprekar_func(digits)
    konstants = set(stated_konstants)
    for i in stated_konstants:
        i_start = i
        seen = set()
        # Reduce, visibly
        print(f"\n  Reduce konstant {i}:")
        while i not in seen:
            seen.add(i)
            i_l2r = ''.join(sorted(f"{i:0{digits}}"))
            i_new = (i1:=int(i_l2r[::-1])) - (i2:=int(i_l2r))
            print(f"    {i:0{digits}} -> {i1:0{digits}} - {i2:0{digits}} = {i_new:0{digits}}")
            i = i_new
        if not seen.intersection(konstants):
            print("  ERROR! A new constant produced?!?")
        elif i in konstants:
            if i != i_start:
                print("  NOTE OK. One of the reduction intermediates occurs in the original konstants.")
            else:
                print("  NOTE OK. Reduces to itself.")
        elif seen.intersection(konstants):
            print("  NOTE OK. One of the reduction intermediates occurs in the original konstants.")
        else:
            print("  ERROR! A new constant produced!")
test_multiple_results(kaprekar3, 5)

TESTING kaprekar3(5) KONSTANTS
  Reduce konstant 0:
    00000 -> 00000 - 00000 = 00000
  NOTE OK. Reduces to itself.

  Reduce konstant 53955:
    53955 -> 95553 - 35559 = 59994
    59994 -> 99954 - 45999 = 53955
  NOTE OK. Reduces to itself.

  Reduce konstant 63954:
    63954 -> 96543 - 34569 = 61974
    61974 -> 97641 - 14679 = 82962
    82962 -> 98622 - 22689 = 75933
    75933 -> 97533 - 33579 = 63954
  NOTE OK. Reduces to itself.

  Reduce konstant 74943:
    74943 -> 97443 - 34479 = 62964
    62964 -> 96642 - 24669 = 71973
    71973 -> 97731 - 13779 = 83952
    83952 -> 98532 - 23589 = 74943
  NOTE OK. Reduces to itself.

test_multiple_results(kaprekar3, 6)

TESTING kaprekar3(6) KONSTANTS
  Reduce konstant 0:
    000000 -> 000000 - 000000 = 000000
  NOTE OK. Reduces to itself.

  Reduce konstant 549945:
    549945 -> 995544 - 445599 = 549945
  NOTE OK. Reduces to itself.

  Reduce konstant 631764:
    631764 -> 766431 - 134667 = 631764
  NOTE OK. Reduces to itself.

  Reduce konstant 851742:
    851742 -> 875421 - 124578 = 750843
    750843 -> 875430 - 034578 = 840852
    840852 -> 885420 - 024588 = 860832
    860832 -> 886320 - 023688 = 862632
    862632 -> 866322 - 223668 = 642654
    642654 -> 665442 - 244566 = 420876
    420876 -> 876420 - 024678 = 851742
  NOTE OK. Reduces to itself.

The konstants from kaprekar3 are legit.

END.