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
endwhere 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
endLet 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-PNext, 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-PAnd 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))))ITERATELet 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)