Sunday, 26 January 2014

Kaprekar's Constant in Excel and Excelsior

The integer 6174 is also known as Kaprekar's constant. According to Wikipedia, it is notable for the following property:

  1. Take any four-digit number which contains at least two different digits (so not 1111, 2222, and so on). Leading zeros are allowed.
  2. Arrange the digits in ascending and then in descending order to get two four-digit numbers, adding leading zeros if necessary.
  3. Subtract the smaller number from the bigger number.
  4. Go back to step 2.
The above process, known as Kaprekar's routine, will always reach its fixed point, 6174, in at most 7 iterations.

I'm going to use it as an example. In my last posting, about literate programming and my science-fiction generator spreadsheet, I explained that I made the spreadsheet by writing a program in a language I call Excelsior, and compiling this to Excel. I want now to demonstrate Excelsior, by using it to write a Kaprekar-constant spreadsheet.

I was inspired by Excel developer Jeff Lutes, who posted to the Microsoft Excel Developers List in July 2012, asking for an elegant way to calculate Kaprekar's constant in Excel, preferably without using Visual Basic. I tried this in Excelsior, and generated this spreadsheet. Here below is the Excelsior program, in the HTML documentation format output by Literate Excelsior. Program text is on a grey background: the rest is commentary. To use the spreadsheet, type a four-digit number into cell A2. You can also see the program here, which may be better if the blog styling interferes with this posting.

Program structure

I'm laying the spreadsheet out in columns. Each row corresponds to one iteration, and I shall define a constant called max_iterations to give the depth of each column:

type column = 1:max_iterations.

constant max_iterations = 20.
I hope this will be big enough.

Briefly stated, the columns hold the following tables:

  • the original number;
  • its digits, calculated by converting it to text and extracting a substring;
  • the digits in ascending order, calculated by using the function SMALL, which returns the k-th smallest value in an array or range;
  • the number in ascending order, calculated by concatenating these;
  • the number in descending order;
  • their difference. I feed this back into the first column.

The tables


number[1] holds the original number. number[n], where n>1, contains the absolute value of difference calculated in the n-1'th iteration. I made it absolute because I hit problems with the minus sign otherwise.

table number : column -> general.

number[ 1 ] = 4973.
number[ n>1 ] = abs( difference[ n-1 ] ).


number_as_text[n] is number[n] converted to text.

table number_as_text : column -> text.

number_as_text[ n ] = text( number[n], "0000" ).


digits is a four-column table. The d'th column holds the d'th digit of number.

type digit_range = 1:4.

table digits : digit_range column -> general.

digits[ d, n ] = value( mid( number_as_text[n], d, 1 ) ).


digits_ascending is also a four-column table. The d'th column holds the d smallest digit.

table digits_ascending : digit_range column -> general.

digits_ascending[ d, n ] = small( digits[all,n], d ).


number_ascending[n] concatenates the digits from digits_ascending[n], giving us them as a single number.

table number_ascending : column -> general.

number_ascending[ n ] =
  value( digits_ascending[ 1, n ] &
         digits_ascending[ 2, n ] &
         digits_ascending[ 3, n ] &
         digits_ascending[ 4, n ]


Similarly, number_descending[n] is a single number with the digits in descending order.

table number_descending : column -> general.

number_descending[ n ] =
  value( digits_ascending[ 4, n ] &
         digits_ascending[ 3, n ] &
         digits_ascending[ 2, n ] &
         digits_ascending[ 1, n ]


difference[n] is the difference between number_ascending[n] and number_descending[n].

table difference : column -> general.

difference[ n ] = number_ascending[ n ] - number_descending[ n ].


This arranges the tables from left to right as named below, and puts an automatically-generated heading above each giving its name.

layout( 'Sheet 1'
      , rows( heading
            , row( number as y
                 , number_as_text as y
                 , digits as xy
                 , digits_ascending as xy
                 , number_ascending as y
                 , number_descending as y
                 , difference as y

And that is how to calculate 6174 in Excel. It's the most useless integer in the mathematical universe, but at least the calculations are easy to read.

No comments:

Post a Comment