login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A030109 Write n in binary, reverse bits, subtract 1, divide by 2. 12
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 (list; graph; refs; listen; history; text; internal format)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 02:56 EDT 2020. Contains 335436 sequences. (Running on oeis4.)