login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 138

%I

%S 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,

%T 23,15,31,1,33,17,49,9,41,25,57,5,37,21,53,13,45,29,61,3,35,19,51,11,

%U 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

%N 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.

%C As with decimal reversal, initial zeros are ignored; otherwise, the reverse of 1 would be 1000000... ad infinitum.

%C Numerators of the binary van der Corput sequence. - _Eric Rowland_, Feb 12 2008

%C It seems that in most cases A030101(x) = A000265(x) and that if A030101(x) <> A000265(x), the next time A030101(y) = A000265(x), A030101(x) = A000265(y). Also, it seems that if a pair of values exist at one index, they will exist at any index where one of them 101/A062383(n), n >= 0}exist. It also seems like the greater of the pair always shows up on A000265 first. - _Dylan Hamilton_, Aug 04 2010

%C 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

%C For n > 0: a(a(n)) = n if and only if n is odd; a(A006995(n)) = A006995(n). - _Juli Mallett_, Nov 11 2010, corrected: _Reinhard Zumkeller_, Oct 21 2011

%C n is binary palindromic if and only if a(n) = n. - _Reinhard Zumkeller_, corrected: Jan 17 2012, thanks to _Hieronymus Fischer_, who pointed this out; Oct 21 2011

%C 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

%C Row n of A030308 gives the binary digits of a(n), prepended with zero at even positions. - _Reinhard Zumkeller_, Jun 17 2012

%C The binary van der Corput sequence is the infinite sequence of fractions { A030101(n)/A62383(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

%D 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

%H T. D. Noe, <a href="/A030101/b030101.txt">Table of n, a(n) for n = 0..10000</a>

%H Harold L. Dorwart, <a href="http://www.jstor.org/stable/2689936">Seventeenth annual USA Mathematical Olympiads</a>, Math. Mag., 62 (1989), 210-214 (#3).

%H Bernd Fischer and Lothar Reichel, <a href="https://doi.org/10.1090/S0025-5718-1989-0969487-3">Newton interpolation in Fejér and Chebyshev points</a>, Mathematics of Computation 53.187 (1989): 265-278. See pp. 266, 267 for the van der Corput sequence. - _N. J. A. Sloane_, Dec 01 2019

%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>

%H Project Euler, <a href="https://projecteuler.net/problem=463">Problem 463: A weird recurrence relation</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Van_der_Corput_sequence">van der Corput sequence</a>.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F 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

%F 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

%F 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.

%F Conjecture: a(n) = 2*w(n) - 2*w(A053645(n)) - 1 for n > 0, where w = A264596. - _Velin Yanev_, Sep 12 2017

%e a(100) = 19 because 100 (base 10) = 1100100 (base 2) and R(1100100 (base 2)) = 10011 (base 2) = 19 (base 10).

%p A030101 := proc(n)

%p convert(n,base,2) ;

%p ListTools[Reverse](%) ;

%p add(op(i,%)*2^(i-1),i=1..nops(%)) ;

%p end proc: # _R. J. Mathar_, Mar 10 2015

%p # second Maple program:

%p a:= proc(n) local m, r; m:=n; r:=0;

%p while m>0 do r:=r*2+irem(m, 2, 'm') od; r

%p end:

%p seq(a(n), n=0..80); # _Alois P. Heinz_, Nov 17 2015

%t Table[FromDigits[Reverse[IntegerDigits[i, 2]], 2], {i, 0, 80}]

%t 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 *)

%o (PARI) a(n)=if(n<1,0,subst(Polrev(binary(n)),x,2))

%o (PARI) a(n) = fromdigits(Vecrev(binary(n)), 2); \\ _Michel Marcus_, Nov 10 2017

%o (MAGMA) A030101:=func<n|SequenceToInteger(Reverse(IntegerToSequence(n,2)),2)>; // _Jason Kimberley_, Sep 19 2011

%o (Haskell)

%o a030101 = f 0 where

%o f y 0 = y

%o f y x = f (2 * y + b) x' where (x', b) = divMod x 2

%o -- _Reinhard Zumkeller_, Mar 18 2014, Oct 21 2011

%o (Sage)

%o def A030101(n): return Integer(bin(n).lstrip("0b")[::-1],2) if n!=0 else 0

%o [A030101(n) for n in (0..78)] # _Peter Luschny_, Aug 09 2012

%o (Python)

%o def a(n): return int(bin(n)[2:][::-1], 2) # _Indranil Ghosh_, Apr 24 2017

%o (J) ([: #. [: |. #:)"0 NB. _Stephen Makdisi_, May 07 2018

%o (Scala) (0 to 127).map(n => Integer.parseInt(Integer.toString(n, 2).reverse, 2)) // _Alonso del Arte_, Feb 11 2020

%Y Cf. A030102 - A030109, A036044, A004086, A005408.

%Y Cf. A055944 (reverse and add), A178225, A273258.

%Y Cf. A056539, A057889 (bijective variants).

%K nonn,base,nice,hear,look

%O 0,4

%A _David W. Wilson_

%E Edits (including correction of an erroneous date pointed out by _J. M. Bergot_) by _Jon E. Schoenfield_, Mar 16 2014

%E Name clarified by _Antti Karttunen_, Nov 09 2017

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 10:24 EDT 2020. Contains 337264 sequences. (Running on oeis4.)