A163356 -id:A163356 - cp's OEIS frontend

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

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

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))).

Original entry on oeis.org

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)).

A163358 Inverse permutation to A163357.

Original entry on oeis.org

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

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: A163357. a(n) = A054239(A163356(n)). One-based version: A163362. See also A163334 and A163336.

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

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.

A163918 Inverse permutation to A163917.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 19 2009

nonn

Inverse: A163917. a(n) = A054239(A163916(n)) = A163908(A163356(n)). See also A163358, A163908.

cp's OEIS Frontend

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

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

A163358 Inverse permutation to A163357.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A163908 Inverse permutation to A163907.

Views

Author

Keywords

Links

Crossrefs

A163918 Inverse permutation to A163917.

Views

Author

Keywords

Links

Crossrefs