The Kitchen Sink and Other Oddities

Atabey Kaygun

An integer dynamical system of integers

Description of the problem

Yesterday I was looking at an integer dynamical system defined by the following procedure:

procedure symmetrize
input: an integer n
output: an integer m
begin
   let x be the integer given by radix 2 digits reversed
   let m be x + n divided by the 2-part of x + n
   return m
end

where 2-part of an integer n is the largest power of 2 that divides n. Today, I am going to do the same in radix p.

procedure symmetrize
input: a pair of integers n and p
output: an integer m
begin
   let x be the integer given by radix p digits reversed
   let y be (x + n) + p - ((x + n) mod p)
   let m be y divided by the p-part of y
   return m
end

An implementation

Let us look at my implementation. First, a function that returns the p-reduction of an integer:

(defun reduce-p (n p)
   (if (zerop (mod n p))
       (reduce-p (/ n p) p)
       n))
REDUCE-P

Next, symmetrization function:

(defun symmetrize-p (n p)
  (let* ((xs (do* ((m n (/ (- m (mod m p)) p))
                   (rs (list (mod m p)) (cons (mod m p) rs)))
                  ((zerop m) rs)))
         (re (do* ((rs (cdr xs) (cdr rs))
                   (g 1 (+ (* g p) (car rs))))
                  ((null (cdr rs)) g))))
    (let ((x (+ re n)))
      (reduce-p (+ x (- p (mod x p))) p))))
SYMMETRIZE-P

And finally, an iteration function:

(defun iterate (n iterator &optional carry)
  (if (member n carry :test #'equal)
      (nreverse carry)
      (iterate (funcall iterator n) iterator (cons n carry))))
ITERATE

Let us test it: First for \(p=2\).

(iterate (reduce-p (random (expt 2 12)) 2)
         (lambda (n) (symmetrize-p n 2)))
(3541 1771 443 111 7 1)

Next, for \(p=3\).

(iterate (reduce-p (random (expt 2 20)) 3)
         (lambda (n) (symmetrize-p n 3))))
(335216 223478 5518 2950 1967 1069 713 395 88 59 31 7 4 1)

and finally for \(p=53\).

(iterate (reduce-p (random (expt 2 20)) 53)
         (lambda (n) (symmetrize-p n 53)))
(363366 10903 306 8 1)