A163540 -id:A163540 - 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

A163542 The relative direction (0=straight ahead, 1=turn right, 2=turn left) taken by the type I Hilbert's Hamiltonian walk A163357 at the step n.

Original entry on oeis.org

1, 1, 2, 0, 2, 2, 1, 1, 2, 2, 0, 2, 1, 1, 0, 1, 2, 2, 1, 0, 1, 1, 2, 2, 1, 1, 0, 1, 2, 2, 0, 0, 2, 2, 1, 0, 1, 1, 2, 2, 1, 1, 0, 1, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 1, 2, 2, 0, 2, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 2, 1, 1, 0, 1, 2, 2, 0, 2, 1, 1, 2, 0, 2, 2, 1, 1, 2, 2, 0, 2, 1, 1, 0, 0, 1, 1, 2, 0, 2, 2

Offset: 1

Antti Karttunen, Aug 01 2009

nonn

a(16*n) = a(256*n) for all n.

Antti Karttunen, Table of n, a(n) for n = 1..65536

a(n) = A014681(A163543(n)). See also A163540.

HC = {L[n_ /; IntegerQ[n/2]] :> {F[n], L[n], L[n + 1], R[n + 2]},
   R[n_ /; IntegerQ[(n + 1)/2]] :> {F[n], R[n], R[n + 3], L[n + 2]},
   R[n_ /; IntegerQ[n/2]] :> {L[n], R[n + 1], R[n], F[n + 3]},
   L[n_ /; IntegerQ[(n + 1)/2]] :> {R[n], L[n + 3], L[n], F[n + 1]},
   F[n_ /; IntegerQ[n/2]] :> {L[n], R[n + 1], R[n], L[n + 3]},
   F[n_ /; IntegerQ[(n + 1)/2]] :> {R[n], L[n + 3], L[n], R[n + 1]}};
a[1] = L[0]; Map[(a[n_ /; IntegerQ[(n - #)/16]] :=
    Part[Flatten[a[(n + 16 - #)/16] /. HC /. HC], #]) &, Range[16]];
Part[a[#] & /@ Range[4^4] /. {L[] -> 2, R[] -> 1, F[_] -> 0},
2 ;; -1] (* Bradley Klee, Aug 07 2015 *)

(define (A163542 n) (A163241 (modulo (- (A163540 (1+ n)) (A163540 n)) 4)))

a(n) = A163241((A163540(n+1)-A163540(n)) modulo 4).

A163538 The change in X-coordinate when moving from the n-1:th to the n-th term in the type I Hilbert's Hamiltonian walk A163357.

Original entry on oeis.org

0, 1, 0, -1, 0, 0, 1, 0, 1, 0, 1, 0, 0, -1, 0, 1, 1, 0, 1, 0, 1, 1, 0, -1, 0, 1, 0, -1, -1, 0, -1, 0, 0, 0, 1, 0, 1, 1, 0, -1, 0, 1, 0, -1, -1, 0, -1, 0, -1, -1, 0, 1, 0, 0, -1, 0, -1, 0, -1, 0, 0, 1, 0, -1, 0, 0, 1, 0, 1, 1, 0, -1, 0, 1, 0, -1, -1, 0, -1, 0, 0, 1, 0, -1, 0, 0, 1, 0, 1, 0, 1, 0

Offset: 0

Antti Karttunen, Aug 01 2009

sign

A. Karttunen, Table of n, a(n) for n = 0..65536

These are the first differences of A059253. See also: A163539, A163540, A163542.

a(0)=0, a(n) = A059253(n) - A059253(n-1).

A163541 The absolute direction (0=east, 1=south, 2=west, 3=north) taken by the type I Hilbert's Hamiltonian walk A163359 at the step n.

Original entry on oeis.org

1, 0, 3, 0, 0, 1, 2, 1, 0, 1, 2, 2, 3, 2, 1, 1, 0, 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 0, 0, 0, 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 0, 3, 3, 2, 1, 2, 2, 3, 0, 3, 2, 3, 0, 0, 1, 0, 3, 0, 0, 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 0, 0, 1, 0, 3, 0, 0, 1, 2, 1, 0, 1, 2, 2, 3, 2, 1, 1, 1, 0, 3, 0, 0, 1

Offset: 1

Antti Karttunen, Aug 01 2009

nonn

Taking every sixteenth term gives the same sequence: (and similarly for all higher powers of 16 as well): a(n) = a(16*n).

Antti Karttunen, Table of n, a(n) for n = 1..4096

a(n) = A163541(A008598(n)) = A004442(A163540(n)). See also A163543.

HC = {L[n_ /; IntegerQ[n/2]] :> {F[n], L[n], L[n + 1], R[n + 2]},
R[n_ /; IntegerQ[(n + 1)/2]] :> {F[n], R[n], R[n + 3], L[n + 2]},
R[n_ /; IntegerQ[n/2]] :> {L[n], R[n + 1], R[n], F[n + 3]},
L[n_ /; IntegerQ[(n + 1)/2]] :> {R[n], L[n + 3], L[n], F[n + 1]},
F[n_ /; IntegerQ[n/2]] :> {L[n], R[n + 1], R[n], L[n + 3]},
F[n_ /; IntegerQ[(n + 1)/2]] :> {R[n], L[n + 3], L[n], R[n + 1]}};
a[1] = L[0]; Map[(a[n_ /; IntegerQ[(n - #)/16]] := Part[Flatten[a[(n + 16 - #)/16]/.HC/.HC],#]) &, Range[16]];
Part[FoldList[Mod[Plus[#1, #2], 4] &, 0, a[#] & /@ Range[4^4]/.{F[n_]:>0,L[n_]:>1,R[n_]:>-1}], 2 ;; -1] (* Bradley Klee, Aug 07 2015 *)

(define (A163541 n) (modulo (+ 3 (A163538 n) (A163539 n) (abs (A163538 n))) 4))

a(n) = A010873(A163538(n) + A163539(n) + abs(A163538(n)) + 3).

A306287 Irregular triangle T(n,k), 1 <= n, 1 <= k <= (1/6)(4+52^(2*n)), read by rows: T(n,k) determines absolute directions along the perimeter of the n-th Y-type Hilbert Tree.

Original entry on oeis.org

1, 0, 3, 2, 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 2, 1, 2, 1, 0, 1, 2, 2, 3, 2, 1, 1, 0, 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 0, 0, 0, 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 0, 3, 3, 2, 1, 2, 2, 3, 0, 3, 2, 3, 2, 1, 2, 1, 0, 1, 2, 2, 3, 2, 1, 1, 1, 0

Offset: 1

Bradley Klee, Feb 03 2019

The Y-type Hilbert trees are a sequence of polyominoes whose edges, all but one, are segments of the Hilbert curve described by A163540. One extra edge closes a loop around the perimeter (cf. Formula). The first Y-type tree is a monomino with four edges, and the second is the Y hexomino with 14 unit edges. All deeper trees are determined by iteration of replacement rules (cf. linked image "First Six Y-type Trees"). The Y-type Hilbert trees nest along the upper half plane according to the limit-periodic ruler function A001511. Such an arrangement reconstructs the Hilbert curve everywhere away from the ground axis (cf. linked image "Limit-Periodic Construction").

			T(1,k) = 1, 0, 3, 2;
T(2,k) = 1, 2, 1, 1, 0, 3, 0, 1, 0, 3, 3, 2, 3, 2.

Bradley Klee, Limit-Periodic Construction.
Bradley Klee, First Six Y-type Trees.

T-Type Trees: A306288. Cf. A163540, A001511, A246559.

HC = {L[n_ /; EvenQ[n]] :> {F[n], L[n], L[Mod[n + 1, 2]], R[n]},
   R[n_ /; OddQ[n]] :> {F[n], R[n], R[Mod[n + 1, 2]], L[n]},
   R[n_ /; EvenQ[n]] :> {L[n], R[Mod[n + 1, 2]], R[n], F[Mod[n + 1, 2]]},
   L[n_ /; OddQ[n]] :> {R[n], L[Mod[n + 1, 2]], L[n], F[Mod[n + 1, 2]]},
   F[n_ /; EvenQ[n]] :> {L[n], R[Mod[n + 1, 2]], R[n], L[Mod[n + 1, 2]]},
   F[n_ /; OddQ[n]] :> {R[n], L[Mod[n + 1, 2]], L[n], R[Mod[n + 1, 2]]}};
TurnMap = {F[] -> 0, L[] -> 1, R[_] -> -1};
T1ind[1] = 1; T1ind[2] = 2; T1ind[n_] := 5*T1ind[n - 1] - 4*T1ind[n - 2];
T1Vec[n_] := Append[Mod[FoldList[Plus, Flatten[Nest[# /. HC &, F[0],
        n] /. TurnMap][[T1ind[n] ;; -(T1ind[n] + 1)]]], 4], 2]
Flatten[T1Vec /@ Range[5]]

a(n,(1/6)*(4+5*2^(2*n))) = 2;

a(n,k) = A163540( (1/12)*(8+7*2^(2*n)-3*(-1)^n *2^(2*n+1))-1+k ).

A306288 Irregular triangle T(n,k), 1 <= n, 1 <= k <= (2/3)(2+2^(2n)), read by rows: T(n,k) determines absolute directions along the perimeter of the n-th T-type Hilbert Tree.

Original entry on oeis.org

3, 0, 1, 2, 3, 3, 2, 3, 0, 0, 0, 1, 2, 1, 1, 2, 3, 3, 2, 3, 0, 3, 3, 2, 1, 2, 2, 3, 0, 3, 2, 3, 0, 0, 1, 0, 3, 0, 1, 0, 3, 0, 0, 1, 2, 1, 0, 1, 2, 2, 3, 2, 1, 1, 0, 1, 2, 1, 1, 2, 3, 3, 2, 3, 0, 3, 3, 2, 1, 2, 2, 3, 0, 3, 2, 3, 0, 0, 1, 0, 3, 3, 2, 3, 0

Offset: 1

Bradley Klee, Feb 03 2019

The T-type Hilbert trees are a sequence of polyominoes whose edges, all but one, are segments of the Hilbert curve described by A163540. One extra edge closes a loop around the perimeter (cf. Formula). The first T-type tree is a monomino with four edges, and the second is the T pentomino with 12 unit edges. All deeper trees are determined by iteration of replacement rules (cf. linked image "First Six T-type Trees"). The T-type Hilbert trees nest along the upper half plane according to the limit-periodic ruler function A001511. Such an arrangement reconstructs the Hilbert curve everywhere away from the ground axis (cf. linked image "Limit-Periodic Construction").

			T(1,k) = 3, 0, 1, 2;
T(2,k) = 3, 3, 2, 3, 0, 0, 0, 1, 2, 1, 1, 2.

Bradley Klee, Limit-Periodic Construction.
Bradley Klee, First Six T-type Trees.

Y-Type Trees: A306287. Cf. A163540, A001511, A246559.

HC = {L[n_ /; EvenQ[n]] :> {F[n], L[n], L[Mod[n + 1, 2]], R[n]},
   R[n_ /; OddQ[n]] :> {F[n], R[n], R[Mod[n + 1, 2]], L[n]},
   R[n_ /; EvenQ[n]] :> {L[n], R[Mod[n + 1, 2]], R[n], F[Mod[n + 1, 2]]},
   L[n_ /; OddQ[n]] :> {R[n], L[Mod[n + 1, 2]], L[n], F[Mod[n + 1, 2]]},
   F[n_ /; EvenQ[n]] :> {L[n], R[Mod[n + 1, 2]], R[n], L[Mod[n + 1, 2]]},
   F[n_ /; OddQ[n]] :> {R[n], L[Mod[n + 1, 2]], L[n], R[Mod[n + 1, 2]]}};
TurnMap = {F[] -> 0, L[] -> 1, R[_] -> -1};
T2ind[1] = 7; T2ind[2] = 27;T2ind[n_] := 5*T2ind[n - 1] - 4*T2ind[n - 2];
T2Vec[n_] := Append[Mod[ FoldList[Plus, Flatten[Nest[# /. HC &, F[0] /. HC, n] /.
       TurnMap][[T2ind[n] ;; -(T2ind[n] + 1)]]], 4], 2]
Flatten[T2Vec/@Range[5]]

a(n,(2/3)*(2+2^(2*n))) = 2;

a(n,k) = A163540( (1/3)*(1+11*2^(2*n)+3*(-1)^n *2^(2*n+1))-1+k ).

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

A163542 The relative direction (0=straight ahead, 1=turn right, 2=turn left) taken by the type I Hilbert's Hamiltonian walk A163357 at the step n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A163538 The change in X-coordinate when moving from the n-1:th to the n-th term in the type I Hilbert's Hamiltonian walk A163357.

Views

Author

Keywords

Links

Crossrefs

Formula

A163541 The absolute direction (0=east, 1=south, 2=west, 3=north) taken by the type I Hilbert's Hamiltonian walk A163359 at the step n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A306287 Irregular triangle T(n,k), 1 <= n, 1 <= k <= (1/6)*(4+5*2^(2*n)), read by rows: T(n,k) determines absolute directions along the perimeter of the n-th Y-type Hilbert Tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A306288 Irregular triangle T(n,k), 1 <= n, 1 <= k <= (2/3)*(2+2^(2*n)), read by rows: T(n,k) determines absolute directions along the perimeter of the n-th T-type Hilbert Tree.

Views

Author

Keywords

Comments

A306287 Irregular triangle T(n,k), 1 <= n, 1 <= k <= (1/6)(4+52^(2*n)), read by rows: T(n,k) determines absolute directions along the perimeter of the n-th Y-type Hilbert Tree.

A306288 Irregular triangle T(n,k), 1 <= n, 1 <= k <= (2/3)(2+2^(2n)), read by rows: T(n,k) determines absolute directions along the perimeter of the n-th T-type Hilbert Tree.