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.

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

Author

Andres Cicuttin, Mar 12 2017

Keywords

• nonn
• base

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

• Andres Cicuttin, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A280079, A280317.

Programs

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}]