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.
LINKS
Andres Cicuttin, Table of n, a(n) for n = 1..10000
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
KEYWORD
nonn,base
AUTHOR
Andres Cicuttin, Mar 12 2017
STATUS
approved