cp's OEIS Frontend

A125974 Function whose restriction to A014486 induces signature-permutation A125976.

%I A125974 #7 Nov 29 2023 11:44:49
%S A125974 0,1,2,5,10,3,2,21,42,11,12,13,10,11,10,85,170,43,44,13,52,7,6,53,42,
%T A125974 11,12,45,10,43,42,341,682,171,172,45,180,39,38,53,212,23,56,57,50,51,
%U A125974 22,213,170,43,44,45,52,39,38,181,42,43,44,173,42,171,170,1365,2730
%N A125974 Function whose restriction to A014486 induces signature-permutation A125976.
%C A125974 A125975 gives the terms i, for which a(a(i)) = i. Question: would it be possible to construct a more elegant and natural variant which were an involution for all the natural numbers? (and acting in the same way on the set A125975, or at least on the set A014486.)
%o A125974 (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)))))))
%o A125974 (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)
%o A125974 (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)))))
%o A125974 (Python)
%o A125974 def A125974(n):
%o A125974     if 0 == n:
%o A125974         return n
%o A125974     chosen = A000265(n)  # Initially ones, get rid of lsb-0's.
%o A125974     others = n >> A007814(n + 1)  # Initially zeros, get rid of lsb-1's.
%o A125974     s = 0  # the resulting sum
%o A125974     b = n % 2  # n's parity.
%o A125974     p = 1  # powers of two.
%o A125974     while (chosen != 0) or (others != 0):
%o A125974         if (1 == chosen) or (1 == A036987(chosen + 1)):  # Last one or zero at hand.
%o A125974             chosen = others
%o A125974             others = 0
%o A125974             nb = 1 - b
%o A125974         elif (0 == (chosen % 4)) or (
%o A125974             3 == (chosen % 4)
%o A125974         ):  # Source run continues, dest changes.
%o A125974             tmp = chosen
%o A125974             chosen = others
%o A125974             others = tmp >> 1
%o A125974             nb = 1 - b
%o A125974         elif 1 == (
%o A125974             chosen % 4
%o A125974         ):  # Source run changes, from ones to zeros, skip past zeros.
%o A125974             chosen = A000265(chosen - 1)
%o A125974             nb = b
%o A125974         else:  # Source run changes, from zeros to ones, skip past ones.
%o A125974             chosen = chosen >> A007814(chosen + 2)
%o A125974             nb = b
%o A125974         s += b * p
%o A125974         p <<= 1
%o A125974         b = nb
%o A125974     return s
%Y A125974 Python code uses the following functions: A000265, A007814 and A036987.
%K A125974 nonn,base
%O A125974 0,3
%A A125974 _Antti Karttunen_, Jan 02 2007