Kaprekar Sequence

Description of the problem

I was reading a blog post on the Kaprekar constant. I will do the same experiment in Common Lisp. Here is the description of the experiment:

Take any integer. Write it in a base. Sort the digits from largest to smallest. Sort it again, this time from smallest to largest. Take the difference. Repeat until you get a cycle.

An implementation

I will need two functions: one to convert a number into digits, and another to convert a list of digits into an integer. Simple enough:

(defun int-to-list (n base &optional acc)
  (multiple-value-bind (a b)
      (floor n base)
    (if (zerop a)
        (cons b acc)
        (int-to-list a base (cons b acc)))))

(defun list-to-int (xs base &optional (acc 0))
  (if (null xs)
      acc
      (list-to-int (cdr xs) base (+ (* acc base) (car xs)))))

INT-TO-LIST
LIST-TO-INT

I know, I know. Common lisp has a radix clause, but these functions work with any base not just for radixes 2 to 32.

Here is my implementation:

(defun kaprekar (n base &optional acc)
  (let* ((xs (int-to-list n base))
         (next (- (list-to-int (sort (copy-list xs) #'>) base)
                  (list-to-int (sort (copy-list xs) #'<) base))))
    (if (member next acc :test #'equal)
        (reverse (cons next acc))
        (kaprekar next base (cons n acc)))))

KAPREKAR

If you wonder why I used copy-list you should know that sort in common lisp is destructive. Yeah, fun isn’t it? Let us test on the original Kaprekar constant:

(kaprekar 1234 10)

(1234 3087 8352 6174 6174)

Note that all numbers are displayed in the decimal notation even though the sequence is computed using a different basis. Here is a large example

(mapcar (lambda (x) (format nil "~X" x)) (kaprekar 293847923129380187 16))

(413F521141CED5B EDCB920FED64322 FCCBA84FA754331 EC98752FCA87632
 DC97420FEDB8633 FCAA851FDA75531 EEA7552FCAA8512 ECC7552FCAA8332
 DC99752FCA86633 DA97431FDCB8653 EAA8641FDB97552 EC96541FDBA9632
 ECA8642FCB97532 DC98641FDB97633 EAA8531FDCA7552 ECA7552FCAA8532
 DC97552FCAA8633 DA97541FDBA8653 EA96541FDBA9652 EC96542FCBA9632
 DC98642FCB97633 DA98531FDCA7653 EAA7541FDBA8552 EC96552FCAA9632
 DC97542FCBA8633 DA98641FDB97653 ECA8642FCB97532)

Why does this work?

Well kids, have you heard the pigeonhole principle? There is a hard guarantee on the largest integer one is going to get from this sequence. One can not fit an infinite sequence of integers into a finite interval of integers. So, pigeonhole principle says there must be a cycle.