login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

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

REFERENCES

L Ducas, T Prest, Fast Fourier Orthogonalization, Preprint 2015, http://eprint.iacr.org/2015/1014.pdf

LINKS

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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 16 19:44 EDT 2017. Contains 290627 sequences.