The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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 April 15 02:27 EDT 2021. Contains 342974 sequences. (Running on oeis4.)