A163355 Permutation of integers for constructing Hilbert curve in N x N grid.

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

Offset

0,3

Links

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

Index entries for sequences that are permutations of the natural numbers

Formula

a(0) = 0,

and given d=1, 2 or 3, then a((d*(4^i))+r)

= (4^i) + a(A057300(r)), if d=1 and i is even, or if d=2 and i is odd

= 2*(4^i) + a(A057300(r)), if d=3,

= 3*(4^i) + a((4^i)-1-r) in other cases.

Maple

A057300 := proc(n)
    option remember;
    `if`(n=0, 0, procname(iquo(n, 4, 'r'))*4+[0, 2, 1, 3][r+1])
end proc:
A163355 := proc(n)
    option remember ;
    local d, base4, i, r ;
    if n <= 1 then
        return n ;
    end if;
    base4 := convert(n, base, 4) ;
    d := op(-1, base4) ;
    i := nops(base4)-1 ;
    r := n-d*4^i ;
    if ( d=1 and type(i, even) ) or ( d=2 and type(i, odd)) then
        4^i+procname(A057300(r)) ;
    elif d= 3 then
        2*4^i+procname(A057300(r)) ;
    else
        3*4^i+procname(4^i-1-r) ;
    end if;
end proc:
seq(A163355(n), n=0..100) ; # R. J. Mathar, Nov 22 2023

Prog

(MIT Scheme:) (define (A163355 n) (let* ((i (floor->exact (/ (A000523 n) 2))) (dd (modulo (floor->exact (/ n (expt 4 i))) 4)) (r (if (zero? n) n (modulo n (expt 4 i))))) (cond ((zero? n) n) ((= 0 dd) (A163355 r)) ((= (+ 1 (modulo i 2)) dd) (+ (expt 4 i) (A163355 (A057300 r)))) ((= 3 dd) (+ (* 2 (expt 4 i)) (A163355 (A057300 r)))) (else (+ (* 3 (expt 4 i)) (A163355 (- (expt 4 i) 1 r)))))))
(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); };
A163355(n) = if(!n, n, my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); if(((1==d)&&!(i%2))||((2==d)&&(i%2)), f+A163355(A057300(r)), if(3==d, f+f+A163355(A057300(r)), (3*f)+A163355(f-1-r)))); \\ Antti Karttunen, Apr 14 2018

Crossrefs

Inverse: A163356. A163357 & A163359 give two variants of Hilbert curve in N x N grid. Cf. also A163332.

Second and third "powers": A163905, A163915.

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.

See also: A163890, A163894, A163902-A163903, A163914, A163485, A302843, A302845.

Sequence in context: A355259 A231183 A324661 * A214885 A145747 A055234

Adjacent sequences: A163352 A163353 A163354 * A163356 A163357 A163358

Keyword

nonn

Author

Antti Karttunen, Jul 29 2009

Extensions

Links to further derived sequences added by Antti Karttunen, Sep 21 2009

Status

approved