OFFSET
0,3
COMMENTS
PROG
(Scheme) (define (A125974 n) (let ((runlens (binexp->runcount1list n))) (let loop ((chosen (reverse! (bisect runlens 0))) (others (reverse! (bisect runlens 1))) (s 0) (b (modulo n 2)) (p 1)) (cond ((and (null? chosen) (null? others)) s) ((and (pair? chosen) (= 1 (car chosen)) (pair? (cdr chosen))) (loop (cdr chosen) others (+ s (* b p)) b (+ p p))) (else (loop others (if (or (null? chosen) (= 1 (car chosen))) '() (cons (- (car chosen) 1) (cdr chosen))) (+ s (* b p)) (- 1 b) (+ p p)))))))
(Scheme) (define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (+ 1 count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2))))))) ;; (binexp->runcount1list 25) returns (2 2 1)
(Scheme) (define (bisect lista parity) (let loop ((lista lista) (i 0) (z (list))) (cond ((null? lista) (reverse! z)) ((eq? i parity) (loop (cdr lista) (modulo (1+ i) 2) (cons (car lista) z))) (else (loop (cdr lista) (modulo (1+ i) 2) z)))))
(Python)
def A125974(n):
if 0 == n:
return n
chosen = A000265(n) # Initially ones, get rid of lsb-0's.
others = n >> A007814(n + 1) # Initially zeros, get rid of lsb-1's.
s = 0 # the resulting sum
b = n % 2 # n's parity.
p = 1 # powers of two.
while (chosen != 0) or (others != 0):
if (1 == chosen) or (1 == A036987(chosen + 1)): # Last one or zero at hand.
chosen = others
others = 0
nb = 1 - b
elif (0 == (chosen % 4)) or (
3 == (chosen % 4)
): # Source run continues, dest changes.
tmp = chosen
chosen = others
others = tmp >> 1
nb = 1 - b
elif 1 == (
chosen % 4
): # Source run changes, from ones to zeros, skip past zeros.
chosen = A000265(chosen - 1)
nb = b
else: # Source run changes, from zeros to ones, skip past ones.
chosen = chosen >> A007814(chosen + 2)
nb = b
s += b * p
p <<= 1
b = nb
return s
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Jan 02 2007
STATUS
approved