|
| |
|
|
A030101
|
|
a(n) is the number produced when n is converted to base 2, reversed and then converted back to base 10.
|
|
82
|
|
|
|
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
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. [From Dylan Hamilton, Aug 04 2010]
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]
For n > 0: a(a(n)) = n iff n is odd; a(A006995(n)) = A006995(n). [Juli Mallett, Nov 11 2010, corrected: Reinhard Zumkeller, Oct 21 2011]
n is binary palindromic iff a(n) = n. [Reinhard Zumkeller, corrected: Jan 17 2012, thanks to Hieronymus Fischer who pointed this out; Oct 21 2011]
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
Row n of A030308 gives the binary digits of a(n), prepended with zero at even positions. - Reinhard Zumkeller, Jun 17 2012
|
|
|
REFERENCES
|
Solutions to 17th USA Mat. Olympiad, Math. Mag., 62 (1989), 210-214 (#3).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..10000
Michael Gilleland, Some Self-Similar Integer Sequences
Wikipedia, van der Corput sequence.
|
|
|
FORMULA
|
a(n) = 0, a(2n) = a(n), a(2n+1) = a(n) + 2^([log2(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) = if n=0 then r else b(floor(n/2), 2*r + n mod 2). [From Reinhard Zumkeller, Mar 03 2010]
|
|
|
EXAMPLE
|
a(100) = 19 because 100 (base 10) = 1100100 (base 2) and R(1100100 (base 2)) = 10011 (base 2) = 19 (base 10)
|
|
|
MATHEMATICA
|
Table[FromDigits[Reverse[IntegerDigits[i, 2]], 2], {i, 0, 80}]
|
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, subst(Polrev(binary(n)), x, 2))
(MAGMA) A030101:=func<n|SequenceToInteger(Reverse(IntegerToSequence(n, 2)), 2)>; // Jason Kimberley, Sep 19 2011
(Haskell)
import Data.List (unfoldr)
a030101 = foldl (\v d -> 2 * v + d) 0 .
unfoldr (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, Oct 21 2011
(Sage)
def A030101(n): return Integer(bin(n).lstrip("0b")[::-1], 2) if n<>0 else 0
[A030101(n) for n in (0..78)] # Peter Luschny, Aug 09 2012
|
|
|
CROSSREFS
|
Cf. A030102 - A030109, A036044, A056539, A004086, A005408.
Cf. A055944 (reverse and add), A178225.
Sequence in context: A106609 A171968 A093474 * A162742 A081432 A136655
Adjacent sequences: A030098 A030099 A030100 * A030102 A030103 A030104
|
|
|
KEYWORD
|
nonn,base,nice
|
|
|
AUTHOR
|
David W. Wilson
|
|
|
STATUS
|
approved
|
| |
|
|
