A036044 -id:A036044 - cp's OEIS frontend

A269633 Numbers whose arithmetic derivative is equal to their BCR, where BCR = A036044, binary-complement-and-reverse = take one's complement then reverse bit order.

1, 9, 21, 93, 381, 6596, 20995, 24573, 57823, 62359, 98756, 208148, 393213, 400844, 405788, 418756, 1572861, 6460508

Offset: 1

Paolo P. Lava, Mar 02 2016

			9 is 1001 in base 2; complement: 0110; reverse: 0110 that is 6 in base 10 and 9' = 6;
21 is 10101 in base 2; complement: 01010; reverse: 01010 that is 10 in base 10 and 21' = 10.

Cf. A003415, A036044.

P:=proc(q) local a,b, k,n,p;
for n from 1 to q do a:=convert(n,base,2); b:=0;
for k from 1 to nops(a) do if a[k]=0 then a[k]:=1 else a[k]:=0; fi; b:=2*b+a[k]; od;
if b=n*add(op(2,p)/op(1,p),p=ifactors(n)[2]) then print(n); fi;
od; end: P(10^6);

f[n_] := If[Abs@ n < 2, 0, n Total[#2/#1 & @@@ FactorInteger@ Abs@ n]]; g[n_] := FromDigits[Reverse[IntegerDigits[n, 2] /. {1 -> 0, 0 -> 1}], 2]; Select[Range[10^6], f@ # == g@ # &] (* Michael De Vlieger, Mar 03 2016, after Michael Somos at A003415 and Harvey P. Dale at A036044 *)

Solution of the equation A003415(n) = A036044(n).

A345401 a(n) is the unique odd number h such that BCR(h*2^m-1) = 2n (except for BCR(0) = 1) where BCR is bit complement and reverse per A036044.

Original entry on oeis.org

1, 3, 7, 5, 15, 11, 13, 9, 31, 23, 27, 19, 29, 21, 25, 17, 63, 47, 55, 39, 59, 43, 51, 35, 61, 45, 53, 37, 57, 41, 49, 33, 127, 95, 111, 79, 119, 87, 103, 71, 123, 91, 107, 75, 115, 83, 99, 67, 125, 93, 109, 77, 117, 85, 101, 69, 121, 89, 105, 73, 113, 81, 97, 65, 255, 191

Offset: 0

Bernard Schott, Jun 18 2021

This sequence is a permutation of the odd numbers.
We have BCR(a(n)*2^m-1) = 2n when n = 0 for m >= 1, and BCR(a(n)*2^m-1) = 2n when n >= 1 for m >= 0.
Why this exception when n = 0? As a(0) = 1, we have BCR(1*2^m-1) = 2*0 = 0 only for m >= 1, because, for m = 0, we have BCR(1*2^0-1) = BCR(0) = 1 <> 2*0 = 0.

			a(0) = 1 because BCR(1*2^m-1) = 2*0 = 0 for m >= 1 (A000225).
a(1) = 3 because BCR(3*2^m-1) = 2*1 = 2 for m >= 0 (A153893).
a(2) = 7 because BCR(7*2^m-1) = 2*2 = 4 for m >= 0 (A086224).
Indeed, a(1) = 3 because 3*2^m-1 = 1011..11_2 (i.e., 10 followed by m 1's), whose bit complement is 0100..00, which reverses to 10_2 = 2 = 2*1.
Also, a(43) = 75 because 75*2^m-1 = 100101011..11_2 (i.e., 1001010 followed by m 1's), whose bit complement is 011010100..00, which reverses to 1010110_2 = 86 = 2*43.

Cf. A036044 (BCR), A059894.

When BCR(n) = 0, 2, 4, 6, 8, 10, 12, then corresponding a(n) = h = 1, 3, 7, 5, 15, 11, 13 and numbers h*2^m-1 are respectively in A000225, A153893, A086224, A153894, A196305, A086225, A198274.

a(n) = BCR(2*n) + 1 for n >= 1.

a(n) = 2*A059894(n) + 1 for n >= 1. - Hugo Pfoertner, Jun 18 2021

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.

Original entry on oeis.org

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

A057164 Self-inverse permutation of natural numbers induced by reflections of the rooted plane trees and mountain ranges encoded by A014486.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 14, 11, 16, 19, 10, 15, 12, 17, 20, 13, 18, 21, 22, 23, 37, 28, 42, 51, 25, 39, 30, 44, 53, 33, 47, 56, 60, 24, 38, 29, 43, 52, 26, 40, 31, 45, 54, 34, 48, 57, 61, 27, 41, 32, 46, 55, 35, 49, 58, 62, 36, 50, 59, 63, 64, 65, 107, 79, 121, 149, 70

Offset: 0

Antti Karttunen, Aug 18 2000

nonn

CatalanRankGlobal given in A057117 and the other Maple procedures in A056539.

Composition with A057163 gives Donaghey's Map M (A057505/A057506).

			a(10)=14 and a(14)=10, A014486[10] = 172 (10101100 in binary), A014486[14] = 202 (11001010 in binary) and these encode the following mountain ranges (and the corresponding rooted plane trees), which are reflections of each other:
...../\___________/\
/\/\/__\_________/__\/\/\
...
...../...........\
..\|/.............\|/

Rémy Sigrist, Table of n, a(n) for n = 0..6917 (first 197 terms from Indranil Ghosh)
Antti Karttunen, Gatomorphisms (includes the complete Scheme program for computing this sequence).
Antti Karttunen, C program which implements this Catalan bijection.
Indranil Ghosh, Python program for computing the sequence.
Rémy Sigrist, PARI program.
Index entries for signature-permutations induced by Catalan automorphisms

A057123(A057163(n)) = A057164(A057123(n)) for all n. Also the car/cdr-flipped conjugate of A069787, i.e., A057164(n) = A057163(A069787(A057163(n))). Fixed terms are given by A061856. Cf. also A057508, A069772.

Row 2 of tables A122287 and A122288.

a(n) = CatalanRankGlobal(runcounts2binexp(reverse(binexp2runcounts(A014486[n])))) # i.e., reverse and complement the totally balanced binary sequences

PARI
```
See Links section.
```

a(n) = A080300(A036044(A014486(n))) = A080300(A056539(A014486(n))).

A056539 Self-inverse permutation: reverse the bits in binary expansion of n and also complement them (0->1, 1->0) if the run count (A005811) is even.

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 14, 9, 10, 13, 12, 11, 8, 15, 30, 17, 22, 25, 26, 21, 18, 29, 28, 19, 20, 27, 24, 23, 16, 31, 62, 33, 46, 49, 54, 41, 38, 57, 58, 37, 42, 53, 50, 45, 34, 61, 60, 35, 44, 51, 52, 43, 36, 59, 56, 39, 40, 55, 48, 47, 32, 63, 126, 65, 94, 97, 110, 81, 78

Offset: 0

Antti Karttunen, Jun 20 2000

			n:                     0, 1,  2,  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15
binary expansion:      0, 1, 10, 11, 100, 101, 110, 111,1000,1001,1010,1011,1100,1101,1110,1111
reversed/complemented: 0, 1, 10, 11, 110, 101, 100, 111,1110,1001,1010,1101,1100,1011,1000,1111

Cf. A054429.

When restricted to A014486 induces another permutation, A057164. A105726 is a "deep" variant.

[seq(runcounts2binexp(reverse(binexp2runcounts(j))),j=0..511)];
runcounts2binexp := proc(c) local i,e,n; n := 0; for i from 1 to nops(c) do e := c[i]; n := ((2^e)*n) + ((i mod 2)*((2^e)-1)); od; RETURN(n); end;
binexp2runcounts := proc(nn) local n,a,p,c; n := nn; a := []; p := (`mod`(n,2)); c := 0; while(n > 0) do c := c+1; n := floor(n/2); if((`mod`(n,2)) <> p) then a := [c,op(a)]; c := 0; p := (`mod`(p+1,2)); fi; od; RETURN(a); end;
# reverse given in A056538

A056539[n_] := If[n == 0, 0, FromDigits[Reverse[If[Last[#] == 1, #, 1-#]], 2] & [IntegerDigits[n, 2]]];
Array[A056539, 100, 0] (* Paolo Xausa, Nov 28 2024 *)

def a005811(n): return bin(n^(n>>1))[2:].count("1")
def a(n):
    if n==0: return 0
    x=bin(n)[2:][::-1]
    if a005811(n)%2==1: return int(x, 2)
    z=''.join('1' if i == '0' else '0' for i in x)
    return int(z, 2) # Indranil Ghosh, Apr 29 2017

a(2n) = A036044(2n), a(2n+1) = A030101(2n+1). - Antti Karttunen, Feb 14 2003

A035928 Numbers n such that BCR(n) = n, where BCR = binary-complement-and-reverse = take one's complement then reverse bit order.

Original entry on oeis.org

2, 10, 12, 38, 42, 52, 56, 142, 150, 170, 178, 204, 212, 232, 240, 542, 558, 598, 614, 666, 682, 722, 738, 796, 812, 852, 868, 920, 936, 976, 992, 2110, 2142, 2222, 2254, 2358, 2390, 2470, 2502, 2618, 2650, 2730, 2762, 2866, 2898, 2978, 3010, 3132, 3164, 3244

Offset: 1

Mike Keith

Numbers n such that A036044(n) = n.
Also: numbers such that n+BR(n) is in A000225={2^k-1} (with BR = binary reversed). - M. F. Hasler, Dec 17 2007
Also called "antipalindromes". - Jeffrey Shallit, Feb 04 2022

			38 is such a number because 38=100110; complement to get 011001, then reverse bit order to get 100110.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
James Haoyu Bai, Joseph Meleshko, Samin Riasat, and Jeffrey Shallit, Quotients of Palindromic and Antipalindromic Numbers, arXiv:2202.13694 [math.NT], 2022.
Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith, Sums of Palindromes: an Approach via Nested-Word Automata, preprint arXiv:1706.10206 [cs.FL], June 30 2017.

Cf. A061855.
Cf. A000225, A036044, A062383.
Intersection of A195064 and A195066; cf. A195063, A195065.

a035928 n = a035928_list !! (n-1)
a035928_list = filter (\x -> a036044 x == x) [0,2..]
-- Reinhard Zumkeller, Sep 16 2011

[seq(ReflectBinSeq(j,(floor_log_2(j)+1)),j=1..256)];
ReflectBinSeq := (x,n) -> (((2^n)*x)+binrevcompl(x));
binrevcompl := proc(nn) local n,z; n := nn; z := 0; while(n <> 0) do z := 2*z + ((n+1) mod 2); n := floor(n/2); od; RETURN(z); end;
floor_log_2 := proc(n) local nn,i: nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi: nn := floor(nn/2); od: end; # Computes essentially the same as floor(log[2](n))
# alternative Maple program:
q:= n-> (l-> is(n=add((1-l[-i])*2^(i-1), i=1..nops(l))))(Bits[Split](n)):
select(q, [$1..3333])[];  # Alois P. Heinz, Feb 10 2021

bcrQ[n_]:=Module[{idn2=IntegerDigits[n,2]},Reverse[idn2/.{1->0,0->1}] == idn2]; Select[Range[3200],bcrQ] (* Harvey P. Dale, May 24 2012 *)

for(n=1,1000,l=length(binary(n)); b=binary(n); if(sum(i=1,l,abs(component(b,i)-component(b,l+1-i)))==l,print1(n,",")))

for(i=1,999,if(Set(vecextract(t=binary(i),"-1..1")+t)==[1],print1(i","))) \\ M. F. Hasler, Dec 17 2007

a(n) = my (b=binary(n)); (n+1)*2^#b-fromdigits(Vecrev(b),2)-1 \\ Rémy Sigrist, Mar 15 2021

def comp(s): z, o = ord('0'), ord('1'); return s.translate({z:o, o:z})
def BCR(n): return int(comp(bin(n)[2:])[::-1], 2)
def aupto(limit): return [m for m in range(limit+1) if BCR(m) == m]
print(aupto(3244)) # Michael S. Branicky, Feb 10 2021

from itertools import count, islice
def A035928_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:n==int(format(~n&(1<<(m:=n.bit_length()))-1,'0'+str(m)+'b')[::-1],2),count(max(startvalue,1)))
A035928_list = list(islice(A035928_gen(),30)) # Chai Wah Wu, Jun 30 2022

If offset were 0, a(2n+1) - a(2n) = 2^floor(log_2(n)+1).

a(n) = n * A062383(n) + A036044(n). - Rémy Sigrist, Jun 11 2022

More terms from Erich Friedman

cp's OEIS Frontend

A195066 Numbers n such that BCR(n) is not less than n, where BCR = binary-complement-and-reverse = A036044.

Views

Author

Keywords

Comments

Links

Programs

Haskell

A195063 Numbers n such that BCR(n) is less than n, where BCR = binary-complement-and-reverse = A036044.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A195064 Numbers n such that BCR(n) is not greater than n, where BCR = binary-complement-and-reverse = A036044.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A195065 Numbers n such that BCR(n) is greater than n, where BCR = binary-complement-and-reverse = A036044.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Python

A269633 Numbers whose arithmetic derivative is equal to their BCR, where BCR = A036044, binary-complement-and-reverse = take one's complement then reverse bit order.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A345401 a(n) is the unique odd number h such that BCR(h*2^m-1) = 2n (except for BCR(0) = 1) where BCR is bit complement and reverse per A036044.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A057164 Self-inverse permutation of natural numbers induced by reflections of the rooted plane trees and mountain ranges encoded by A014486.

Views

Author