|
| |
|
|
A030109
|
|
Write n in binary, reverse bits, subtract 1, divide by 2.
|
|
14
|
|
|
|
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
|
| |
|
|
