A072600 -id:A072600 - cp's OEIS frontend

A140116 Numbers encoded in an alternate, sometimes more compact, binary system with a third, dual-purpose, prefix/delimiter symbol not always required.

0, 20, 1, 21, 10, 21021, 21020, 210, 11, 1120, 1121, 211210, 11210, 21121, 21120, 211, 100, 10020, 10021, 2100211210, 100210, 210021121, 210021120, 2100211, 100211, 210021021, 210021020, 2100210, 21002120, 210021, 210020, 2100, 101, 10120

Offset: 0

Rick L. Shepherd, May 08 2008

In general, this representation is (sometimes much) more compact for numbers having almost all 0's or 1's 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 1's than 0's (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, otherwise 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 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.
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.
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 1's than 0's; the leading 1 is in position 5 = 101 (base 2).
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).
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).

Cf. A140117, A007088, A072600.

cp's OEIS Frontend

A140116 Numbers encoded in an alternate, sometimes more compact, binary system with a third, dual-purpose, prefix/delimiter symbol not always required.

Views

Author

Keywords

Comments

Examples

Crossrefs