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

Author

David W. Wilson

Keywords

• nonn
• base
• tabf
• look

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

Examples

			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;
  ...
		

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.

Crossrefs

Cf. A030101. A049773 is another version.

Programs

Haskell

a030109 = flip div 2 . subtract 1 . a030101
-- Reinhard Zumkeller, Mar 14 2015

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

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 *)

PARI

a(n) = (fromdigits(Vecrev(binary(n)), 2) - 1)/2; \\ Michel Marcus, Oct 01 2019

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

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

Extensions

More terms from Patrick De Geest, Jun 15 1998