A163358 -id:A163358 - cp's OEIS frontend

A163357 Hilbert curve in N X N grid, starting rightwards from the top-left corner, listed by descending antidiagonals.

0, 1, 3, 14, 2, 4, 15, 13, 7, 5, 16, 12, 8, 6, 58, 19, 17, 11, 9, 57, 59, 20, 18, 30, 10, 54, 56, 60, 21, 23, 29, 31, 53, 55, 61, 63, 234, 22, 24, 28, 32, 52, 50, 62, 64, 235, 233, 25, 27, 35, 33, 51, 49, 67, 65, 236, 232, 230, 26, 36, 34, 46, 48, 68, 66, 78, 239, 237, 231

Offset: 0

Antti Karttunen, Jul 29 2009

			The top left 8 X 8 corner of the array shows how this surjective self-avoiding walk begins (connect the terms in numerical order, 0-1-2-3-...):
   0  1 14 15 16 19 20 21
   3  2 13 12 17 18 23 22
   4  7  8 11 30 29 24 25
   5  6  9 10 31 28 27 26
  58 57 54 53 32 35 36 37
  59 56 55 52 33 34 39 38
  60 61 50 51 46 45 40 41
  63 62 49 48 47 44 43 42

A. Karttunen, Table of n, a(n) for n = 0..32895
Jörg Arndt, Plane-filling curves on all uniform grids, arXiv:1607.02433v1 [math.CO], July 11, 2016.
Herman Haverkort, Recursive tilings and space-filling curves
Herman Haverkort, The Sound of Space-Filling Curves, Proc. Bridges 2017, pp. 399-402.
Eric Weisstein's World of Mathematics, Hilbert curve
Wikipedia, Self-avoiding walk
Wikipedia, Space-filling curve
Index entries for sequences that are permutations of the nonnegative integers

Transpose: A163359. Inverse: A163358. One-based version: A163361. Row sums: A163365. Row 0: A163482. Column 0: A163483. Central diagonal: A062880. See also A163334 & A163336 for the Peano curve.

b[{n_, k_}, {m_}] := (A[k, n] = m-1);
MapIndexed[b, List @@ HilbertCurve[4][[1]]];
Table[A[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Mar 07 2021 *)

a(n) = A163355(A054238(n)).

Links to further derived sequences added by Antti Karttunen, Sep 21 2009

A059252 Hilbert's Hamiltonian walk on N X N projected onto x axis: m(3).

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 3, 2, 2, 3, 3, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 5, 5, 4, 4, 4, 5, 5, 6, 6, 7, 7, 7, 6, 6, 7, 7, 7, 6, 6, 5, 4, 4, 5, 5, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 8, 8, 8, 9, 9, 10, 10, 11, 11, 11, 10, 10, 11, 12, 12, 13, 13, 14, 15, 15, 14, 14, 15, 15, 14

Offset: 0

Claude Lenormand (claude.lenormand(AT)free.fr), Jan 23 2001

nonn

This is the X-coordinate of the n-th term in Hilbert's Hamiltonian walk A163359 and the Y-coordinate of its transpose A163357.

			[m(1)=0 0 1 1, m'(1)= 0 1 10] [m(2) =0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, m'(2)=0 1 1 0 0 0 1 1 2 2 3 3 3 2 2 3].

Antti Karttunen, Table of n, a(n) for n = 0..65535
Joerg Arndt, Matters Computational (The Fxtbook), section 1.31.1 "The Hilbert curve", page 85, lin2hilbert.
Michael Beeler, R. William Gosper, and Richard Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory report AIM-239, February 1972. Item 115 by Gosper, page 52. Also HTML transcription. (To use algorithm S or the state table, pad n with high 0-bits to a multiple of 4 bits.)
J. Shallit, Hilbert's spacefilling curve described by automatic, regular, and synchronized sequences, arXiv:2106.01062 [cs.FL], June 2 2021.
Index entries for sequences related to coordinates of 2D curves

See also the y-projection, m'(3), A059253, as well as: A163539, A163540, A163542, A059261, A059285, A163547 and A163529.

void h(unsigned int *x, unsigned int *y, unsigned int l){
x[0] = y[0] = 0; unsigned int *t = NULL; unsigned int n = 0, k = 0;
for(unsigned int i = 1; i>(2*n)){
case 1: x[i] = y[i&k]; y[i] = x[i&k]+(1<Jared Rager, Jan 09 2021 */
(C++) See Fxtbook link.

Initially [m(0) = 0, m'(0) = 0]; recursion: m(2n + 1) = m(2n).m'(2n).f(m'(2n), 2n).c(m(2n), 2n + 1); m'(2n + 1) = m'(2n).f(m(2n), 2n).f(m(2n), 2n).mir(m'(2n)); m(2n) = m(2n - 1).f(m'(2n - 1), 2n - 1).f(m'(2n - 1), 2n - 1).mir(m(2n - 1)); m'(2n) = m'(2n - 1).m(2n - 1).f(m(2n - 1), 2n - 1).c(m'(2n - 1), 2n); where f(m, n) is the alphabetic morphism i := i + 2^n [example: f(0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, 2) = 4 4 5 5 6 7 7 6 6 7 7 6 5 5 4 4]; c(m, n) is the complementation to 2^n - 1 alphabetic morphism [example: c(0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, 3) = 7 7 6 6 5 4 4 5 5 4 4 5 6 6 7 7]; and mir(m) is the mirror operator [example: mir(0 1 1 0 0 0 1 1 2 2 3 3 3 2 2 3) = 3 2 2 3 3 3 2 2 1 1 0 0 0 1 1 0].

a(n) = A002262(A163358(n)) = A025581(A163360(n)) = A059906(A163356(n)).

Extended by Antti Karttunen, Aug 01 2009

A059253 Hilbert's Hamiltonian walk on N X N projected onto y axis: m'(3).

Original entry on oeis.org

0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 6, 6, 7, 7, 6, 5, 5, 4, 4, 4, 4, 5, 5, 6, 7, 7, 6, 6, 7, 7, 6, 5, 5, 4, 4, 3, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 3, 3, 2, 2, 3, 3, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 5, 5, 4, 4, 4

Offset: 0

Claude Lenormand (claude.lenormand(AT)free.fr), Jan 23 2001

nonn

This is the Y-coordinate of the n-th term in the type I Hilbert's Hamiltonian walk A163359 and the X-coordinate of its transpose A163357.

Antti Karttunen, Table of n, a(n) for n = 0..65535
J. Shallit, Hilbert's spacefilling curve described by automatic, regular, and synchronized sequences, arXiv:2106.01062 [cs.FL], June 2 2021.
Index entries for sequences related to coordinates of 2D curves

See also the y-projection, m(3), A059252 as well as A163538, A163540, A163542, A059261, A059285, A163547 and A163528.

C
```
See A059252.
```

Initially [m(0) = 0, m'(0) = 0]; recursion: m(2n + 1) = m(2n).m'(2n).f(m'(2n), 2n).c(m(2n), 2n + 1); m'(2n + 1) = m'(2n).f(m(2n), 2n).f(m(2n), 2n).mir(m'(2n)); m(2n) = m(2n - 1).f(m'(2n - 1), 2n - 1).f(m'(2n - 1), 2n - 1).mir(m(2n - 1)); m'(2n) = m'(2n - 1).m(2n - 1).f(m(2n - 1), 2n - 1).c(m'(2n - 1), 2n); where f(m, n) is the alphabetic morphism i := i + 2^n [example: f(0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, 2) = 4 4 5 5 6 7 7 6 6 7 7 6 5 5 4 4]; c(m, n) is the complementation to 2^n - 1 alphabetic morphism [example: c(0 0 1 1 2 3 3 2 2 3 3 2 1 1 0 0, 3) = 7 7 6 6 5 4 4 5 5 4 4 5 6 6 7 7]; and mir(m) is the mirror operator [example: mir(0 1 1 0 0 0 1 1 2 2 3 3 3 2 2 3) = 3 2 2 3 3 3 2 2 1 1 0 0 0 1 1 0].

a(n) = A025581(A163358(n)) = A002262(A163360(n)) = A059905(A163356(n)).

Extended by Antti Karttunen, Aug 01 2009

A163335 Inverse permutation to A163334.

Original entry on oeis.org

0, 1, 3, 7, 4, 2, 5, 8, 12, 17, 23, 30, 22, 16, 11, 6, 10, 15, 21, 28, 36, 46, 37, 29, 38, 47, 57, 69, 58, 48, 59, 70, 82, 96, 83, 71, 60, 50, 41, 32, 40, 49, 39, 31, 24, 18, 13, 9, 14, 19, 25, 33, 26, 20, 27, 34, 42, 52, 43, 35, 44, 53, 63, 74, 86, 99, 85, 73, 62, 51, 61, 72

Offset: 0

Antti Karttunen, Jul 29 2009

nonn

abs(A025581(a(n+1)) - A025581(a(n))) + abs(A002262(a(n+1)) - A002262(a(n))) = 1 for all n.

Inverse: A163334. a(n) = A163329(A163332(n)). One-based version: A163339. See also A163337, A163358.

A163337 Inverse permutation to A163336.

Original entry on oeis.org

0, 2, 5, 8, 4, 1, 3, 7, 12, 18, 25, 33, 26, 19, 13, 9, 14, 20, 27, 35, 44, 53, 43, 34, 42, 52, 63, 74, 62, 51, 61, 73, 86, 99, 85, 72, 60, 49, 39, 31, 40, 50, 41, 32, 24, 17, 11, 6, 10, 16, 23, 30, 22, 15, 21, 29, 38, 47, 37, 28, 36, 46, 57, 69, 82, 96, 83, 70, 58, 48, 59, 71

Offset: 0

Antti Karttunen, Jul 29 2009

nonn

abs(A025581(a(n+1))-A025581(a(n))) + abs(A002262(a(n+1))-A002262(a(n))) = 1 for all n.

Inverse: A163336. a(n) = A163331(A163332(n)) = A061579(A163335(n)). One-based version: A163341. See also A163335, A163358.

A163360 Inverse permutation to A163359.

Original entry on oeis.org

0, 2, 4, 1, 3, 6, 11, 7, 12, 17, 24, 18, 13, 8, 5, 9, 14, 19, 26, 20, 27, 35, 43, 34, 42, 52, 62, 51, 41, 33, 25, 32, 40, 49, 60, 50, 61, 73, 85, 72, 84, 98, 112, 97, 83, 71, 59, 70, 58, 47, 38, 48, 39, 31, 23, 30, 22, 16, 10, 15, 21, 29, 37, 28, 36, 45, 56, 46, 57, 69, 81

Offset: 0

Antti Karttunen, Jul 29 2009

abs(A025581(a(n+1)) - A025581(a(n))) + abs(A002262(a(n+1)) - A002262(a(n))) = 1 for all n.

Inverse: A163359. a(n) = A061579(A163358(n)). One-based version: A163364.

A166042 Permutation of nonnegative integers: a(n) tells which integer is in the same position in the square array A163334 as where n is located in the array A163357.

Original entry on oeis.org

0, 1, 4, 5, 6, 47, 46, 7, 8, 45, 44, 9, 14, 3, 2, 15, 16, 13, 12, 17, 18, 19, 22, 23, 24, 25, 28, 29, 42, 11, 10, 43, 40, 37, 36, 41, 30, 31, 34, 35, 72, 73, 76, 77, 66, 71, 70, 67, 68, 57, 56, 69, 38, 39, 50, 51, 52, 49, 48, 53, 54, 55, 58, 59, 60, 425, 424, 61, 62, 63, 422

Offset: 0

Antti Karttunen, Oct 06 2009

nonn

			The top left 8 X 8 corner of A163357:
   0  1 14 15 16 19 20 21
   3  2 13 12 17 18 23 22
   4  7  8 11 30 29 24 25
   5  6  9 10 31 28 27 26
  58 57 54 53 32 35 36 37
  59 56 55 52 33 34 39 38
  60 61 50 51 46 45 40 41
  63 62 49 48 47 44 43 42
The top left 9 X 9 corner of A163334:
   0  1  2 15 16 17 18 19 20
   5  4  3 14 13 12 23 22 21
   6  7  8  9 10 11 24 25 26
  47 46 45 44 43 42 29 28 27
  48 49 50 39 40 41 30 31 32
  53 52 51 38 37 36 35 34 33
  54 55 56 69 70 71 72 73 74
  59 58 57 68 67 66 77 76 75
  60 61 62 63 64 65 78 79 80
9 is in position (3,2) in A163357, while A163334(3,2) = 45. Thus a(9) = 45.

Inverse: A166041. a(n) = A163334(A163358(n)) = A163336(A163360(n)). Fixed points: A165465. Cf. also A166044.

A166044 Permutation of nonnegative integers: a(n) tells which integer is in the same position in the square array A163336 as where n is located in the array A163357.

Original entry on oeis.org

0, 5, 4, 1, 2, 15, 14, 3, 8, 9, 44, 45, 46, 7, 6, 47, 48, 49, 52, 53, 54, 59, 58, 55, 56, 57, 68, 69, 38, 51, 50, 39, 40, 41, 36, 37, 70, 67, 66, 71, 72, 77, 76, 73, 34, 35, 30, 31, 28, 25, 24, 29, 42, 43, 10, 11, 12, 13, 16, 17, 18, 23, 22, 19, 20, 141, 140, 21, 26, 27, 134

Offset: 0

Antti Karttunen, Oct 06 2009

nonn

			The top left 8 X 8 corner of A163357:
   0  1 14 15 16 19 20 21
   3  2 13 12 17 18 23 22
   4  7  8 11 30 29 24 25
   5  6  9 10 31 28 27 26
  58 57 54 53 32 35 36 37
  59 56 55 52 33 34 39 38
  60 61 50 51 46 45 40 41
  63 62 49 48 47 44 43 42
The top left 9 X 9 corner of A163336:
   0  5  6 47 48 53 54 59 60
   1  4  7 46 49 52 55 58 61
   2  3  8 45 50 51 56 57 62
  15 14  9 44 39 38 69 68 63
  16 13 10 43 40 37 70 67 64
  17 12 11 42 41 36 71 66 65
  18 23 24 29 30 35 72 77 78
  19 22 25 28 31 34 73 76 79
  20 21 26 27 32 33 74 75 80
12 is in position (1,3) in A163357, while A163336(1,3) = 46. Thus a(12) = 46.

Inverse: A166043. a(n) = A163336(A163358(n)) = A163334(A163360(n)). Fixed points: A165467. Cf. also A166042.

A163362 Inverse permutation to A163361.

Original entry on oeis.org

1, 2, 5, 3, 6, 10, 14, 9, 13, 19, 25, 18, 12, 8, 4, 7, 11, 17, 23, 16, 22, 29, 38, 30, 39, 48, 59, 49, 40, 31, 24, 32, 41, 51, 61, 50, 60, 71, 84, 72, 85, 98, 113, 99, 86, 73, 62, 74, 63, 53, 43, 52, 42, 33, 26, 34, 27, 20, 15, 21, 28, 35, 44, 36, 45, 55, 65, 54, 64, 75, 88

Offset: 1

Antti Karttunen, Jul 29 2009

nonn

Inverse: A163361.

a(n) = A163358(n-1) + 1.

A163908 Inverse permutation to A163907.

Original entry on oeis.org

0, 1, 2, 4, 12, 24, 17, 18, 11, 3, 6, 7, 8, 13, 5, 9, 10, 22, 15, 16, 21, 28, 29, 37, 39, 30, 31, 23, 48, 47, 38, 58, 62, 42, 51, 52, 41, 32, 33, 25, 27, 34, 35, 43, 20, 19, 26, 14, 73, 61, 85, 72, 71, 70, 59, 83, 49, 50, 40, 60, 84, 97, 98, 112, 144, 180, 161, 162, 179

Offset: 0

Antti Karttunen, Sep 19 2009

nonn

Inverse: A163907. a(n) = A054239(A163906(n)) = A163358(A163356(n)). See also A163358, A163918.

cp's OEIS Frontend

A163357 Hilbert curve in N X N grid, starting rightwards from the top-left corner, listed by descending antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A059252 Hilbert's Hamiltonian walk on N X N projected onto x axis: m(3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Formula

Extensions

A059253 Hilbert's Hamiltonian walk on N X N projected onto y axis: m'(3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Formula

Extensions

A163335 Inverse permutation to A163334.

Views

Author

Keywords

Comments

Links

Crossrefs

A163337 Inverse permutation to A163336.

Views

Author

Keywords

Comments

Links

Crossrefs

A163360 Inverse permutation to A163359.

Views

Author

Keywords

Comments

Links

Crossrefs

A166042 Permutation of nonnegative integers: a(n) tells which integer is in the same position in the square array A163334 as where n is located in the array A163357.

Views

Author

Keywords

Examples

Links

Crossrefs

A166044 Permutation of nonnegative integers: a(n) tells which integer is in the same position in the square array A163336 as where n is located in the array A163357.

Views

Author

Keywords

Examples

Links

Crossrefs

A163362 Inverse permutation to A163361.

Views

Author

Keywords

Links

Crossrefs

Formula

A163908 Inverse permutation to A163907.

Views

Author