A224195 -id:A224195 - cp's OEIS frontend

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.

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

Offset: 0

David W. Wilson

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. - 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 if and only if n is odd; a(A006995(n)) = A006995(n). - Juli Mallett, Nov 11 2010, corrected: Reinhard Zumkeller, Oct 21 2011
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
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
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
Record highs occur at n = A209492(m) (for n>=1) with values a(n) = A224195(m) (for n>=3). - Bill McEachen, Aug 02 2023

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

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

T. D. Noe, Table of n, a(n) for n = 0..10000
Sean Anderson, Bit Twiddling Hacks, for fixed-width reversals.
Joerg Arndt, Matters Computational (The Fxtbook), section 1.14 Reversing the bits of a word, page 33.
Harold L. Dorwart, Seventeenth annual USA Mathematical Olympiads, Math. Mag., 62 (1989), 210-214 (#3).
Bernd Fischer and Lothar Reichel, Newton interpolation in Fejér and Chebyshev points, 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
Michael Gilleland, Some Self-Similar Integer Sequences
E. Hlawka, 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
Project Euler, Problem 463: A weird recurrence relation
Wikipedia, van der Corput sequence.
Index entries for sequences related to binary expansion of n

Cf. A030102 - A030109, A036044, A004086, A005408.
Cf. A055944 (reverse and add), A178225, A273258.
Cf. A056539, A057889 (bijective variants), A224195, A209492.

a030101 = f 0 where
   f y 0 = y
   f y x = f (2 * y + b) x'  where (x', b) = divMod x 2
-- Reinhard Zumkeller, Mar 18 2014, Oct 21 2011

([: #. [: |. #:)"0 NB. Stephen Makdisi, May 07 2018

A030101:=func; // Jason Kimberley, Sep 19 2011

A030101 := proc(n)
    convert(n,base,2) ;
    ListTools[Reverse](%) ;
    add(op(i,%)*2^(i-1),i=1..nops(%)) ;
end proc: # R. J. Mathar, Mar 10 2015
# 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:
seq(a(n), n=0..80);  # Alois P. Heinz, Nov 17 2015

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

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

a(n) = fromdigits(Vecrev(binary(n)), 2); \\ Michel Marcus, Nov 10 2017

def a(n): return int(bin(n)[2:][::-1], 2) # Indranil Ghosh, Apr 24 2017

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

(0 to 127).map(n => Integer.parseInt(Integer.toString(n, 2).reverse, 2)) // Alonso del Arte, Feb 11 2020

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.
Conjecture: a(n) = 2*w(n) - 2*w(A053645(n)) - 1 for n > 0, where w = A264596. - Velin Yanev, Sep 12 2017

Edits (including correction of an erroneous date pointed out by J. M. Bergot) by Jon E. Schoenfield, Mar 16 2014

Name clarified by Antti Karttunen, Nov 09 2017

A209492 a(0)=1; for n >= 1, let k = floor((1 + sqrt(8*n-7))/2), m = n - (k^2 - k+2)/2. Then a(n) = 2^k + 2^(m+1) - 1.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 15, 17, 19, 23, 31, 33, 35, 39, 47, 63, 65, 67, 71, 79, 95, 127, 129, 131, 135, 143, 159, 191, 255, 257, 259, 263, 271, 287, 319, 383, 511, 513, 515, 519, 527, 543, 575, 639, 767, 1023, 1025, 1027, 1031, 1039, 1055, 1087, 1151, 1279, 1535, 2047, 2049, 2051, 2055, 2063, 2079, 2111, 2175, 2303, 2559, 3071

Offset: 0

Vladimir Shevelev, Mar 09 2012

The sequence is concatenation of rows of triangle which begins
  i\j |   0     1     2     3     4     5     6     7     8
======+====================================================
 |   1
 |   3     5
 |   7     9    11
 |  15    17    19    23
 |  31    33    35    39    47
 |  63    65    67    71    79    95
 | 127   129   131   135   143   159   191
 | 255   257   259   263   271   287   319   383
 | 511   513   515   519   527   543   575   639   767

			Consider n=19. Then k = floor((1 + sqrt(145))/2) = 6 and m = 19 - 16 = 3. Thus a(19) = 2^6 + 2^4 - 1 = 79.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000225, A224195 (binary reversal).

k = Floor[(1 + Sqrt[8*n - 7])/2]; m = n - (k^2 - k + 2)/2; a[n_] = If[n == 0, 1, 2^k + 2^(m + 1) - 1]; Table[a[n], {n, 0, 100}]

For i=0,1,..., the i-th row is 2^(i+1)-1, if j=0, and 2^(i+1)+2^j-1, if j=1,...,i.

A224380 Table read by antidiagonals of numbers of form (2^n -1)*2^(m+2) + 3 where n>=1, m>=1.

Original entry on oeis.org

11, 19, 27, 35, 51, 59, 67, 99, 115, 123, 131, 195, 227, 243, 251, 259, 387, 451, 483, 499, 507, 515, 771, 899, 963, 995, 1011, 1019, 1027, 1539, 1795, 1923, 1987, 2019, 2035, 2043, 2051, 3075, 3587, 3843, 3971, 4035, 4067, 4083, 4091, 4099, 6147, 7171, 7683, 7939, 8067, 8131, 8163, 8179

Offset: 1

Brad Clardy, Apr 05 2013

The table has row labels 2^n - 1 and column labels 2^(m+2). The table entry is row*col + 3. A MAGMA program is provided that generates the numbers in a table format. The sequence is read along the antidiagonals starting from the top left corner. Using the lexicographic ordering of A057555  the sequence is:
A(n) = Table(i,j) with (i,j)=(1,1),(1,2),(2,1),(1,3),(2,2),(3,1)...
+3  |    8    16    32    64   128    256    512 ...
----|-------------------------------------------
1   |   11    19    35    67   131    259    515
3   |   27    51    99   195   387    771   1539
7   |   59   115   227   451   899   1795   3587
15  |  123   243   483   963  1923   3843   7683
31  |  251   499   995  1987  3971   7939  15875
63  |  507  1011  2019  4035  8067  16131  32259
127 | 1019  2035  4067  8131 16259  32515  65027
...
All of these numbers have the following property: let m be a member of A(n); if a sequence B(n) = all i such that i XOR (m - 1) = i - (m - 1), then the differences between successive members of B(n) is an alternating series of 1's and 3's with the last difference in the pattern m. The number of alternating 1's and 3's in the pattern is 2^(j+1) - 1, where j is the column index.
As an example consider A(1) which is 11, the sequence B(n) where i XOR 10 = i - 10 starts as 10, 11, 14, 15, 26, 27, 30, 31, 42, ... (A214864) with successive differences of 1, 3, 1, 11.
Main diagonal is A191341, the largest k such that k-1 and k+1 in binary representation have the same number of 1's and 0's

Brad Clardy, Table of n, a(n) for n = 1..1000

Cf. A057555(lexicographic ordering), A214864(example), A224195.
Rows: A062729(i=1), A147595(2 n>=5), A164285(3 n>=3).
Cols: A168616(j=1 n>=4).
Diagonal: A191341.

//program generates values in a table form,row labels of 2^i -1
for i:=1 to 10 do
    m:=2^i - 1;
    m, [ m*2^n +1 : n in [1..10]];
end for;
//program generates sequence in lexicographic ordering of A057555, read
//along antidiagonals from top. Primes in the sequence are marked with *.
for i:=2 to 18 do
    for j:=1 to i-1 do
       m:=2^j -1;
       k:=m*2^(2+i-j) + 3;
       if IsPrime(k) then k, "*";
          else k;
       end if;;
    end for;
end for;

a(n) = 2^(A057555(2*n - 1))*2^(A057555(2*n) + 2) + 3 for n>=1.

A276918 a(2n) = A060867(n+1), a(2n+1) = A092440(n+1).

Original entry on oeis.org

1, 5, 9, 25, 49, 113, 225, 481, 961, 1985, 3969, 8065, 16129, 32513, 65025, 130561, 261121, 523265, 1046529, 2095105, 4190209, 8384513, 16769025, 33546241, 67092481, 134201345, 268402689, 536838145, 1073676289, 2147418113, 4294836225, 8589803521, 17179607041

Offset: 0

Daniel Poveda Parrilla, Jan 26 2017

nonn

In binary there is a pattern in how the zeros and ones appear:
a(0)  =         01
a(1)  =        101
a(2)  =        1001
a(3)  =       11001
a(4)  =       110001
a(5)  =      1110001
a(6)  =      11100001
a(7)  =     111100001
a(8)  =     1111000001
a(9)  =    11111000001
a(10) =    111110000001
a(11) =   1111110000001
a(12) =   11111100000001
a(13) =  111111100000001
a(14) =  1111111000000001
a(15) = 11111111000000001
Graphically, each term can be obtained by successively and alternately forming squares and centered squares as shown in the illustration.

Daniel Poveda Parrilla, Table of n, a(n) for n = 0..1000
Daniel Poveda Parrilla, Illustration of initial terms
Index entries for linear recurrences with constant coefficients, signature (3,0,-6,4).

Cf. A000225, A060867, A092440, A224195.

Table[1+2^(n+2)-2^(1+n/2)+(-1)^(n+1) 2^(1+n/2)-2^((n+1)/2)+(-1)^(n+2) 2^((n+1)/2), {n,0,28}] (*or*)
CoefficientList[Series[(-1 - 2 x + 6 x^2 - 4 x^3)/(-1 + 3 x - 6 x^3 + 4 x^4), {x,0,28}], x] (*or*)
LinearRecurrence[{3, 0, -6, 4}, {1, 5, 9, 25}, 29]

Vec((-1-2*x+6*x^2-4*x^3) / (-1+3*x-6*x^3+4*x^4) + O(x^29))

a(n) = 1 + 2^(n+2) - 2^(1 + n/2) + (-1)^(n+1)*2^(1 + n/2) - 2^((n+1)/2) + (-1)^(n+2)*2^((n+1)/2).
a(n) = 3*a(n-1) - 6*a(n-3) + 4*a(n-4) for n>3.
G.f.: (-1-2*x+6*x^2-4*x^3)/(-1+3*x-6*x^3+4*x^4).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

J

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Scala

Formula

Extensions

A209492 a(0)=1; for n >= 1, let k = floor((1 + sqrt(8*n-7))/2), m = n - (k^2 - k+2)/2. Then a(n) = 2^k + 2^(m+1) - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A224380 Table read by antidiagonals of numbers of form (2^n -1)*2^(m+2) + 3 where n>=1, m>=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Formula

A276918 a(2n) = A060867(n+1), a(2n+1) = A092440(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula