A054238 Array read by downward antidiagonals: T(i,j) = bits of binary expansion of i interleaved with that of j.

0, 1, 2, 4, 3, 8, 5, 6, 9, 10, 16, 7, 12, 11, 32, 17, 18, 13, 14, 33, 34, 20, 19, 24, 15, 36, 35, 40, 21, 22, 25, 26, 37, 38, 41, 42, 64, 23, 28, 27, 48, 39, 44, 43, 128, 65, 66, 29, 30, 49, 50, 45, 46, 129, 130, 68, 67, 72, 31, 52, 51, 56, 47, 132, 131, 136, 69, 70, 73, 74

Offset: 0

Author

Marc LeBrun, Feb 07 2000

Keywords

• easy
• nonn
• base
• tabl

Comments

Inverse of sequence A054239 considered as a permutation of the nonnegative integers.

Permutation of nonnegative integers. Can be used as natural alternate number casting for pairs/tables (vs. usual diagonalization).

This array is a Z-order curve in an N x N grid. - Max Barrentine, Sep 24 2015

Each row n of this array is the lexicographically earliest sequence such that no term occurs in a previous row, no three terms form an arithmetic progression, and the k-th term in the n-th row is equal to the k-th term in row 0 plus some constant (specifically, T(n,k) = T(0,k) + A062880(n)). - Max Barrentine, Jul 20 2016

Examples

			From _Philippe Deléham_, Oct 18 2011: (Start)
The array starts in row n=0 with columns k >= 0 as follows:
   0  1  4  5 16 17 20 21 ...
   2  3  6  7 18 19 22 23 ...
   8  9 12 13 24 25 28 29 ...
  10 11 14 15 26 27 30 31 ...
  32 33 36 37 48 49 52 53 ...
  34 35 38 39 50 51 54 55 ...
  40 41 44 45 56 57 60 61 ...
  42 43 46 47 58 59 62 63 ...
(End)
T(6,5)=57 because 1.1.0. (6) merged with .1.0.1 (5) is 111001 (57). [Corrected by _Georg Fischer_, Jan 21 2022]
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• G. M. Morton, A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, IBM, 1966.
• Wikipedia, Z-order Curve
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A000695 (row n=0), A062880 (column k=0), A001196 (main diagonal).

Cf. A059905, A059906, A346453 (by upwards antidiagonals).

See also A163357 and A163334 for other fractal curves in N x N grids.

Programs

Maple

N:= 4: # to get the first 2^(2N+1)+2^N terms
G:= 1/(1-y)/(1-x)*(add(2^(2*i+1)*x^(2^i)/(1+x^(2^i)),i=0..N) + add(2^(2*i)*y^(2^i)/(1+y^(2^i)),i=0..N)):
S:= mtaylor(G,[x=0,y=0],2^(N+1)):
seq(seq(coeff(coeff(S,x,i),y,m-i),i=0..m),m=0..2^(N+1)-1); # Robert Israel, Jul 21 2016

Mathematica

Table[Total@ Map[FromDigits[#, 2] &, Insert[#, 0, {-1, -1}] &@ Map[Riffle[IntegerDigits[#, 2], 0, 2] &, {n - k, k}]], {n, 0, 11}, {k, 0, n}] // Flatten (* Michael De Vlieger, Jul 21 2016 *)

Formula

T(n,k) = A000695(k) + 2*A000695(n). - Philippe Deléham, Oct 18 2011

From Robert Israel, Jul 21 2016: (Start)

G.f. of array: g(x,y) = (1/(1-x)*(1-y)) * Sum_{i>=0}

(2^(2*i+1)*x^(2^i)/(1+x^(2^i)) + 2^(2*i)*y^(2^i)/(1+y^(2^i))).

T(2*n+i,2*k+j) = 4*T(n,k) + 2*i+j for i,j in {0,1}. (End)