|
%I #10 Dec 01 2021 03:52:29
%S 0,20,1,21,10,21021,21020,210,11,1120,1121,211210,11210,21121,21120,
%T 211,100,10020,10021,2100211210,100210,210021121,210021120,2100211,
%U 100211,210021021,210021020,2100210,21002120,210021,210020,2100,101,10120
%N Numbers encoded in an alternate, sometimes more compact, binary system with a third, dual-purpose, prefix/delimiter symbol not always required.
%C In general, this representation is (sometimes much) more compact for numbers having almost all 0's or 1's in their binary representations.
%C Definition: i) 0 is encoded as 0. ii) For n>0, first convert the number to its standard binary representation n_2 (A007088(n)).
%C If and only if n_2 has more 1's than 0's (i.e., n is a term of A072600), a(n) begins with the prefix symbol 2.
%C 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.
%C For the last step, the target bit type depends upon whether the prefix symbol was used: if so, target is 0, otherwise 1. Finally, scan n_2 left-to-right for all bits of the target type.
%C 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).
%C PARI program to do encoding is available; may be posted later.
%C Some ideas for improvement (and other sequences):
%C 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 1's, which would still need to be distinguished from a 1 followed by all 0's) the new "delimiter" would have to be used as the final symbol instead.
%C 2) Use a type of run-length encoding on the bit positions to make representations more compact also when there are blocks of 0's or 1's.
%C 3) Use the fact that the present method may encode the 1s complement of a particular number more compactly.
%e a(63) = 2101 as 63 = 111111 (base 2) has more 1's than 0's; the leading 1 is in position 5 = 101 (base 2).
%e a(64) = 110 as 64 = 1000000 (base 2) does not have more 1's than 0's; the leading 1 is in position 6 = 110 (base 2).
%e a(65) = 11020 as 65 = 1000001 (base 2) does not have more 1's than 0's; 1's are in positions 6 = 110 (base 2) and 0 = 0 (base 2).
%Y Cf. A140117, A007088, A072600.
%K base,nonn
%O 0,2
%A _Rick L. Shepherd_, May 08 2008
| 