login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 17:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)