cp's OEIS Frontend

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

%I A163355 #31 May 14 2025 19:06:42
%S A163355 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,
%T A163355 31,28,24,25,27,26,58,57,59,56,54,53,55,52,60,61,63,62,50,51,49,48,32,
%U A163355 35,33,34,36,37,39,38,46,45,47,44,40,41,43,42,234,235,233,232,236,239
%N A163355 Permutation of integers for constructing Hilbert curve in N x N grid.
%H A163355 Antti Karttunen, <a href="/A163355/b163355.txt">Table of n, a(n) for n = 0..262143</a>
%H A163355 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A163355 a(0) = 0, and given d=1, 2 or 3, then a((d*(4^i))+r)
%F A163355   = (4^i) + a(A057300(r)), if d=1 and i is even, or if d=2 and i is odd
%F A163355   = 2*(4^i) + a(A057300(r)), if d=3,
%F A163355   = 3*(4^i) + a((4^i)-1-r) in other cases.
%F A163355 From _Alan Michael Gómez Calderón_, May 06 2025: (Start)
%F A163355 a(3*A000695(n)) = 2*A000695(n);
%F A163355 a(3*(A000695(n) + 2^A000695(2*m))) = 2*(A000695(n) + 2^A000695(2*m)) for m >= 2;
%F A163355 a((2 + 16^n)*2^(-1 + 4*m)) = 4^(2*(n + m) - 1) + (11*16^m - 2)/3. (End)
%p A163355 A057300 := proc(n)
%p A163355     option remember;
%p A163355     `if`(n=0, 0, procname(iquo(n, 4, 'r'))*4+[0, 2, 1, 3][r+1])
%p A163355 end proc:
%p A163355 A163355 := proc(n)
%p A163355     option remember ;
%p A163355     local d,base4,i,r ;
%p A163355     if n <= 1 then
%p A163355         return n ;
%p A163355     end if;
%p A163355     base4 := convert(n,base,4) ;
%p A163355     d := op(-1,base4) ;
%p A163355     i := nops(base4)-1 ;
%p A163355     r := n-d*4^i ;
%p A163355     if ( d=1 and type(i,even) ) or ( d=2 and type(i,odd)) then
%p A163355         4^i+procname(A057300(r)) ;
%p A163355     elif d= 3 then
%p A163355         2*4^i+procname(A057300(r)) ;
%p A163355     else
%p A163355         3*4^i+procname(4^i-1-r) ;
%p A163355     end if;
%p A163355 end proc:
%p A163355 seq(A163355(n),n=0..100) ; # _R. J. Mathar_, Nov 22 2023
%o A163355 (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)))))))
%o A163355 (PARI)
%o A163355 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); };
%o A163355 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
%Y A163355 Inverse: A163356. A163357 & A163359 give two variants of Hilbert curve in N x N grid. Cf. also A163332.
%Y A163355 Second and third "powers": A163905, A163915.
%Y A163355 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.
%Y A163355 See also: A000695, A163890, A163894, A163902-A163903, A163914, A163485, A302843, A302845.
%K A163355 nonn
%O A163355 0,3
%A A163355 _Antti Karttunen_, Jul 29 2009
%E A163355 Links to further derived sequences added by _Antti Karttunen_, Sep 21 2009