A264596 -id:A264596 - 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

A293290 a(n) = Product_{1 <= j <= k <= n} (k^2 + j^2).

Original entry on oeis.org

1, 2, 80, 187200, 50918400000, 2675955409920000000, 40702283662588674048000000000, 250658664786823821917343252480000000000000, 832906513114759565863066815448211678822400000000000000000, 1919381816160714520414106848157314737202346840876384256000000000000000000000

Offset: 0

Velin Yanev, Oct 05 2017

Suggested by Omar E. Pol from A264596 formula.

Cf. A101686, A203475, A324403.

Table[Product[k^2 + j^2, {k, 1, n}, {j, 1, k}], {n, 0, 10}]

[prod([prod([k^2+j^2 for j in range(1,k+1)]) for k in range(1,n+1)]) for n in range(10)] # Danny Rorabaugh, Oct 16 2017

a(n) ~ sqrt(Gamma(1/4)) * Pi^(-1/8) * 2^(n^2/2 + n - 1/8) * exp(Pi*n*(n+1)/4 - 3*n^2/2 - n + Pi/24) * n^(n*(n+1) + 1/4). - Vaclav Kotesovec, Feb 26 2019

A263856 Let S_n be the list of the first n primes written in binary, with least significant bits on the left, and sorted into lexicographic order; a(n) = position of n-th prime in S_n.

Original entry on oeis.org

1, 2, 2, 4, 4, 3, 2, 6, 9, 5, 11, 4, 3, 11, 14, 6, 13, 9, 11, 17, 3, 20, 14, 5, 2, 9, 23, 20, 12, 4, 31, 17, 5, 23, 12, 32, 17, 22, 32, 15, 26, 14, 42, 2, 11, 37, 29, 46, 27, 14, 9, 48, 6, 40, 2, 43, 22, 51, 18, 12, 43, 17, 39, 56, 14, 32, 45, 6, 50

Offset: 1

John Bodeen, Oct 28 2015

a(A264647(n)) = n and a(m) != n for m < A264647(n). - Reinhard Zumkeller, Nov 19 2015

A264662(n,a(n)) = A000040(n): a(n) = index of prime(n) in n-th row of triangle A264662. - Reinhard Zumkeller, Nov 20 2015

			S_1 = [01], a(1) = 1;
S_2 = [01, 11], a(2) = 2;
S_3 = [01, 101, 11], a(3) = 2;
S_4 = [01, 101, 11, 111], a(4) = 4;
S_5 = [01, 101, 11, 1101, 111], a(5) = 4;
S_5 = [01, 101, 1011, 11, 1101, 111], a(6) = 3;
...

John Bodeen, Table of n, a(n) for n = 1..24771
John Bodeen, OCaml program to generate the sequence

A004676 is the sequence upon which the lexicographic ordering is based.
Cf. A264596.
Cf. A264647, A264662.

import Data.List (insertBy); import Data.Function (on)
import Data.List (elemIndex); import Data.Maybe (fromJust)
a263856 n = a263856_list !! (n-1)
a263856_list = f [] a004676_list where
   f bps (x:xs) = y : f bps' xs where
     y = fromJust (elemIndex x bps') + 1
     bps' = insertBy (compare `on` (reverse . show)) x bps
-- Reinhard Zumkeller, Nov 19 2015

s:= proc(n) s(n):= cat("", convert(ithprime(n), base, 2)[]) end:
a:= n-> ListTools[BinarySearch](sort([seq(s(i), i=1..n)]), s(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 19 2015

S[n_] := S[n] = SortBy[Prime[Range[n]], StringJoin @@ ToString /@ Reverse[IntegerDigits[#, 2]]&];
a[n_] := FirstPosition[S[n], Prime[n]][[1]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Sep 22 2021 *)

from sympy import prime
def A263856(n):
    return 1+sorted(format(prime(i),'b')[::-1] for i in range(1,n+1)).index(format(prime(n),'b')[::-1]) # Chai Wah Wu, Nov 22 2015

A264600 Let S_n denote the list of decimal numbers 0 to n, written backwards (allowing leading zeros) and arranged in lexicographic order; a(n) = position where backwards-n appears, starting indexing at 0.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 6, 13, 20, 27, 34, 41, 48, 55, 62, 69, 7, 15, 23, 31, 39, 47, 55, 63, 71, 79, 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 9, 19, 29, 39, 49, 59, 69, 79, 89, 99, 1, 12

Offset: 0

N. J. A. Sloane, Nov 20 2015

			S_0 = [0], so a(0)=0,
...
S_9 = [0,1,2,3,4,5,6,7,8,9], so a(9) = 9,
S_10 = [0,01,1,2,3,4,5,6,7,8,9], so a(10) = 1,
S_11 = [0,01,1,11,2,3,4,5,6,7,8,9], so a(11) = 3,
...
S_20 = [0,01,02,1,11,2,21,3,31,4,41,5,51,6,61,7,71,8,81,9,91], so a(20) = 2, and so on

Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 10000 terms from Chai Wah Wu)

Decimal analog of A264596.

Has same beginning as A061486 but is ultimately different: see A264668.

a:= proc(n) option remember; `if`(n=0, 0,
      irem(n, 10, 'r')*(r+1)+a(r))
    end:
seq(a(n), n=0..101);  # Alois P. Heinz, Nov 20 2015

A264600[0]=0;A264600[n_]:=A264600[n]=Mod[n,10](Floor[n/10]+1)+A264600[Floor[n/10]];Array[A264600,100,0] (* Paolo Xausa, Nov 04 2023, after Alois P. Heinz *)

def A264600(n):
    return sorted(str(i)[::-1] for i in range(n+1)).index(str(n)[::-1]) # Chai Wah Wu, Nov 20 2015

a(0) = 0, a(10n+m) = a(n) + m*(n+1) for m in {0,...,9}. - Alois P. Heinz, Nov 20 2015

More terms from Alois P. Heinz, Nov 20 2015

A188215 Starting with an empty list, n is inserted after the a(n)th element such that the binary representations of the list's elements are always sorted lexicographically.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 6, 7, 4, 5, 7, 8, 11, 12, 14, 15, 5, 6, 8, 9, 12, 13, 15, 16, 20, 21, 23, 24, 27, 28, 30, 31, 6, 7, 9, 10, 13, 14, 16, 17, 21, 22, 24, 25, 28, 29, 31, 32, 37, 38, 40, 41, 44, 45, 47, 48, 52, 53, 55

Offset: 0

Grant Garcia, Mar 24 2011

The last occurrence of any positive n in this sequence is a(2^(n - 1)).
As the list in question expands, its initial terms converge toward A131577.
The last item of the list is always zero or an element of A075427.

			For example, an a(n) of 3 means that n should be inserted after the 3rd element of the list to keep the elements lexicographically ordered.
[] (Initial empty list)
[0] (Zero inserted at the beginning: a(0) = 0)
[0, 1] (One inserted after element 1: a(1) = 1)
[0, 1, 10] (Two inserted after element 2: a(2) = 2)
[0, 1, 10, 11] (Three inserted after element 3: a(3) = 3)
[0, 1, 10, 100, 11] (Four inserted after element 3: a(4) = 3)

T. D. Noe, Table of n, a(n) for n = 0..1023

Cf. A264596.

lst = {}; Table[s = IntegerString[n, 2]; lst = Sort[Append[lst, s]]; Position[lst, s][[1, 1]] - 1, {n, 0, 63}] (* T. D. Noe, Apr 19 2011 *)

l = []
for i in range(17):
    b = bin(i)[2:]
    l.append(b)
    l.sort()
    print(l.index(b))

a(2^n + b) = n + b + 1 for b = 0 or 1.

a(2^n - b) = 2^n - b for b = 1 or 2.

Program added by Grant Garcia, Mar 30 2011

Edited by Grant Garcia, Apr 13 2011

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

A293290 a(n) = Product_{1 <= j <= k <= n} (k^2 + j^2).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Sage

Formula

A263856 Let S_n be the list of the first n primes written in binary, with least significant bits on the left, and sorted into lexicographic order; a(n) = position of n-th prime in S_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

A264600 Let S_n denote the list of decimal numbers 0 to n, written backwards (allowing leading zeros) and arranged in lexicographic order; a(n) = position where backwards-n appears, starting indexing at 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A188215 Starting with an empty list, n is inserted after the a(n)th element such that the binary representations of the list's elements are always sorted lexicographically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions