A334474 T(n, k) is the number of steps from the point (0, 0) to the point (k, n) along the space filling curve T defined in Comments section; square array T(n, k), n, k >= 0 read by antidiagonals downwards.

0, 2, 1, 8, 3, 4, 9, 7, 6, 5, 31, 10, 11, 15, 16, 32, 30, 12, 14, 18, 17, 33, 29, 27, 13, 24, 19, 20, 35, 34, 28, 26, 25, 23, 22, 21, 121, 36, 37, 41, 42, 61, 62, 63, 64, 122, 120, 38, 40, 43, 44, 60, 59, 66, 65, 123, 119, 117, 39, 47, 46, 45, 58, 72, 67, 68

Offset: 0

Author

Rémy Sigrist, May 02 2020

Keywords

• nonn
• tabl

Comments

We consider a hexagonal lattice with X-axis and Y-axis as follows:

Y

/

/

0 ---- X

We define the family {T_n, n > 0} as follows:

- T_1 contains the origin (0, 0):

+

O

- T_2 contains the points (0, 0), (0, 1) and (1, 0), in that order:

+

/ \

/ \

+ . . +

O

- for n > 1, T_{2*n} is built from 3 copies of T_n and one copy T_{n-1} arranged as follows:

+

/ \

/ \

/ n \

/ \

+ . . . . +

\ \

+ +-----+ +

/ \ .n-1/ / .

/ \ . / / .

/ n \ + / n .

/ \ / / .

+ . . . . + +---------+

O

- for n > 0, T_{2*n+1} is built from 3 copies of T_n and one copy of T_{n+1} arranged as follows:

+

/ \

/ \

/ \

/ n+1 \

/ \

+ . . . . . +

\ \

+ +---------+ +

/ \ . / / .

/ \ . n / / .

/ n \ . / / n .

/ \ . / / .

+ . . . . +--+ +---------+

O

- for any n > 0, T_n starts at (0, 0) and ends at (n-1, n-1), and contains every point (x, y) such that x, y >= 0 and x + y < n,

- T is the limit of T_{2^k} as k tends to infinity (note that for any k >= 0, T_{2^k} is a prefix of T_{2^(k+1)}),

- T visits exactly once every point (x, y) such that x, y >= 0.

Examples

			Square array starts:
  n\k|   0  1  2  3  4  5  6  7
  ---+-------------------------
    0|   0  2  8--9 31-32-33 35
     |   | /|  |  |  |     | /|
     |   |/ |  |  |  |     |/ |
    1|   1  3  7 10 30-29 34 36
     |     /  /  /      |    /
     |    /  /  /       |   /
    2|   4  6 11-12 27-28 37-38
     |   | /      |  |        |
     |   |/       |  |        |
    3|   5 15-14-13 26 41-40-39
     |    /         /  /
     |   /         /  /
    4|  16 18 24-25 42-43 47-48
     |   | /|  |       /  /   |
     |   |/ |  |      /  /    |
    5|  17 19 23 61 44 46 50-49
     |     /  /  /|  | /   |
     |    /  /  / |  |/    |
    6|  20 22 62 60 45 56 51-52-
     |   | /  /  /     /|
		

Links

• Ideophilus, A triangular space-filling curve
• Rémy Sigrist, Colored representation of T_{2^10} (where the hue is function of the number of steps from the origin)
• Rémy Sigrist, Representation of T_{2^k} for k = 1..5
• Rémy Sigrist, PARI program for A334474

Crossrefs

See A334475 and A334476 for the coordinates of the curve.

Programs

PARI

\\ See Links section.

Formula

T(A334476(n), A334475(n)) = n.