|
| |
|
|
A030101
|
|
a(n) is the number produced when n is converted to binary digits, the binary digits are reversed and then converted back into a decimal number.
|
|
180
|
|
|
|
0, 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 13, 3, 11, 7, 15, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19, 51, 11, 43, 27, 59, 7, 39, 23, 55, 15, 47, 31, 63, 1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
As with decimal reversal, initial zeros are ignored; otherwise, the reverse of 1 would be 1000000... ad infinitum.
Numerators of the binary van der Corput sequence. - Eric Rowland, Feb 12 2008
The number of occasions A030101(n) = A000265(n) before n = 2^k is A053599(k) + 1. For n = 0..2^19, the sequences match less than 1% of the time. - Andrew Woods, May 19 2012
Given any n > 1, the set of numbers A030109(i) = (A030101(i) - 1)/2 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}. This is important in the standard FFT algorithms (starting or ending bit-reversal permutation). - Stanislav Sykora, Mar 15 2012
The binary van der Corput sequence is the infinite sequence of fractions { A030101(n)/A062383(n), n = 0, 1, 2, 3, ... }, and begins 0, 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16, 5/16, 13/16, 3/16, 11/16, 7/16, 15/16, 1/32, 17/32, 9/32, 25/32, 5/32, 21/32, 13/32, 29/32, 3/32, 19/32, 11/32, 27/32, 7/32, 23/32, 15/32, 31/32, 1/64, 33/64, 17/64, 49/64, ... - N. J. A. Sloane, Dec 01 2019
|
|
|
REFERENCES
|
Hlawka E. The theory of uniform distribution. Academic Publishers, Berkhamsted, 1984. See pp. 93, 94 for the van der Corput sequence. - N. J. A. Sloane, Dec 01 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 0, a(2n) = a(n), a(2n+1) = a(n) + 2^(floor(log_2(n)) + 1). For n > 0, a(n) = 2*A030109(n) - 1. - Ralf Stephan, Sep 15 2003
a(n) = b(n, 0) with b(n, r) = r if n = 0, otherwise b(floor(n/2), 2*r + n mod 2). - Reinhard Zumkeller, Mar 03 2010
a(1) = 1, a(3) = 3, a(2n) = a(n), a(4n+1) = 2a(2n+1) - a(n), a(4n+3) = 3a(2n+1) - 2a(n) (as in the Project Euler problem). To prove this, expand the recurrence into binary strings and reversals. - David Applegate, Mar 16 2014, following a posting to the Sequence Fans Mailing List by Martin Møller Skarbiniks Pedersen.
|
|
|
EXAMPLE
|
a(100) = 19 because 100 (base 10) = 1100100 (base 2) and R(1100100 (base 2)) = 10011 (base 2) = 19 (base 10).
|
|
|
MAPLE
|
convert(n, base, 2) ;
ListTools[Reverse](%) ;
add(op(i, %)*2^(i-1), i=1..nops(%)) ;
# second Maple program:
a:= proc(n) local m, r; m:=n; r:=0;
while m>0 do r:=r*2+irem(m, 2, 'm') od; r
end:
|
|
|
MATHEMATICA
|
Table[FromDigits[Reverse[IntegerDigits[i, 2]], 2], {i, 0, 80}]
bitRev[n_] := Switch[Mod[n, 4], 0, bitRev[n/2], 1, 2 bitRev[(n + 1)/2] - bitRev[(n - 1)/4], 2, bitRev[n/2], 3, 3 bitRev[(n - 1)/2] - 2 bitRev[(n - 3)/4]]; bitRev[0] = 0; bitRev[1] = 1; bitRev[3] = 3; Array[bitRev, 80, 0] (* Robert G. Wilson v, Mar 18 2014 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, subst(Polrev(binary(n)), x, 2))
(PARI) a(n) = fromdigits(Vecrev(binary(n)), 2); \\ Michel Marcus, Nov 10 2017
(Magma) A030101:=func<n|SequenceToInteger(Reverse(IntegerToSequence(n, 2)), 2)>; // Jason Kimberley, Sep 19 2011
(Haskell)
a030101 = f 0 where
f y 0 = y
f y x = f (2 * y + b) x' where (x', b) = divMod x 2
(Sage)
def A030101(n): return Integer(bin(n).lstrip("0b")[::-1], 2) if n!=0 else 0
(Python)
def a(n): return int(bin(n)[2:][::-1], 2) # Indranil Ghosh, Apr 24 2017
(Scala) (0 to 127).map(n => Integer.parseInt(Integer.toString(n, 2).reverse, 2)) // Alonso del Arte, Feb 11 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
