0,2

In general, this representation is (sometimes much) more compact for numbers having almost all 0s or 1s in their binary representations.

Definition: i) 0 is encoded as 0. ii) For n>0, first convert the number to its standard binary representation n_2 (A007088(n)).

If, and only if, n_2 has more 1s than 0s (i.e., n is a term of A072600), a(n) begins with the prefix symbol 2.

For determining bit positions below, the least significant bit position is counted as position 0. In all cases, a(n) next includes the bit position of the leading 1 in n_2.

For the last step, the target bit type depends upon whether the prefix symbol was used: if so, target is 0 else 1. Finally, scan n_2 left-to-right for all bits of the target type.

For each such bit found, append the delimiter symbol 2 followed by that bit's position p in standard binary; i.e., append 2, then A007088(p).

PARI program to do encoding is available; may be posted later.

Some ideas for improvement (and other sequences):

1) Introduce a fourth symbol, 3, to serve as a second delimiter (usually meaning "switch to 0-positions now") and save a symbol position by avoiding the need for a prefix -- except that in the cases where the numbers are of the form 2^k-1 (all 1s, which would still need to be distinguished from a 1 followed by all 0s) the new "delimiter" would have to be used as the final symbol instead.

2) Use a type of run length encoding on the bit positions to make representations more compact also when there are blocks of 0s or 1s.

3) Use the fact that the present method may encode the 1s complement of a particular number more compactly.

a(63) = 2101 as 63 = 111111 (base 2) has more 1s than 0s; the leading 1 is in position 5 = 101 (base 2). a(64) = 110 as 64 = 1000000 (base 2) does not have more 1s than 0s; the leading 1 is in position 6 = 110 (base 2). a(65) = 11020 as 65 = 1000001 (base 2) does not have more 1s than 0s; 1s are in positions 6 = 110 (base 2) and 0 = 0 (base 2).

Cf. A140117, A007088, A072600.

Sequence in context: A040417 A003833 A040418 this_sequence A084923 A141589 A040419

Adjacent sequences: A140113 A140114 A140115 this_sequence A140117 A140118 A140119

base,nonn

Rick L. Shepherd (rshepherd2(AT)hotmail.com), May 08 2008