The Kitchen Sink and Other Oddities

Atabey Kaygun

Binary Symmetrization

Description of the problem

Today I am going to do something silly, sort of. Here is what I want to do: take a number, convert it into binary, reverse the digits and add to the original number, then finally remove all the 2-part, that is, divide it by 2 as far as you can. Then I am going to iterate this until I hit a fixed point.

An implementation in Common Lisp

Here is the function that does the silly tranformation:

(defun silly-fn (n)
  (let ((m (parse-integer (reverse (format nil "~b" n)) :radix 2)))
    (do ((r (+ m n) (/ r 2)))
        ((oddp r) r))))
SILLY-FN

Here is the iterator:

(defun iterate (init fn &optional carry)
  (if (member init carry)
      (nreverse carry)
      (iterate (funcall fn init) fn (cons init carry))))
ITERATE

And here are a couple of examples:

(loop repeat 10 collect (iterate (1+ (* 2 (random (expt 2 20)))) #'silly-fn))
((2030507 1891277 841165 12321 5193 4935 381)
 (2011297 193829 181233 164223 106209 43893 44325 43245 45057 38919 3009 2559
  831 921 3)
 (726733 730797 736893 758565 716769 636843 378273 325983 104907 106623 118341
  50379 52215 56805 3117 375 213 3)
 (1122121 1163053 1322863 836477 101115 107727 116109 51765 11985 10455 6375
  6885 765)
 (1149447 373383 208701 25137 10773)
 (494267 473765 203107 203235 203811 202371 200211 202731 211911 222621 51591
  54669 12519 13653 3)
 (1737929 735805 753669 704529 630819 358431 216645 23937 20271 6453 1497 1371
  195)
 (816841 355179 24849 10581 10749 11505 10335 6585 2907 801 333 345 327 195)
 (1901891 1748141 404075 421511 441629 102497 42781 45057 38919 3009 2559 831
  921 3)
 (1842167 1903487 1995467 1863245 831301 187347 6189 747 201 87 51))

An analysis

It seems the sequence terminates always. But I need to actually prove this. Curious problem.