login
Write n in binary, reverse bits, subtract 1, divide by 2.
12

%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