|
%I #54 May 27 2024 15:29:47
%S 0,0,1,0,2,1,3,0,4,2,6,1,5,3,7,0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15,
%T 0,16,8,24,4,20,12,28,2,18,10,26,6,22,14,30,1,17,9,25,5,21,13,29,3,19,
%U 11,27,7,23,15,31,0,32,16,48,8,40,24,56,4,36,20,52,12,44,28,60,2,34,18,50
%N Write n in binary, reverse bits, subtract 1, divide by 2.
%C The sequence divides naturally into blocks of length 2^k, k = 0, 1, 2, ... On block k, let n go from 0 to 2^k-1, write n in binary using k bits and reverse the bits. - _N. J. A. Sloane_, Jun 11 2002
%C For example: the 3-bit strings are 000, 001, 010, 011, 100, 101, 110 and 111. When they are bit-reversed, we get 000, 100, 010, 110, 001, 101, 011, 111. Or, in decimal representation 0,4,2,6,1,5,3,7.
%C In other words: Given any n>1, the set of numbers A030109[i] for indexes i ranging from 2^n to 2^(n+1)-1 is a permutation of the set of consecutive integers {0,1,2,...,2^n-1}. Example: for n=2, we have the permutation of {0,2,1,3} of {0,1,2,3} This is important in the standard FFT algorithms requiring a starting (or ending) bit-reversal permutation of indices. - _Stanislav Sykora_, Mar 15 2012
%H Alois P. Heinz, <a href="/A030109/b030109.txt">Table of n, a(n) for n = 1..8191</a>
%H L. Ducas, T. Prest, <a href="https://ia.cr/2015/1014">Fast Fourier Orthogonalization</a>, IACR, Report 2015/1014, 2015-2016.
%F a(n) = A059893(n) - A053644(n). If 2*2^k<= n<3*2^k then a(n) = 2*a(n-2^k); if 3*2^k<= n<4*2^k then a(n) = 1+ a(n-2^k) starting with a(1) = 0. - _Henry Bottomley_, Sep 13 2001
%F a(2n) = a(n), a(2n+1) = a(n) + 2^[log_2(n)]. - _Ralf Stephan_, Aug 22 2003
%F a(2^m*(2*A072758(n)+1)) = n for m and n >= 0. - _Yosu Yurramendi_, Jan 24 2015
%e As an irregular triangle, first few rows are:
%e 0;
%e 0,1;
%e 0,2,1,3;
%e 0,4,2,6,1,5,3,7;
%e 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15;
%e ...
%p a:= proc(n) option remember; local r; `if`(n<3, 0,
%p `if`(irem(n, 2, 'r')=0, a(r), a(r) +2^ilog2(r)))
%p end:
%p seq(a(n), n=1..127); # _Alois P. Heinz_, Oct 08 2012
%t Table[(FromDigits[Reverse[IntegerDigits[n,2]],2]-1)/2,{n,90}] (* _Harvey P. Dale_, Oct 26 2013 *)
%o (R)
%o maxrow <- 10 # by choice
%o a <- 0
%o for(m in 0:maxrow) for(k in 0:(2^m-1)) {
%o a[2^(m+1)+ k] <- 2*a[2^m+k]
%o a[2^(m+1)+2^m+k] <- a[2^(m+1)+k]+1
%o }
%o a
%o # _Yosu Yurramendi_, Jan 24 2015
%o (Haskell)
%o a030109 = flip div 2 . subtract 1 . a030101
%o -- _Reinhard Zumkeller_, Mar 14 2015
%o (PARI) a(n) = (fromdigits(Vecrev(binary(n)), 2) - 1)/2; \\ _Michel Marcus_, Oct 01 2019
%o (MATLAB) % To get the irregular triangle
%o function T = ITriang(rows)
%o T = cell(rows, 1);
%o T{1} = [0];
%o for r = 1:rows - 1;
%o T{r + 1} = [2*T{r} (2*T{r} + 1)];
%o end
%o end
%o % _Miguel Vargas_, May 04 2024
%Y Cf. A030101. A049773 is another version.
%K nonn,base,tabf,look
%O 1,5
%A _David W. Wilson_
%E More terms from _Patrick De Geest_, Jun 15 1998
|
