A005811 -id:A005811 - cp's OEIS frontend

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.

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

A236840 n minus number of runs in the binary expansion of n: a(n) = n - A005811(n).

Original entry on oeis.org

0, 0, 0, 2, 2, 2, 4, 6, 6, 6, 6, 8, 10, 10, 12, 14, 14, 14, 14, 16, 16, 16, 18, 20, 22, 22, 22, 24, 26, 26, 28, 30, 30, 30, 30, 32, 32, 32, 34, 36, 36, 36, 36, 38, 40, 40, 42, 44, 46, 46, 46, 48, 48, 48, 50, 52, 54, 54, 54, 56, 58, 58, 60, 62, 62, 62, 62, 64, 64, 64

Offset: 0

Antti Karttunen, Apr 18 2014

All terms are even. Used by the "number-of-runs beanstalk" sequence A255056 and many of its associated sequences.

Antti Karttunen, Table of n, a(n) for n = 0..8192

Cf. A091067 (the positions of records), A106836 (run lengths).
Cf. A255070 (terms divided by 2).
Cf. A005811, A000120, A003188.
Cf. A255056, A255066, A255061, A255062, A255071, A255072, A255058, A255327.
Other subtracting maps: A011371, A178503, A219641, A219651, A227190, A227191, A237449, A244320, A244234, A255131.

A236840 := proc(n) local i, b; if n=0 then 0 else b := convert(n, base, 2); select(i -> (b[i-1]<>b[i]), [$2..nops(b)]); n-1-nops(%) fi end: seq(A236840(i), i=0..69); # Peter Luschny, Apr 19 2014

a[n_] := n - Length@ Split[IntegerDigits[n, 2]]; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Jul 16 2023 *)

Scheme
```
(define (A236840 n)  (- n (A005811 n)))
```

a(n) = n - A005811(n) = n - A000120(A003188(n)).

a(n) = 2*A255070(n).

A344341 Gray-code Niven numbers: numbers divisible by the number of 1's in their binary reflected Gray code (A005811).

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 15, 16, 20, 24, 27, 28, 30, 31, 32, 33, 36, 39, 40, 42, 44, 45, 48, 51, 52, 56, 57, 60, 62, 63, 64, 68, 72, 75, 76, 80, 84, 88, 90, 92, 96, 99, 100, 104, 105, 108, 111, 112, 116, 120, 123, 124, 126, 127, 128, 129, 132, 135, 136

Offset: 1

Amiram Eldar, May 15 2021

			2 is a term since its Gray code is 11 and 1+1 = 2 is a divisor of 2.
6 is a term since its Gray code is 101 and 1+0+1 = 2 is a divisor of 6.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Gray Code.
Wikipedia, Gray code.

Cf. A005811, A014550.
Subsequences: A344342, A344343, A344344.
Similar sequences: A005349 (decimal), A049445 (binary), A064150 (ternary), A064438 (quaternary), A064481 (base 5), A118363 (factorial), A328208 (Zeckendorf), A328212 (lazy Fibonacci), A331085 (negaFibonacci), A333426 (primorial), A334308 (base phi), A331728 (negabinary), A342426 (base 3/2), A342726 (base i-1).

gcNivenQ[n_] := Divisible[n, DigitCount[BitXor[n, Floor[n/2]], 2, 1]]; Select[Range[150], gcNivenQ]

A173318 Partial sums of A005811.

Original entry on oeis.org

0, 1, 3, 4, 6, 9, 11, 12, 14, 17, 21, 24, 26, 29, 31, 32, 34, 37, 41, 44, 48, 53, 57, 60, 62, 65, 69, 72, 74, 77, 79, 80, 82, 85, 89, 92, 96, 101, 105, 108, 112, 117, 123, 128, 132, 137, 141, 144, 146, 149, 153, 156, 160, 165, 169, 172, 174, 177, 181, 184, 186, 189

Offset: 0

Jonathan Vos Post, Feb 16 2010

Partial sums of number of runs in binary expansion of n (n>0). Partial sums of number of 1's in Gray code for n. The subsequence of squares in this partial sum begins 0, 1, 4, 9, 144, 169, 256, 289, 324 (since we also have 32 and 128 I wonder about why so many powers). The subsequence of primes in this partial sum begins: 3, 11, 17, 29, 31, 37, 41, 53, 79, 89, 101, 137, 149, 181, 191, 197, 229, 271.

Note: A227744 now gives the squares, which occur at positions given by A227743. - Antti Karttunen, Jul 27 2013

			1 has 1 run in its binary representation "1".
2 has 2 runs in its binary representation "10".
3 has 1 run in its binary representation "11".
4 has 2 runs in its binary representation "100".
5 has 3 runs in its binary representation "101".
Thus a(1) = 1, a(2) = 1+2 = 3, a(3) = 1+2+1 = 4, a(4) = 1+2+1+2 = 6, a(5) = 1+2+1+2+3 = 9.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Richard Blecksmith and Purushottam W. Laud, Some Exact Number Theory Computations via Probability Mechanisms, American Mathematical Monthly, volume 102, number 10, December 1995, pages 893-903, with a(n) = Sum_{j=0..n} b_j as calculated in section 2.
Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, volume 13, number 4, December 2017, article number 47, pages 1-43. Also first authors' copy, 2016. See example 5.5.
Kevin Ryde, Iterations of the Dragon Curve, see index "DirCumul".

Cf. A005811, A000788, A056539, A014707, A014577, A082410, A000975, A034947.
Cf. also A227737, A227741, A227742.
Cf. A227744 (squares occurring), A227743 (indices of squares).

Accumulate[Join[{0},Table[Length[Split[IntegerDigits[n,2]]],{n,110}]]] (* Harvey P. Dale, Jul 29 2013 *)

a(n) = my(v=binary(n+1),d=0,e=4); for(i=1,#v, if(v[i], v[i]=#v-i+d;d+=e;e=0, e=4)); fromdigits(v,2)>>1; \\ Kevin Ryde, Aug 27 2021

a(n) = sum(i=0..n) A005811(i) = sum(i=0..n) (A037834(i)+1) = sum(i=0..n) (A069010(i) + A033264(i)).
a(A000225(n)) = A001787(n) = A000788(A000225(n)). - Antti Karttunen, Jul 27 2013 & Aug 09 2013
a(2n) = 2*a(n) + n - 2*(ceiling(A005811(n)/2) - (n mod 2)), a(2n+1) = 2*a(n) + n + 1. - Ralf Stephan, Aug 11 2013

A227741 Simple self-inverse permutation of natural numbers: List each block of A005811(n) numbers from A173318(n-1)+1 to A173318(n) in reverse order.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jul 25 2013

nonn

This permutation maps between such irregular tables as A101211 and A227736 which are otherwise identical, except for the order in which the lengths of runs have been listed. In other words, A227736(n) = A101211(a(n)) and vice versa, A101211(n) = A227736(a(n)).

Antti Karttunen, Table of n, a(n) for n = 1..1001
Index entries for sequences that are permutations of the natural numbers

Cf. A227742 (gives the fixed points).

Cf. also A227737, A227740, A005811, A173318.

(define (A227741 n) (- (A173318 (A227737 n)) (A227740 n)))

a(n) = A173318(A227737(n)) - A227740(n).

A255070 (1/2)*(n minus number of runs in the binary expansion of n): a(n) = (n - A005811(n)) / 2 = A236840(n)/2.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 3, 3, 3, 3, 4, 5, 5, 6, 7, 7, 7, 7, 8, 8, 8, 9, 10, 11, 11, 11, 12, 13, 13, 14, 15, 15, 15, 15, 16, 16, 16, 17, 18, 18, 18, 18, 19, 20, 20, 21, 22, 23, 23, 23, 24, 24, 24, 25, 26, 27, 27, 27, 28, 29, 29, 30, 31, 31, 31, 31, 32, 32, 32, 33, 34, 34, 34, 34, 35

Offset: 0

Antti Karttunen, Feb 14 2015

Antti Karttunen, Table of n, a(n) for n = 0..8192
Helmut Prodinger and Friedrich J. Urbanek, Infinite 0-1-Sequences Without Long Adjacent Identical Blocks, Discrete Mathematics, Volume 28, Number 3, 1979, pages 277-289. Also first author's copy. See theorem 3.6, n_1(k) = a(k).

Least inverse: A091067 (also the positions of records).
Greatest inverse: A255068.
Run lengths: A106836.
Cf. A005811, A060833, A236840, A255054, A255056, A255072, A269363, A269367.

a[n_] := (n - Length@ Split[IntegerDigits[n, 2]])/2; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Jul 16 2023 *)

Scheme
```
(define (A255070 n) (/ (A236840 n) 2))
```

a(n) = A236840(n) / 2 = (n - A005811(n)) / 2.
Other identities:
a(A091067(n)) = n for all n >= 1.
a(A255068(n)) = n for all n >= 0.
a(A269363(n)) = A269367(n). - Antti Karttunen, Aug 12 2019

A361644 Irregular triangle T(n, k), n >= 0, k = 1..max(1, 2^(A005811(n)-1)), read by rows; the n-th row lists the integers with the same binary length as n and whose partial sums of run lengths are included in those of n.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 7, 4, 5, 6, 7, 6, 7, 7, 8, 15, 8, 9, 14, 15, 8, 9, 10, 11, 12, 13, 14, 15, 8, 11, 12, 15, 12, 15, 12, 13, 14, 15, 14, 15, 15, 16, 31, 16, 17, 30, 31, 16, 17, 18, 19, 28, 29, 30, 31, 16, 19, 28, 31, 16, 19, 20, 23, 24, 27, 28, 31

Offset: 0

Rémy Sigrist, Mar 19 2023

In other words, the n-th row contains the numbers k with the same binary length as n and for any i >= 0, if the i-th bit and the (i+1)-th bit in k are different then they are also different in n (i = 0 corresponding to the least significant bit).

The value m appears 2^A092339(m) times in the triangle (see A361674).

			Triangle begins (in decimal and in binary):
  n   n-th row      bin(n)  n-th row in binary
  --  ------------  ------  ------------------
   0  0                  0  0
   1  1                  1  1
   2  2, 3              10  10, 11
   3  3                 11  11
   4  4, 7             100  100, 111
   5  4, 5, 6, 7       101  100, 101, 110, 111
   6  6, 7             110  110, 111
   7  7                111  111
   8  8, 15           1000  1000, 1111
   9  8, 9, 14, 15    1001  1000, 1001, 1110, 1111
.
For n = 9:
- the binary expansion of 9 is "1001",
- the corresponding run lengths are 1, 2, 1,
- so the 9th row contains the values with the following run lengths:
      1, 2, 1  ->   9 ("1001" in binary)
      1,  2+1  ->   8 ("1000" in binary)
      1+2,  1  ->  14 ("1110" in binary)
       1+2+1   ->  15 ("1111" in binary)

Rémy Sigrist, Table of n, a(n) for n = 0..9841 (rows for n = 0..511 flattened)
Index entries for sequences related to binary expansion of n

Cf. A003817, A005811, A092339, A101211, A225081, A342126, A361645, A361646, A361674, A361676.

row(n) = { my (r = []); while (n, my (v = valuation(n+n%2, 2)); n \= 2^v; r = concat(v, r)); my (s = [if (#r, 2^r[1]-1, 0)]); for (k = 2, #r, s = concat(s * 2^r[k], [(h+1)*2^r[k]-1|h<-s]);); vecsort(s); }

T(n, 1) = A342126(n).

T(n, max(1, 2^(A005811(n)-1))) = A003817(n).

A371257 Irregular triangle T(n, k), n >= 0, k = 1..2^A005811(n), read by rows; the n-th row lists the numbers m such that A371256(m) = n.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 17, 18, 22, 10, 11, 15, 16, 19, 20, 21, 23, 12, 14, 24, 25, 13, 26, 27, 53, 54, 67, 28, 29, 51, 52, 55, 56, 66, 68, 30, 32, 33, 34, 46, 47, 48, 50, 57, 59, 60, 61, 64, 65, 69, 70, 31, 35, 45, 49, 58, 62, 63, 71, 36, 44, 72, 76

Offset: 0

Rémy Sigrist, Mar 16 2024

The n-th row has 2^A005811(n) terms.

As a flat sequence, this is a permutation of the nonnegative integers, with inverse A371258.

			Triangle T(n, k) begins:
  n   n-th row
  --  --------------------------------------------------------------
   0  0
   1  1, 2
   2  3, 5, 6, 7
   3  4, 8
   4  9, 17, 18, 22
   5  10, 11, 15, 16, 19, 20, 21, 23
   6  12, 14, 24, 25
   7  13, 26
   8  27, 53, 54, 67
   9  28, 29, 51, 52, 55, 56, 66, 68
  10  30, 32, 33, 34, 46, 47, 48, 50, 57, 59, 60, 61, 64, 65, 69, 70
  11  31, 35, 45, 49, 58, 62, 63, 71
  12  36, 44, 72, 76
  13  37, 38, 42, 43, 73, 74, 75, 77
  14  39, 41, 78, 79
  15  40, 80
.
Triangle T(n, k) begins, in ternary, with row indexes in binary:
  bin(n)  n-th row in ternary
  ------  ----------------------------------------------
       0  0
       1  1, 2
      10  10, 12, 20, 21
      11  11, 22
     100  100, 122, 200, 211
     101  101, 102, 120, 121, 201, 202, 210, 212
     110  110, 112, 220, 221
     111  111, 222
    1000  1000, 1222, 2000, 2111
    1001  1001, 1002, 1220, 1221, 2001, 2002, 2110, 2112

Rémy Sigrist, Table of n, a(n) for n = 0..6560
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

See A371265 for a similar sequence.

Cf. A005811, A166242, A368229, A371256.

PARI
```
\\ See Links section.
```

A255336 a(n) = A005811(A255056(n)); After the initial zero, the first differences of A255056.

Original entry on oeis.org

0, 2, 2, 2, 4, 2, 2, 4, 4, 4, 2, 2, 2, 4, 6, 4, 4, 4, 4, 2, 2, 2, 4, 6, 4, 6, 6, 4, 2, 4, 6, 4, 4, 4, 4, 2, 2, 2, 4, 6, 4, 6, 4, 4, 6, 6, 6, 6, 6, 4, 2, 4, 6, 4, 6, 6, 4, 2, 4, 6, 4, 4, 4, 4, 2, 2, 2, 4, 6, 4, 6, 4, 4, 6, 6, 6, 6, 4, 4, 6, 6, 6, 8, 6, 6, 6, 6, 6, 6, 4, 2, 4, 6, 4, 6, 4, 4, 6, 6, 6, 6, 6, 4, 2, 4, 6, 4, 6, 6, 4, 2, 4, 6, 4, 4, 4, 4, 2, 2

Offset: 0

Antti Karttunen, Feb 21 2015

nonn

First differences of A255056, shifted once right (prepended with zero).

Antti Karttunen, Table of n, a(n) for n = 0..8590

First differences of A255056.
Terms of A255337 doubled.
Cf. A005811.
Analogous sequence: A213712.

a(n) = A005811(A255056(n)).
a(0) = 0; and for n >= 1: a(n) = A255056(n) - A255056(n-1).
a(n) = 2*A255337(n).

A324345 Lexicographically earliest positive sequence such that a(i) = a(j) => A005811(i) = A005811(j) and A278222(i) = A278222(j), for all i, j >= 0.

Original entry on oeis.org

1, 2, 3, 4, 3, 5, 6, 7, 3, 5, 8, 9, 6, 9, 10, 11, 3, 5, 8, 9, 8, 12, 13, 14, 6, 9, 13, 15, 10, 14, 16, 17, 3, 5, 8, 9, 8, 12, 13, 14, 8, 12, 18, 19, 13, 19, 20, 21, 6, 9, 13, 15, 13, 19, 22, 23, 10, 14, 20, 23, 16, 21, 24, 25, 3, 5, 8, 9, 8, 12, 13, 14, 8, 12, 18, 19, 13, 19, 20, 21, 8, 12, 18, 19, 18, 26, 27, 28, 13, 19, 27, 29, 20, 28, 30, 31, 6, 9, 13, 15, 13, 19

Offset: 0

Antti Karttunen, Feb 24 2019

nonn

Restricted growth sequence transform of the ordered pair [A005811(n), A278222(n)], or equally, of [A005811(n), A286622(n)].
For all i, j >= 1:
  a(i) = a(j) => A033264(i) = A033264(j).

Antti Karttunen, Table of n, a(n) for n = 0..65537
Index entries for sequences related to binary expansion of n

Cf. A005811, A278222, A286622.

Cf. also A033264, A323889, A324343, A324346.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A005811(n) = hammingweight(bitxor(n, n>>1)); \\ From A005811
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A278222(n) = A046523(A005940(1+n));
Aux324345(n) = [A005811(n), A278222(n)];
v324345 = rgs_transform(vector(1+up_to,n,Aux324345(n-1)));
A324345(n) = v324345[1+n];

a(2^n) = 3 for all n >= 1.

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A236840 n minus number of runs in the binary expansion of n: a(n) = n - A005811(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Scheme

Formula

A344341 Gray-code Niven numbers: numbers divisible by the number of 1's in their binary reflected Gray code (A005811).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A173318 Partial sums of A005811.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A227741 Simple self-inverse permutation of natural numbers: List each block of A005811(n) numbers from A173318(n-1)+1 to A173318(n) in reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A255070 (1/2)*(n minus number of runs in the binary expansion of n): a(n) = (n - A005811(n)) / 2 = A236840(n)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A361644 Irregular triangle T(n, k), n >= 0, k = 1..max(1, 2^(A005811(n)-1)), read by rows; the n-th row lists the integers with the same binary length as n and whose partial sums of run lengths are included in those of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A371257 Irregular triangle T(n, k), n >= 0, k = 1..2^A005811(n), read by rows; the n-th row lists the numbers m such that A371256(m) = n.

Views

Author