A059252 -id:A059252 - cp's OEIS frontend

A302846 Interleave the Gray-coded X and Y-coordinates of 2-dimensional Hilbert's curve in alternate bit-positions: a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

0, 1, 3, 2, 10, 8, 9, 11, 15, 13, 12, 14, 6, 7, 5, 4, 20, 22, 23, 21, 17, 16, 18, 19, 27, 26, 24, 25, 29, 31, 30, 28, 60, 62, 63, 61, 57, 56, 58, 59, 51, 50, 48, 49, 53, 55, 54, 52, 36, 37, 39, 38, 46, 44, 45, 47, 43, 41, 40, 42, 34, 35, 33, 32, 160, 162, 163, 161, 165, 164, 166, 167, 175, 174, 172, 173, 169, 171, 170, 168, 136

Offset: 0

Antti Karttunen, Apr 14 2018

Like in binary Gray code A003188, also in this permutation the binary expansions of a(n) and a(n+1) differ always by just a single bit-position, that is, A000120(A003987(a(n),a(n+1))) = 1 for all n >= 0. Here A003987 computes bitwise-XOR of its two arguments.

When composed with A052330 this gives A302781.

Cf. A302845 (inverse permutation).
Cf. A000695, A302844, A057300, A059252, A059253, A064706, A163356, A302781.
Cf. also A003188, A163252, A300838 for other permutations satisfying the same condition.

A064706(n) = bitxor(n, n>>2);
A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n,n,my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d,f-1-A163356(r),A057300(A163356(r))));
A302846(n) = A064706(A163356(n));

a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

a(n) = A064706(A163356(n)) = A003188(A302844(n)).

A059261 Hilbert's Hamiltonian walk on N X N projected onto the first diagonal: M(3) (sum of the sequences A059252 and A059253).

Original entry on oeis.org

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

Offset: 0

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

nonn

The interest comes from a simplest recursion than the cross-recursion, dependent on parity, governing the projections onto the x and y axis.

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

Cf. the x-projection m(3), A059252 and the y-projection m'(3), A059253. See also: A163530, A059285, A163547.

Initially, M(0)=0; recursion: M(n+1)=M(n).f(M(n), n).f(M(n), n+1).d(M(n), n); -f(m, n) is the alphabetic morphism i := i+2^n; [example: f(0 1 2 1 2 3 4 3 4 5 6 5 4 3 2 3, 2)=4 5 6 5 6 7 8 7 8 9 10 9 8 7 6 7 ] -d(m, n) is the complementation to 2^(n-1)*3-2, alphabetic morphism; [example: d(0 1 2 1 2 3 4 3 4 5 6 5 4 3 2 3, 3)=10 9 8 9 8 7 6 7 6 5 4 5 6 7 8 7] Here is M(3). [M(1)=0.1.2.1, M(2)=0 1 2 1.2 3 4 3.4 5 6 5.4 3 2 3]

Extended by Antti Karttunen, Aug 01 2009

A059285 Hilbert's Hamiltonian walk projected onto the second diagonal: M'(3) (difference between sequences A059253 and A059252; their sum is A059261).

Original entry on oeis.org

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

Offset: 0

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

sign

			[M'(0)=0, M'(1)=0 1 0 -1, M'(2)=0 1 0 -1 -2 -3 -2 -1 0 -1 0 1 2 1 2 3]

The x-projection m(3) is A059253, the y-projection m(3) is A059252 and the projection onto the first diagonal, M(3), is A059261.

Initially, M'(0)=0; recursion: M'(2n)=M'(2n-1). (-f(-M'(2n-1), 2n-1)).(-M'(2n-1)).f(M'(2n-1), 2n-1), M'(2n+1)=M'(2n).f(M'(2n), 2n).(-M'(2n)).(-(f(-M'(2n), 2n+1)). f(m, n) is the complementation to 2^n, [example: f(4 3 4 5 6 7 6 5 4 5 4 6 2 3 2 1, 3)=4 5 4 3 2 1 2 3 4 3 4 5 6 5 6 7]; (-m) is the opposite[example: m=4 5 4 3 2 1 2 3 4 3 4 5 6 5 6 7, (-m)=-4 -5 -4 -3 -2 -1 -2 -3 -4 -3 -4 -5 -6 -5 -6 -7] [Corrected by Sean A. Irvine, Sep 17 2022]

A342217 The n-th and a(n)-th points of the Hilbert's Hamiltonian walk (A059252, A059253) are symmetrical with respect to the line X=Y.

Original entry on oeis.org

0, 3, 2, 1, 14, 15, 12, 13, 8, 11, 10, 9, 6, 7, 4, 5, 58, 57, 56, 59, 60, 63, 62, 61, 50, 49, 48, 51, 52, 55, 54, 53, 32, 35, 34, 33, 46, 47, 44, 45, 40, 43, 42, 41, 38, 39, 36, 37, 26, 25, 24, 27, 28, 31, 30, 29, 18, 17, 16, 19, 20, 23, 22, 21, 234, 235, 232

Offset: 0

Rémy Sigrist, Mar 05 2021

nonn

In other words, a(n) is the unique k such that A059252(n) = A059253(k) and A059253(n) = A059252(k).

This sequence is a self-inverse permutation of the nonnegative integers.

			The Hilbert's Hamiltonian walk (A059252, A059253) begins as follows:
     +     +-----+-----+
     |15   |12    11   |10
     |     |           |
     +-----+     +-----+
      14    13   |8     9
                 |
     +-----+     +-----+
     |1    |2     7    |6
     |     |           |
     +     +-----+-----+
      0     3     4     5
- so a(0) = 0,
     a(1) = 3,
     a(2) = 2,
     a(4) = 14,
     a(5) = 15,
     a(7) = 13,
     a(8) = 8,
     a(9) = 11,
     a(10) = 10.

Rémy Sigrist, Table of n, a(n) for n = 0..4095
Rémy Sigrist, PARI program for A342217
Index entries for sequences that are permutations of the nonnegative integers

See A342218 and A342224 for similar sequences.

Cf. A059252, A059253, A062880.

PARI
```
See Links section.
```

a(n) = n iff n belongs to A062880.

a(n) < 16^k for any n < 16^k.

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

A163356 Inverse permutation to A163355, related to Hilbert's curve in N x N grid.

Original entry on oeis.org

0, 1, 3, 2, 8, 10, 11, 9, 12, 14, 15, 13, 7, 6, 4, 5, 16, 18, 19, 17, 20, 21, 23, 22, 28, 29, 31, 30, 27, 25, 24, 26, 48, 50, 51, 49, 52, 53, 55, 54, 60, 61, 63, 62, 59, 57, 56, 58, 47, 46, 44, 45, 39, 37, 36, 38, 35, 33, 32, 34, 40, 41, 43, 42, 128, 130, 131, 129, 132, 133

Offset: 0

Antti Karttunen, Jul 29 2009

nonn

Inverse: A163355.
Second and third "powers": A163906, A163916. See also A059252-A059253.
In range [A000302(n-1)..A024036(n)] of this permutation, the number of cycles is given by A163910, number of fixed points seems to be given by A147600(n-1) (fixed points themselves: A163901). Max. cycle sizes is given by A163911 and LCM's of all cycle sizes by A163912.
Cf. A059252, A059253, A059905, A059906.
Cf. also A302844, A302846, A302781.

A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n,n,my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d,f-1-A163356(r),A057300(A163356(r)))); \\ Antti Karttunen, Apr 14 2018

a(0) = 0, and provided that d=1, 2 or 3, then a((d*(4^i))+r) = (((2+(i mod 2))^d mod 5)-1) * [either A024036(i) - a(r), if d is 3, and A057300(a(r)) in other cases].
From Antti Karttunen, Apr 14 2018: (Start)
A059905(a(n)) = A059253(n).
A059906(a(n)) = A059252(n).
a(n) = A000695(A059253(n)) + 2*A000695(A059252(n)).
(End)

Links to further derived sequences and a nicer Scheme function & formula added by Antti Karttunen, Sep 21 2009

A163528 The X-coordinate of the n-th point in the Peano curve A163334.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 01 2009

nonn

There is a 2-state automaton that accepts exactly those pairs (n,a(n)) where n is represented in base 9 and a(n) in base 3; see accompanying file a163528.pdf - Jeffrey Shallit, Aug 10 2023

Antti Karttunen, Table of n, a(n) for n = 0..59048
Jeffrey Shallit, Automaton for A163528
Index entries for sequences related to coordinates of 2D curves

Cf. A025581, A163335, A002262, A163337, A163325, A163332.

See also: A059252, A059253, A163529, A163530, A163531, A163532.

a(n) = A025581(A163335(n)) = A002262(A163337(n)) = A163325(A163332(n)).

Name corrected by Kevin Ryde, Aug 28 2020

A163529 The Y-coordinate of the n-th point in the Peano curve A163334.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 01 2009

There is a 2-state automaton that accepts exactly those pairs (n,a(n)) where n is represented in base 9 and a(n) in base 3; see accompanying file a163529.pdf. - Jeffrey Shallit, Aug 10 2023

Antti Karttunen, Table of n, a(n) for n = 0..59048
Jeffrey Shallit, Automaton for A163529
Index entries for sequences related to coordinates of 2D curves

Cf. A002262, A163335, A025581, A163337, A163326, A163332.

Cf. A059252, A059253, A163528, A163530, A163531, A163533.

a(n) = A002262(A163335(n)) = A025581(A163337(n)) = A163326(A163332(n)).

Name corrected by Kevin Ryde, Aug 28 2020

A302781 Divisor-or-multiple permutation of natural numbers constructed from two-dimensional Hilbert curve (A163357) and Fermi-Dirac primes (A050376).

Original entry on oeis.org

1, 2, 6, 3, 15, 5, 10, 30, 120, 40, 20, 60, 12, 24, 8, 4, 28, 84, 168, 56, 14, 7, 21, 42, 210, 105, 35, 70, 280, 840, 420, 140, 1260, 3780, 7560, 2520, 630, 315, 945, 1890, 378, 189, 63, 126, 504, 1512, 756, 252, 36, 72, 216, 108, 540, 180, 360, 1080, 270, 90, 45, 135, 27, 54, 18, 9, 117, 351, 702, 234, 936, 468

Offset: 0

Antti Karttunen, Apr 14 2018

nonn

Note that the starting offset is 0, to align with A052330 and A207901.
Shares with A064736, A207901, A298480, A302350, A302783, A303771, etc. the property that a(n) is either a divisor or a multiple of a(n+1). Permutations satisfying such property are called "divisor-or-multiple permutations" in the OEIS, although Mazet & Saias call them "chain permutations" in their paper. [Edited by Antti Karttunen, Aug 26 2018]
One way to construct such permutations is by composing A052330 from the right with any such permutation like A003188 or A302846 where the binary expansions of a(n) and a(n+1) always differ by just a single bit-position.
Further permutations satisfying the same condition could be constructed from higher-dimensional versions (i.e., greater than 2) of Hilbert's space-filling curves, where the coordinates of each dimension would be Gray coded separately and then interleaved together. Permutation A207901 is essentially a one-dimensional variant of the same idea, while this is constructed from the 2-dimensional curve A163357, which is a Hamiltonian path on N X N grid.
See Peter Munn's A300012 for another idea for constructing such a permutation. - Antti Karttunen, Aug 26 2018

Antti Karttunen, Table of n, a(n) for n = 0..16383
Pierre Mazet and Eric Saias, Etude du graphe divisoriel 4, arXiv:1803.10073 [math.NT], 2018.
Various, Discussion on SeqFan-list, April 2018.
Index entries for sequences that are permutations of the natural numbers

Cf. A302782 (inverse).

Cf. A003188, A050376, A052330, A059252, A059253, A064706, A163356, A163357, A207901, A298480, A300012, A302844, A302846, A302783, A303771.

up_to_e = 14;
v050376 = vector(up_to_e);
A050376(n) = v050376[n];
ispow2(n) = (n && !bitand(n,n-1));
i = 0; for(n=1,oo,if(ispow2(isprimepower(n)), i++; v050376[i] = n); if(i == up_to_e,break));
A052330(n) = { my(p=1,i=1); while(n>0, if(n%2, p *= A050376(i)); i++; n >>= 1); (p); };
A064706(n) = bitxor(n, n>>2);
A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n,n,my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d,f-1-A163356(r),A057300(A163356(r))));
A302781(n) = A052330(A064706(A163356(n)));

a(n) = A052330(A302846(n)), where A302846(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

a(n) = A207901(A302844(n)) = A052330(A064706(A163356(n))).

Name edited by Antti Karttunen, Aug 26 2018

A163547 The square of the distance from the origin to the n-th term in the type I Hilbert's Hamiltonian walk A163357.

Original entry on oeis.org

0, 1, 2, 1, 4, 9, 10, 5, 8, 13, 18, 13, 10, 5, 4, 9, 16, 17, 26, 25, 36, 49, 50, 37, 40, 53, 58, 45, 34, 29, 20, 25, 32, 41, 50, 41, 52, 65, 74, 61, 72, 85, 98, 85, 74, 61, 52, 65, 58, 53, 40, 45, 34, 25, 20, 29, 26, 17, 16, 25, 36, 37, 50, 49, 64, 81, 82, 65, 68, 73, 90, 85

Offset: 0

Antti Karttunen, Aug 01 2009

nonn

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

cp's OEIS Frontend

A302846 Interleave the Gray-coded X and Y-coordinates of 2-dimensional Hilbert's curve in alternate bit-positions: a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A059261 Hilbert's Hamiltonian walk on N X N projected onto the first diagonal: M(3) (sum of the sequences A059252 and A059253).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A059285 Hilbert's Hamiltonian walk projected onto the second diagonal: M'(3) (difference between sequences A059253 and A059252; their sum is A059261).

Views

Author

Keywords

Examples

Crossrefs

Formula

A342217 The n-th and a(n)-th points of the Hilbert's Hamiltonian walk (A059252, A059253) are symmetrical with respect to the line X=Y.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A163356 Inverse permutation to A163355, related to Hilbert's curve in N x N grid.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A163528 The X-coordinate of the n-th point in the Peano curve A163334.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A163529 The Y-coordinate of the n-th point in the Peano curve A163334.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A302781 Divisor-or-multiple permutation of natural numbers constructed from two-dimensional Hilbert curve (A163357) and Fermi-Dirac primes (A050376).

Views

Author