This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A030109 Write n in binary, reverse bits, subtract 1, divide by 2. 9
 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 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 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.

Last modified March 25 10:31 EDT 2019. Contains 321470 sequences. (Running on oeis4.)