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:
- Form the integer
i1from the (zero-extended) digits ofisorted from largest digit to smallest. - Form the integer
i2from the (zero-extended) digits ofisorted from smallest digit to largest. - Form a new, replacement
iby 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 = 4print(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 = 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 ifi = 1111theni1 == i2 == 1111and the newi = i1 - i2 = 0.- Or
6174for 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.
No comments:
Post a Comment