A101211 -id:A101211 - cp's OEIS frontend

A376423 Nonnegative numbers m such that the run lengths in binary expansion of m, say (r_1, ..., r_k), correspond to a complete ruler: the sums r_i + ... r_j with i <= j <= k cover an initial interval of the positive integers.

0, 1, 2, 4, 5, 6, 9, 10, 11, 13, 18, 19, 20, 21, 22, 23, 25, 26, 29, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 49, 50, 53, 54, 58, 68, 69, 70, 73, 74, 75, 76, 77, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 98, 101, 102, 105, 106, 109

Offset: 1

Rémy Sigrist, Sep 22 2024

There are A103295(k) terms with k binary digits (ignoring leading zeros).

			The binary expansion of 35 is "100011", the corresponding run lengths are (1, 3, 2); the sums 1, 2, 3, 1+3, 3+2, 1+3+2 cover the positive integers between 1 and 6, hence 35 is a term.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A101211, A103295, A376314.

toruns(n) = { my (r = []); while (n, my (v = valuation(n+n%2, 2)); n \= 2^v; r = concat(v, r)); r }
is(n) = { my (r = toruns(n)); #setbinop((i, j) -> vecsum(r[i..j]), [1..#r])==vecsum(r); }

A379213 a(n) is the number of nonnegative integers m such that A184615(m) = A003714(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 1, 5, 2, 1, 2, 1, 8, 3, 2, 2, 1, 3, 1, 1, 13, 5, 3, 4, 2, 3, 1, 1, 5, 2, 1, 2, 1, 21, 8, 5, 6, 3, 6, 2, 2, 5, 2, 1, 2, 1, 8, 3, 2, 2, 1, 3, 1, 1, 34, 13, 8, 10, 5, 9, 3, 3, 10, 4, 2, 4, 2, 8, 3, 2, 2, 1, 3, 1, 1, 13, 5, 3, 4, 2, 3, 1, 1, 5

Offset: 0

Rémy Sigrist, Dec 18 2024

To compute a(n) for n > 0:
- consider the runs in the binary expansion A003714(n), say (r_1, ..., r_w) (with w = A005811(A003714(n))),
- then a(n) = A000045(r_1) * ... * A000045(r_{w-1}) * A000045(r_w + 1).

Cf. A000045, A003714, A005811, A101211, A184615.

tozeck(n) = { for (i=0, oo, if (n<=fibonacci(2+i), my (v=0, f); forstep (j=i, 0, -1, if (n>=f=fibonacci(2+j), n-=f; v+=2^j;); if (n==0, return (v););););); }
toruns(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); r }
a(n) = { my (z = tozeck(n), r = toruns(z), v = 1); forstep (i = 2, #r, 2, v *= fibonacci(r[i] + if (i==#r, 1, 0));); return (v); }

a(n) = Product_{k = 1..A005811(A003714(n))} A000045(A101211(A003714(n), k) + [k = A005811(A003714(n))]) (where [] is the Iverson bracket).

A044888 Numbers whose base-2 run lengths alternate: even, odd, even, ...

Original entry on oeis.org

3, 6, 15, 24, 27, 30, 54, 63, 96, 99, 111, 120, 123, 126, 198, 216, 219, 222, 246, 255, 384, 387, 399, 438, 447, 480, 483, 495, 504, 507, 510, 774, 792, 795, 798, 864, 867, 879, 888, 891, 894, 966, 984, 987, 990, 1014, 1023, 1536

Offset: 1

Clark Kimberling

From Emeric Deutsch, Jan 27 2018: (Start)
Also the indices of the compositions whose parts alternate: even, odd, even, ... . For the definition of the index of a composition see A298644.
For example, 99 is in the sequence since its binary form is 1100011 and the composition [2,3,2] has parts: even, odd, even. 100 is not in the sequence since its binary form is 1100100 and the composition [2,2,1,2] has parts even, even, odd, even. The command c(n) from the Maple program yields the composition having index n. (End)

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A298644, A101211.

Runs := proc (L) local j, r, i, k: j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: A := {}: for n to 1540 do if `and`(type(c(n)[1], even) = true, type(product(c(n)[j]-c(n)[j+1], j = 1 .. nops(c(n))-1), odd)) then A := `union`(A, {n}) else  end if end do: A; # most of the Maple program is due to W. Edwin Clark. # Emeric Deutsch, Jan 27 2018

oeQ[n_]:=Module[{idsleb=Boole[EvenQ/@(Length/@Split[IntegerDigits[ n,2]])]},idsleb == PadRight[{},Length[idsleb],{1,0}]]; Select[ Range[ 1600],oeQ] (* Harvey P. Dale, Sep 04 2020 *)

from itertools import groupby
def ok(n): return all(len(list(g))%2 == i%2 for i, (k, g) in enumerate(groupby(bin(n)[2:])))
print([i for i in range(1, 1537) if ok(i)]) # Michael S. Branicky, Jan 04 2021

A175453 a(1)=1. a(n) = sum a(k), where k, taken over the runs (of both 0's and 1's) in binary n, equals the length of each run.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 2, 3, 4, 4, 4, 4, 4, 3, 3, 4, 4, 5, 5, 5, 5, 5, 4, 4, 5, 5, 5, 4, 4, 4, 3, 4, 5, 5, 5, 6, 6, 6, 5, 5, 6, 6, 6, 6, 6, 5, 5, 5, 5, 6, 6, 6, 6, 6, 5, 4, 5, 5, 5, 5, 5, 4, 3, 4, 5, 6, 6, 6, 6, 6, 5, 6, 7, 7, 7, 7, 7, 6, 6, 6, 6, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 6, 6, 6, 5, 5, 6, 6, 6, 7, 7, 7, 6, 6

Offset: 1

Leroy Quet, May 16 2010

			23 in binary is 10111. There is a run of one 1, followed by a run of one 0, followed finally by a run of three 1's. So, a(23) = a(1)+a(1)+a(3) = 1+1+2 = 4.

Jason Kimberley, Table of n, a(n) for n = 1..5000

Cf. A101211.

runs := function(s)
    r := []; c := 1;
    for i in [1..#s-1] do
        if s[i] eq s[i+1]
        then c +:= 1;
        else Append(~r,c); c := 1;
        end if;
    end for;
    Append(~r,c);
    return r;
end function;
A175453 := func;
// Jason Kimberley, Feb 11 2013

Extended by Jason Kimberley, Feb 11 2013

A332017 a(n) is the sum of the squares of the lengths of the runs of consecutive equal digits in the binary representation of n.

Original entry on oeis.org

0, 1, 2, 4, 5, 3, 5, 9, 10, 6, 4, 6, 8, 6, 10, 16, 17, 11, 7, 9, 7, 5, 7, 11, 13, 9, 7, 9, 13, 11, 17, 25, 26, 18, 12, 14, 10, 8, 10, 14, 12, 8, 6, 8, 10, 8, 12, 18, 20, 14, 10, 12, 10, 8, 10, 14, 18, 14, 12, 14, 20, 18, 26, 36, 37, 27, 19, 21, 15, 13, 15, 19

Offset: 0

Rémy Sigrist, Feb 04 2020

a(0) = 0 by convention.

Every nonnegative number k appears A006456(k) times in the sequence, the last occurrence being at index A000975(k).

			For n = 49:
- the binary representation of 49 is "110001",
- we have a run of 2 1's followed by a run of 3 0's followed by a run of 1 1's,
- so a(49) = 2^2 + 3^2 + 1^2 = 14.

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

Cf. A000975, A005811, A006456, A101211.

a(n) = { my (v=0); while (n, my (r=valuation(n+(n%2),2)); v+=r^2; n\=2^r); v }

a(n) = Sum_{k = 1..A005811(n)} A101211(n, k)^2.
a(A000975(k)) = k for any k >= 0.
a(2^k-1) = k^2 for any k >= 0.
a(2^k) = k^2+1 for any k >= 0.

A348111 Numbers k whose binary expansion starts with the concatenation of the binary expansions of the run lengths in binary expansion of k.

Original entry on oeis.org

0, 1, 7, 14, 28, 112, 127, 254, 509, 1016, 1018, 1792, 2033, 2037, 2039, 4066, 4072, 4075, 4078, 8132, 8135, 8150, 8156, 16256, 16300, 16313, 32513, 32528, 32576, 32601, 32607, 32626, 32639, 32767, 65027, 65087, 65153, 65202, 65248, 65253, 65255, 65534, 130307

Offset: 1

Rémy Sigrist, Oct 01 2021

We consider here that 0 has an empty binary expansion, and include it in the sequence.

This sequence is infinite as it contains A077585.

			Regarding 32607:
- the binary expansion of 32607 is "111111101011111",
- the corresponding run lengths are: 7, 1, 1, 1, 5,
- in binary: "111", "1", "1", "1", "101",
- after concatenation: "111111101",
- as "111111101011111" starts with "111111101", 32607 belongs to this sequence.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program for A348111

Cf. A077585, A101211, A175930, A319678.

PARI
```
See Links section.
```

from itertools import groupby
def ok(n):
    if n == 0: return True
    b = bin(n)[2:]
    c = "".join(bin(len(list(g)))[2:] for k, g in groupby(b))
    return b.startswith(c)
print(list(filter(ok, range(2**17)))) # Michael S. Branicky, Oct 02 2021

A355663 Square array A(n, k), n, k >= 0, read by antidiagonals; for any number n with runs in binary expansion (r_w, ..., r_0), let p(n) be the polynomial of a single indeterminate x where the coefficient of x^e is r_e for e = 0..w and otherwise 0, and let q be the inverse of p; A(n, k) = q(p(n) + p(k)).

Original entry on oeis.org

0, 1, 1, 2, 3, 2, 3, 4, 4, 3, 4, 7, 12, 7, 4, 5, 8, 8, 8, 8, 5, 6, 11, 24, 15, 24, 11, 6, 7, 12, 19, 16, 16, 19, 12, 7, 8, 15, 28, 23, 48, 23, 28, 15, 8, 9, 16, 16, 24, 39, 39, 24, 16, 16, 9, 10, 19, 48, 31, 56, 51, 56, 31, 48, 19, 10, 11, 20, 35, 32, 32, 35, 35, 32, 32, 35, 20, 11

Offset: 0

Rémy Sigrist, Jul 13 2022

In other words, A(n, k) encodes the sum of the polynomials encoded by n and k.

			Array A(n, k) begins:
  n\k|   0   1   2   3    4    5    6   7    8    9   10   11   12
  ---+------------------------------------------------------------
    0|   0   1   2   3    4    5    6   7    8    9   10   11   12
    1|   1   3   4   7    8   11   12  15   16   19   20   23   24
    2|   2   4  12   8   24   19   28  16   48   35   44   39   56
    3|   3   7   8  15   16   23   24  31   32   39   40   47   48
    4|   4   8  24  16   48   39   56  32   96   71   88   79  112
    5|   5  11  19  23   39   51   35  47   79   99   76  103   71
    6|   6  12  28  24   56   35   60  48  112   67   92   71  120
    7|   7  15  16  31   32   47   48  63   64   79   80   95   96
    8|   8  16  48  32   96   79  112  64  192  143  176  159  224
    9|   9  19  35  39   71   99   67  79  143  195  156  199  135
   10|  10  20  44  40   88   76   92  80  176  156  204  152  184
   11|  11  23  39  47   79  103   71  95  159  199  152  207  143
   12|  12  24  56  48  112   71  120  96  224  135  184  143  240

Index entries for sequences related to binary expansion of n

Cf. A001196, A014601, A101211, A355664.

toruns(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); r }
fromruns(r) = { my (v=0); for (k=1, #r, v=(v+k%2)*2^r[k]-k%2); v }
A(n,k) = { fromruns(Vec(Pol(toruns(n)) + Pol(toruns(k)))) }

A(n, k) = A(k, n).
A(n, 0) = n.
A(n, 1) = A014601(n) for any n > 0.
A(n, n) = A001196(n).

A355664 Square array A(n, k), n, k >= 0, read by antidiagonals; for any number n with runs in binary expansion (r_w, ..., r_0), let p(n) be the polynomial of a single indeterminate x where the coefficient of x^e is r_e for e = 0..w and otherwise 0, and let q be the inverse of p; A(n, k) = q(p(n) * p(k)).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 3, 0, 0, 4, 12, 12, 4, 0, 0, 5, 35, 15, 35, 5, 0, 0, 6, 38, 48, 48, 38, 6, 0, 0, 7, 49, 51, 271, 51, 49, 7, 0, 0, 8, 56, 60, 284, 284, 60, 56, 8, 0, 0, 9, 135, 63, 387, 313, 387, 63, 135, 9, 0, 0, 10, 142, 192, 448, 398, 398, 448, 192, 142, 10, 0

Offset: 0

Rémy Sigrist, Jul 13 2022

In other words, A(n, k) encodes the product of the polynomials encoded by n and k.

			Array A(n, k) begins:
  n\k|  0   1    2    3     4     5     6     7      8      9     10     11
  ---+---------------------------------------------------------------------
    0|  0   0    0    0     0     0     0     0      0      0      0      0
    1|  0   1    2    3     4     5     6     7      8      9     10     11
    2|  0   2    9   12    35    38    49    56    135    142    153    156
    3|  0   3   12   15    48    51    60    63    192    195    204    207
    4|  0   4   35   48   271   284   387   448   2111   2172   2275   2288
    5|  0   5   38   51   284   313   398   455   2168   2289   2502   2531
    6|  0   6   49   60   387   398   481   504   3079   3102   3185   3196
    7|  0   7   56   63   448   455   504   511   3584   3591   3640   3647
    8|  0   8  135  192  2111  2168  3079  3584  33279  33784  34695  34752
    9|  0   9  142  195  2172  2289  3102  3591  33784  34785  36622  36739
   10|  0  10  153  204  2275  2502  3185  3640  34695  36622  39993  40476
   11|  0  11  156  207  2288  2531  3196  3647  34752  36739  40476  40719
   12|  0  12  195  240  3087  3132  3843  4032  49215  49404  50115  50160

Index entries for sequences related to binary expansion of n

Cf. A001196, A097254, A101211, A355663.

toruns(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); r }
fromruns(r) = { my (v=0); for (k=1, #r, v=(v+k%2)*2^r[k]-k%2); v }
A(n,k) = { fromruns(Vec(Pol(toruns(n)) * Pol(toruns(k)))) }

A(n, k) = A(k, n).
A(n, 0) = 0.
A(n, 1) = n.
A(n, 3) = A001196(n).
A(n, 7) = A097254(n+1).
A(n, n) = A355654(n).

A370470 In the binary expansion of n, change the i-th run length to the difference of the i-th and (i-1)-th run lengths. The first run length remains as is.

Original entry on oeis.org

1, 1, 3, 2, 1, 6, 7, 4, 5, 1, 3, 3, 6, 28, 15, 8, 19, 5, 2, 2, 1, 6, 7, 6, 7, 6, 13, 14, 28, 120, 31, 16, 71, 19, 9, 10, 5, 4, 5, 4, 5, 1, 3, 3, 6, 28, 15, 12, 27, 7, 3, 12, 6, 26, 27, 7, 29, 28, 57, 60, 120, 496, 63, 32, 271, 71, 35, 38, 19, 18, 4, 20, 21, 5

Offset: 1

Aritra Mitra, Mar 30 2024

			Consider n = 988:
  binary(n)            1111  0  111  00
  run_length            4    1   3   2
  modified run_length   4    3   2   1
  binary(a(n))         1111 000  11  0
a(n) = 966.

Aritra Mitra, Table of n, a(n) for n = 1..8191
Michael De Vlieger, Plot bits of a(n), n = 1..4096, with the least bit at bottom and greatest bit at top, with 1s in black and 0s in white.
Michael De Vlieger, Fan style binary tree for a(n), n = 1..8192, with a color function showing binary weight, where red represents 1 and darkest blue 13.

Run lengths are as in A101211.

Array[FromDigits[Flatten@ MapIndexed[ConstantArray[Mod[First[#2], 2], #1] &, Prepend[Abs@ Differences[#], First[#]]], 2] &@ Map[Length, Split[IntegerDigits[#, 2]]] &, 120] (* Michael De Vlieger, Apr 19 2024 *)

def A370470(n):
    s = bin(n)[2:]
    run_length = 0
    runs = []
    last_char = '2'
    for j in range(len(s)):
        if(s[j] != last_char):
            last_char = s[j]
            runs.append(run_length)
            run_length = 1
        else:
            run_length+=1
    runs.append(run_length)
    k = ''
    for j in range(1, len(runs)):
        k+=str(chr(ord('0')+(j%2)))*abs(runs[j]-runs[j-1])
    return int(k, 2)

from itertools import groupby
def a(n):
    r = [len(list(g)) for k, g in groupby(bin(n)[2:])]
    return int("1"*r[0]+"".join(str(i&1)*abs(r[i+1]-r[i]) for i in range(len(r)-1)), 2)
print([a(n) for n in range(1, 64)]) # Michael S. Branicky, Apr 10 2024

a(2^j-1) = 2^j-1, as there is only one run.
a(2^j-2) = (2^(j-1)-1)*(2^(j-2)).
a(5*2^k+r) = a(2^k+r) for 0 <= r < 2^k; i.e., appending a '10' to the start of the binary expansion has no effect on the value.

More terms from Michael De Vlieger, Apr 19 2024

A376424 Nonnegative numbers m such that the run lengths in binary expansion of m, say (r_1, ..., r_k), satisfy r_1 + ... + r_i <> r_j + ... + r_k for any i in the interval 1..k-1 and j in the interval 2..k.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 8, 14, 15, 16, 19, 23, 24, 25, 28, 29, 30, 31, 32, 35, 47, 48, 49, 60, 61, 62, 63, 64, 67, 68, 71, 76, 79, 80, 88, 95, 96, 97, 102, 103, 110, 111, 112, 113, 114, 115, 120, 121, 122, 123, 124, 125, 126, 127, 128, 131, 132, 135, 156, 159, 160

Offset: 1

Rémy Sigrist, Sep 22 2024

Visually, if we consider a row of bricks of widths r_1, ..., r_k (in that order) above a row of widths r_k, ..., r_1 (in that order), we never have 4 bricks whose corners meet.

There are A108411(k) terms with k binary digits (ignoring leading zeros).

			The binary expansion of 35 is "100011", the corresponding run lengths are (1, 3, 2); the sums 1, 1+3 are distinct from the sums 3+2, 2, so 35 is a term. Visually, if we consider a row of bricks of widths 1, 3, 2 (in that order) above a row of widths 2, 3, 1 (in that order), we never have 4 bricks whose corners meet:
    .-.-----.---.
    | |     |   |
    .-.-.---.-.-.
    |   |     | |
    .---.-----.-.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A101211, A108411.

toruns(n) = { my (r = []); while (n, my (v = valuation(n+n%2, 2)); n \= 2^v; r = concat(v, r)); r }
is(n) = { if (n, my (r = toruns(n)); setintersect(vector(#r, k, vecsum(r[1..k])), vector(#r, k, vecsum(r[#r+1-k..#r])))==[vecsum(r)], 1); }

cp's OEIS Frontend

A376423 Nonnegative numbers m such that the run lengths in binary expansion of m, say (r_1, ..., r_k), correspond to a complete ruler: the sums r_i + ... r_j with i <= j <= k cover an initial interval of the positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A379213 a(n) is the number of nonnegative integers m such that A184615(m) = A003714(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A044888 Numbers whose base-2 run lengths alternate: even, odd, even, ...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

A175453 a(1)=1. a(n) = sum a(k), where k, taken over the runs (of both 0's and 1's) in binary n, equals the length of each run.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Extensions

A332017 a(n) is the sum of the squares of the lengths of the runs of consecutive equal digits in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A348111 Numbers k whose binary expansion starts with the concatenation of the binary expansions of the run lengths in binary expansion of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links