Displaying 1-10 of 18 results found.
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
COMMENTS
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.
PROG
(PARI)
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))));
Hilbert's Hamiltonian walk on N X N projected onto the first diagonal: M(3) (sum of the sequences A059252 and A059253).
+20
6
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
COMMENTS
The interest comes from a simplest recursion than the cross-recursion, dependent on parity, governing the projections onto the x and y axis.
FORMULA
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]
AUTHOR
Claude Lenormand (claude.lenormand(AT)free.fr), Jan 24 2001
Hilbert's Hamiltonian walk projected onto the second diagonal: M'(3) (difference between sequences A059253 and A059252; their sum is A059261).
+20
5
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
FORMULA
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]
EXAMPLE
[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]
CROSSREFS
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.
AUTHOR
Claude Lenormand (claude.lenormand(AT)free.fr), Jan 24 2001
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.
+20
3
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
COMMENTS
This sequence is a self-inverse permutation of the nonnegative integers.
FORMULA
a(n) < 16^k for any n < 16^k.
EXAMPLE
+ +-----+-----+
|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.
PROG
(PARI) See Links section.
Hilbert's Hamiltonian walk on N X N projected onto x axis: m(3).
+10
19
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
COMMENTS
This is the X-coordinate of the n-th term in Hilbert's Hamiltonian walk A163359 and the Y-coordinate of its transpose A163357.
LINKS
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.)
FORMULA
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].
EXAMPLE
[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].
PROG
(C) 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<l; i++){
switch(i>>(2*n)){
case 1: x[i] = y[i&k]; y[i] = x[i&k]+(1<<n); break;
case 2: x[i] = y[i&k]+(1<<n); y[i] = x[i&k]+(1<<n); break;
case 3: x[i] = (2<<n)-1-x[i&k]; y[i] = y[k-i&k]; break;
case 4: n++; k = (1<<(2*n))-1; t=x; x=y; y=t; x[i] = 0; y[i] = 1<<n; break;
(C++) See Fxtbook link.
AUTHOR
Claude Lenormand (claude.lenormand(AT)free.fr), Jan 23 2001
Inverse permutation to A163355, related to Hilbert's curve in N x N grid.
+10
17
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
FORMULA
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]. (End)
PROG
(MIT Scheme:)
(define ( A163356 n) (if (zero? n) n (let* ((i (floor->exact (/ ( A000523 n) 2))) (d (modulo (floor->exact (/ n (expt 4 i))) 4)) (r (modulo n (expt 4 i)))) (+ (* (-1+ (modulo (expt (+ 2 (modulo i 2)) d) 5)) (expt 4 i)) (cond ((= 3 d) (- (expt 4 i) 1 ( A163356 r))) (else ( A057300 ( A163356 r)))))))) (Another, iterative version): (define (A163356v2 n) (let loop ((z 0) (n n) (i 0)) (let ((dd (modulo n 4))) (cond ((zero? n) z) ((= 0 dd) (loop z (floor->exact (/ n 4)) (+ i 2))) ((= 2 dd) (loop (+ (* 3 (expt 2 i)) ( A057300 z)) (floor->exact (/ n 4)) (+ i 2))) ((= 1 dd) (loop (+ (expt 2 (+ i (floor->exact (/ (modulo i 4) 2)))) ( A057300 z)) (floor->exact (/ n 4)) (+ i 2))) (else (loop (+ (expt 2 (+ i (- 1 (floor->exact (/ (modulo i 4) 2))))) (- (expt 2 i) z 1)) (floor->exact (/ n 4)) (+ i 2))))))) (PARI)
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); };
CROSSREFS
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.
EXTENSIONS
Links to further derived sequences and a nicer Scheme function & formula added by Antti Karttunen, Sep 21 2009
The X-coordinate of the n-th point in the Peano curve A163334.
+10
16
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
COMMENTS
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
The Y-coordinate of the n-th point in the Peano curve A163334.
+10
14
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
COMMENTS
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
Divisor-or-multiple permutation of natural numbers constructed from two-dimensional Hilbert curve ( A163357) and Fermi-Dirac primes ( A050376).
+10
12
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
COMMENTS
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.
PROG
(PARI)
up_to_e = 14;
v050376 = vector(up_to_e);
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); };
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))));
CROSSREFS
Cf. A003188, A050376, A052330, A059252, A059253, A064706, A163356, A163357, A207901, A298480, A300012, A302844, A302846, A302783, A303771.
The square of the distance from the origin to the n-th term in the type I Hilbert's Hamiltonian walk A163357.
+10
7
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
Search completed in 0.015 seconds
|