|
%I #191 Aug 17 2023 09:10:58
%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)/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,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
|
