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

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, 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, 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

Offset

1,5

Comments

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

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.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..8191

L. Ducas, T. Prest, Fast Fourier Orthogonalization, IACR, Report 2015/1014, 2015-2016.

Formula

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

a(2n) = a(n), a(2n+1) = a(n) + 2^[log_2(n)]. - Ralf Stephan, Aug 22 2003

a(2^m*(2*A072758(n)+1)) = n for m and n >= 0. - Yosu Yurramendi, Jan 24 2015

Example

As an irregular triangle, first few rows are:
  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;
  ...

Maple

a:= proc(n) option remember; local r; `if`(n<3, 0,
      `if`(irem(n, 2, 'r')=0, a(r), a(r) +2^ilog2(r)))
    end:
seq(a(n), n=1..127);  # Alois P. Heinz, Oct 08 2012

Mathematica

Table[(FromDigits[Reverse[IntegerDigits[n, 2]], 2]-1)/2, {n, 90}] (* Harvey P. Dale, Oct 26 2013 *)

Prog

(R)
maxrow <- 10 # by choice
a <- 0
for(m in 0:maxrow) for(k in 0:(2^m-1)) {
  a[2^(m+1)+    k] <- 2*a[2^m+k]
  a[2^(m+1)+2^m+k] <-   a[2^(m+1)+k]+1
}
a
# Yosu Yurramendi, Jan 24 2015
(Haskell)
a030109 = flip div 2 . subtract 1 . a030101
-- Reinhard Zumkeller, Mar 14 2015
(PARI) a(n) = (fromdigits(Vecrev(binary(n)), 2) - 1)/2; \\ Michel Marcus, Oct 01 2019
(MATLAB) % To get the irregular triangle
function T = ITriang(rows)
  T = cell(rows, 1);
  T{1} = [0];
  for r = 1:rows - 1;
    T{r + 1} = [2*T{r} (2*T{r} + 1)];
  end
end
% Miguel Vargas, May 04 2024

Crossrefs

Cf. A030101. A049773 is another version.

Sequence in context: A108202 A025480 A088002 * A208571 A264520 A058208

Adjacent sequences: A030106 A030107 A030108 * A030110 A030111 A030112

Keyword

nonn,base,tabf,look

Author

David W. Wilson

Extensions

More terms from Patrick De Geest, Jun 15 1998

Status

approved