A341018 a(n) is the X-coordinate of the n-th point of the space filling curve M defined in Comments section; A341019 gives Y-coordinates.

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

Offset: 0

Author

Rémy Sigrist, Feb 02 2021

Keywords

• nonn

Comments

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

- M_0 corresponds to the points (0, 0), (1, 1) and (2, 0), in that order:

+

/ \

/ \

+ +

O

- for any n >= 0, M_{n+1} is obtained by arranging 4 copies of M_n as follows:

+ . . . + . . . +

. B . B .

+ . . . + . . .

. B . .A C.A C.

. . --> + . . . + . . . +

.A C. .C . A.

+ . . . + . B.B .

O .A . C.

+ . . . + . . . +

O

- for any n >= 0, M_n has A087289(n) points,

- the space filling curve M is the limit of M_{2*n} as n tends to infinity.

The odd bisection of M is similar to a Hilbert's Hamiltonian walk (hence the connection with A059253, see illustration in Links section).

Examples

			The curve M starts as follows:
       11+ 13+   +19 +21
        / \ / \ / \ / \
     10+ 12+ 14+18 +20 +22
        \     / \     /
        9+ 15+   +17 +23
        /     \ /     \
      8+  6+   +   +26 +24
        \ / \ 16  / \ /
        7+  5+   +27 +25
            /     \
          4+       +28
            \     /
        1+  3+   +29 +31
        / \ /     \ / \
      0+  2+       +30 +32
- so a(0) = a(8) = a(10) = 0,
     a(1) = a(7) = a(9) = a(11) = 1.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• F. M. Dekking, Recurrent Sets, Advances in Mathematics, vol. 44, no. 1, 1982.
• Larry Riddle, Space Filling Curve
• Rémy Sigrist, Illustration of M_6
• Rémy Sigrist, Illustration of the connection between the space filling curve M and Hilbert Hamiltonian walk
• Rémy Sigrist, PARI program for A341018
• Index entries for sequences related to coordinates of 2D curves

Crossrefs

Cf. A000695, A059253, A087289, A341019.

Programs

PARI

See Links section.

Formula

a(n) = A341019(n) iff n belongs to A000695.

a(2*n-1) + A341019(2*n-1) = a(2*n) + A341019(2*n) for any n > 0.

a(2*n) - A341019(2*n) = a(2*n+1) - A341019(2*n+1) for any n >= 0.

A059253(n) = (a(2*n+1) - 1)/2.

a(4*n) = 2*A341019(n).

a(16*n) = 4*a(n).