Happy Numbers

Description of the problem

Assume we have a decimal integer \(N\) of the form \((a_k a_{k-1} \ldots a_1 a_0)\). Now consider the sum \[ \sum_{i=0}^k a_i^2 \] in decimal again. Iterate recursively. Such numbers are called Happy Numbers.

Today, I am going to see if numbers create cycles in this iteration. Plus, I will do this in an arbitrary radix instead of just in decimal.

Implementation

First, I will need to generate the list of digits in an arbitrary radix. Common Lisp has excellent support for displaying numbers in commonly used radices, even for roman numerals by the way.

(defun digits (n radix &optional carry)
   (if (zerop n)
       (reverse carry)
       (multiple-value-bind
           (q r) (floor n radix)
         (digits q radix (cons r carry)))))
DIGITS

Now, we go for the squaring the digits:

(defun happy (n radix)
   (reduce #'+ (mapcar (lambda (x) (* x x)) (digits n radix))))
HAPPY

Now, a function that iterates until we get a cycle, or when the sequence longer than a preset length. I hard-coded it to be 1000, but it can also be fed into the iteration.

(defun iterate (n fn &optional carry (max-depth 999))
   (cond
     ((member n carry :test #'equal) (reverse (cons n carry)))
     ((zerop max-depth) nil)
     (t (iterate (funcall fn n) fn (cons n carry) (1- max-depth)))))
ITERATE

Okay. Let’s go:

(iterate 56 (lambda (x) (happy x 16)))
(56 73 97 37 29 170 200 208 169 181 146 85 50 13 169)


(iterate 129 (lambda (x) (happy x 10)))
(129 86 100 1 1)


(iterate 129371982371 (lambda (x) (happy x 217)))
(129371982371 87661 78697 41475 37265 54205 30609 20025 12185 4225 10765
 19825 14365 6205 17425 10625 45985 83725 60625 10569 25713 25373 53857 2643
 1665 21365 19405 16385 17725 28465 18605 32825 26165 30025 25285 26225 48625
 339 14885 21265 56065 7923 13617 30413 20689 14501 36397 52853 15561 28757
 30193 20221 10249 4709 23545 23545)