login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A283618
A 2D -> 1D binary encoding of points (x,y) of the square lattice such that x >= 0 and 0 <= y <= x, and ranked in order of increasing distance from the origin. Equidistant points are ranked in order of increasing ordinate.
1
0, 2, 3, 8, 9, 12, 10, 11, 14, 32, 33, 15, 36, 34, 37, 35, 38, 48, 39, 40, 41, 44, 50, 45, 42, 43, 51, 56, 46, 47, 57, 128, 129, 58, 132, 60, 133, 59, 144, 130, 131, 134, 62, 145, 135, 146, 63, 136, 148, 137, 140, 147, 141, 149, 152, 150, 138, 139, 142, 153, 192, 143, 151, 156, 154, 160, 161, 194, 155, 164, 157, 165
OFFSET
1,2
COMMENTS
The encoding consists of assigning a number whose binary representation is the interleaving of the binary representation of the two integers of the encoded pair. Let's call Enc(x,y) the encoding function of two nonnegative integers x and y, and call z the corresponding coding number, that is Enc(x,y) = z, and also call respectively nbx, nby and nbz the corresponding number of bits of x, y, and z; then there are two possible cases:
a) If nbx >= nby then nbz is even, and the bits of z in odd positions correspond to the bits of x, and those in even positions correspond to y. For example, if x=8 (1000 in base 2) and y=3 (11 in base 2) then z = Enc(8,3) = 133 (10000101 in base 2):
x: 8 -> 1000 -> 1 0 0 0
odd positions | | | |
z: interleaved -> 1 0 0 0 0 1 0 1 -> 10000101 -> 133
even positions | | | |
y: 3 -> 0011 -> 0 0 1 1
b) If nbx < nby then nbz is odd, and the bits of z in even positions correspond to the bits of x, and those in odd positions correspond to y. For example if x=5 (101 in base 2) and y=31 (11111 in base 2) then z= 383(101111111 in base 2):
x: 5 -> 101 -> 0 1 0 1
even positions | | | |
z: interleaved -> 1 0 1 1 1 0 1 1 1 -> 101110111 -> 375
odd positions | | | | |
y: 31 -> 10001 -> 1 1 1 1 1
Before interleaving the bits, the binary representations must be eventually completed by padding with zeros on the left to ensure an equal number of bits for both integers.
The same encoding scheme could be generalized for more dimensions (ND -> 1D), and for numeric representations in other bases of the positional numeral system.
This encoding scheme can also be generalized for real numbers, for example, establishing a bijection between reals belonging to the open interval (0,1) and points within the square with vertices (0,0),(0,1),(1,0) and (1,1). In this case the corresponding binary representations will in general be infinite.
Number of bits of a(n) is even for n > 1.
The encoded points are those whose abscissas and ordinates are respectively given by A280079, A280317.
LINKS
MATHEMATICA
(* Maximum explorative abscissa *)
xmax=20;
(* points in the triangle of vertices (0, 0), (0, max) and (xmax, xmax) *)
points=Flatten[Table[{x, y}, {x, 0, xmax}, {y, 0, x}], 1];
(* Sorting points: first by increasing distance from origin, and then by increasing ordinate *)
sortedpoints=SortBy[points, {#[[1]]^2+#[[2]]^2&, #[[2]]&}];
(* Safe limit for correctly sorted sequence *)
nmax=Floor[xmax^2/4];
(* Separate lists of abscissas and ordinates *)
abs=Transpose[sortedpoints][[1]][[1;; nmax]];
ord=Transpose[sortedpoints][[2]][[1;; nmax]];
(* Definition of the 2D -> 1D binary encoding function: *)
MergerEncoder[a_, b_]:=Module[{x, maxbits},
maxbits=32; (* for a, b < 2^32-1, increase this value for larger integers *)
x={IntegerDigits[a, 2, maxbits],
IntegerDigits[b, 2, maxbits]}//Transpose//Flatten;
FromDigits[x, 2]//Return];
a= Table[MergerEncoder[abs[[n]], ord[[n]]], {n, 1, nmax}]
CROSSREFS
Sequence in context: A288740 A290150 A237037 * A284370 A273783 A075190
KEYWORD
nonn,base
AUTHOR
Andres Cicuttin, Mar 12 2017
STATUS
approved