A030101 - OEIS

%I #196 Jun 20 2024 07:59:50

%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 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)/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

%C Record highs occur at n = A209492(m) (for n>=1) with values a(n) = A224195(m) (for n>=3). - _Bill McEachen_, Aug 02 2023

%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 Sean Anderson, <a href="http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious">Bit Twiddling Hacks</a>, for fixed-width reversals.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.14 Reversing the bits of a word, page 33.

%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 E. Hlawka, <a href="https://archive.org/details/theoryofuniformd0000hlaw">The theory of uniform distribution</a>. Academic Publishers, Berkhamsted, 1984. See pp. 93, 94 for the van der Corput sequence. - _N. J. A. Sloane_, Dec 01 2019

%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), A224195, A209492.

%K nonn,base,frac,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