cp's OEIS Frontend

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.

%I A283618 #31 Nov 11 2019 00:50:03
%S A283618 0,2,3,8,9,12,10,11,14,32,33,15,36,34,37,35,38,48,39,40,41,44,50,45,
%T A283618 42,43,51,56,46,47,57,128,129,58,132,60,133,59,144,130,131,134,62,145,
%U A283618 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
%N 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.
%C A283618 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:
%C A283618 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):
%C A283618     x: 8 -> 1000 ->      1   0   0   0
%C A283618         odd positions    |   |   |   |
%C A283618     z: interleaved ->    1 0 0 0 0 1 0 1   ->  10000101  ->  133
%C A283618         even positions     |   |   |   |
%C A283618     y: 3 -> 0011 ->        0   0   1   1
%C A283618 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):
%C A283618     x: 5  -> 101 ->        0   1   0   1
%C A283618         even positions     |   |   |   |
%C A283618     z: interleaved ->    1 0 1 1 1 0 1 1 1   ->  101110111  ->  375
%C A283618         odd positions    |   |   |   |   |
%C A283618     y: 31 -> 10001 ->    1   1   1   1   1
%C A283618 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.
%C A283618 The same encoding scheme could be generalized for more dimensions (ND -> 1D), and for numeric representations in other bases of the positional numeral system.
%C A283618 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.
%C A283618 Number of bits of a(n) is even for n > 1.
%C A283618 The encoded points are those whose abscissas and ordinates are respectively given by A280079, A280317.
%H A283618 Andres Cicuttin, <a href="/A283618/b283618.txt">Table of n, a(n) for n = 1..10000</a>
%t A283618 (* Maximum explorative abscissa *)
%t A283618 xmax=20;
%t A283618 (* points in the triangle of vertices (0,0),(0,max) and (xmax,xmax) *)
%t A283618 points=Flatten[Table[{x,y},{x,0,xmax},{y,0,x}],1];
%t A283618 (* Sorting points: first by increasing distance from origin, and then by increasing ordinate *)
%t A283618 sortedpoints=SortBy[points,{#[[1]]^2+#[[2]]^2&,#[[2]]&}];
%t A283618 (* Safe limit for correctly sorted sequence *)
%t A283618 nmax=Floor[xmax^2/4];
%t A283618 (* Separate lists of abscissas and ordinates *)
%t A283618 abs=Transpose[sortedpoints][[1]][[1;;nmax]];
%t A283618 ord=Transpose[sortedpoints][[2]][[1;;nmax]];
%t A283618 (* Definition of the 2D -> 1D binary encoding function: *)
%t A283618 MergerEncoder[a_,b_]:=Module[{x,maxbits},
%t A283618 maxbits=32; (* for a,b < 2^32-1, increase this value for larger integers *)
%t A283618 x={IntegerDigits[a,2,maxbits],
%t A283618 IntegerDigits[b,2,maxbits]}//Transpose//Flatten;
%t A283618 FromDigits[x,2]//Return];
%t A283618 a= Table[MergerEncoder[abs[[n]],ord[[n]]],{n,1,nmax}]
%Y A283618 Cf. A280079, A280317.
%K A283618 nonn,base
%O A283618 1,2
%A A283618 _Andres Cicuttin_, Mar 12 2017