A209859 Rewrite the binary expansion of n from the most significant end, 1 -> 1, 0+1 (one or more zeros followed by one) -> 0, drop the trailing zeros of the original n.

0, 1, 1, 3, 1, 2, 3, 7, 1, 2, 2, 5, 3, 6, 7, 15, 1, 2, 2, 5, 2, 4, 5, 11, 3, 6, 6, 13, 7, 14, 15, 31, 1, 2, 2, 5, 2, 4, 5, 11, 2, 4, 4, 9, 5, 10, 11, 23, 3, 6, 6, 13, 6, 12, 13, 27, 7, 14, 14, 29, 15, 30, 31, 63, 1, 2, 2, 5, 2, 4, 5, 11, 2, 4, 4, 9, 5, 10, 11, 23, 2, 4, 4, 9, 4, 8, 9, 19, 5, 10, 10, 21, 11, 22, 23, 47, 3, 6, 6, 13, 6, 12, 13, 27, 6, 12, 12, 25, 13

Offset: 0

Author

Antti Karttunen, Mar 24 2012

Keywords

• nonn
• base

Comments

This is the number k such that the k-th composition in standard order is the reversed sequence of lengths of the maximal anti-runs of the binary indices of n. Here, the binary indices of n are row n of A048793, and the k-th composition in standard order is row k of A066099. For example, the binary indices of 100 are {3,6,7}, with maximal anti-runs ((3,6),(7)), with reversed lengths (1,2), which is the 6th composition in standard order, so a(100) = 6. - Gus Wiseman, Jul 27 2025

Examples

			102 in binary is 1100110, we rewrite it from the left so that first two 1's stay same ("11"), then "001" is rewritten to "0", the last 1 to "1", and we ignore the last 0, thus getting 1101, which is binary expansion of 13, thus a(102) = 13.
		

Links

• Gus Wiseman, Statistics, classes, and transformations of standard compositions

Crossrefs

This is an "inverse" of A071162, i.e. a(A071162(n)) = n for all n. Bisection: A209639. Used to construct permutation A209862.

Removing duplicates appears to give A358654.

Sorted positions of firsts appearances appear to be A247648+1.

A245563 lists run-lengths of binary indices (ranks A246029), reverse A245562.

A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.

Cf. A000120, A023758, A029931, A044813, A048793, A052499, A069010, A348366, A384878, A384879, A384893.

Cf. A384877, A385816, A385887, A385889.

Programs

Mathematica

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[Reverse[Length/@Split[bpe[n],#2!=#1+1&]]],{n,0,100}] (* Gus Wiseman, Jul 25 2025 *)

Python

import re
def a(n): return int(re.sub("0+1", "0", bin(n)[2:].rstrip("0")), 2) if n else 0
print([a(n) for n in range(109)])  # Michael S. Branicky, Jul 25 2025

Scheme

(define (A209859 n) (let loop ((n n) (s 0) (i (A053644 n))) (cond ((zero? n) s) ((> i n) (if (> (/ i 2) n) (loop n s (/ i 2)) (loop (- n (/ i 2)) (* 2 s) (/ i 4)))) (else (loop (- n i) (+ (* 2 s) 1) (/ i 2))))))

Formula

a(n) = a(A000265(n)).