A120385 -id:A120385 - cp's OEIS frontend

A080277 Partial sums of A038712.

1, 4, 5, 12, 13, 16, 17, 32, 33, 36, 37, 44, 45, 48, 49, 80, 81, 84, 85, 92, 93, 96, 97, 112, 113, 116, 117, 124, 125, 128, 129, 192, 193, 196, 197, 204, 205, 208, 209, 224, 225, 228, 229, 236, 237, 240, 241, 272, 273, 276, 277, 284, 285, 288, 289, 304, 305, 308

Offset: 1

N. J. A. Sloane, Mar 19 2003

nonn

			From _Omar E. Pol_, Sep 10 2019: (Start)
Illustration of initial terms:
a(n) is also the total area (or the total number of cells) in first n regions of an infinite diagram of compositions (ordered partitions) of the positive integers, where the length of the n-th horizontal line segment is equal to A001511(n), the length of the n-th vertical line segment is equal to A006519(n), and area of the n-th region is equal to A038712(n), as shown below (first eight regions):
-----------------------------------
n  A038712(n)  a(n)       Diagram
-----------------------------------
.                         _ _ _ _
1      1         1       |_| | | |
2      3         4       |_ _| | |
3      1         5       |_|   | |
4      7        12       |_ _ _| |
5      1        13       |_| |   |
6      3        16       |_ _|   |
7      1        17       |_|     |
8     15        32       |_ _ _ _|
.
The above diagram represents the eight compositions of 4: [1,1,1,1],[2,1,1],[1,2,1],[3,1],[1,1,2],[2,2],[1,3],[4].
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..16383
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013-2014.
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, Journal of Graph Algorithms and Applications 18(2) (2014), 177-209.
Klaus Brockhaus, Illustration of A038712 and A080277.
B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions. [ps file]
Ralf Stephan, Table of generating functions. [pdf file]

Cf. A001787, A038712, A050292, A080333, A120385.

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 40, 41, 41, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48, 49, 49, 50, 51, 52, 52, 53, 54

Offset: 0

Eric W. Weisstein

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.
Least k such that a(k)=n is equal to A003159(n).
To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004
Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011
Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013

			Examples for n = 1 through 8: {1}, {1}, {1,3}, {1,3,4}, {1,3,4,5}, {1,3,4,5}, {1,3,4,5,7}, {1,3,4,5,7}.
Binary expansion of 5 is 101, so Sum{i>=0} b_i*(-1)^i = 2. Therefore a(5) = 10/3 + 2/3 = 4. - _Vladimir Shevelev_, Apr 15 2010

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Double-Free Set.

Bisection of A123087.

Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.

a050292 n = a050292_list !! (n-1)
a050292_list = scanl (+) 0 a035263_list
-- Reinhard Zumkeller, Jan 21 2013

A050292:=n->add((-1)^k*floor(n/2^k), k=0..n); seq(A050292(n), n=0..100); # Wesley Ivan Hurt, Feb 14 2014

a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* Harvey P. Dale, Apr 29 2018 *)

PARI
```
a(n)=if(n<2,1,n-a(floor(n/2)))
```

from sympy.ntheory import digits
def A050292(n): return ((n<<1)+sum((0,1,-1,0)[i] for i in digits(n,4)[1:]))//3 # Chai Wah Wu, Jan 30 2025

Partial sums of A035263. Close to (2/3)*n.
a(n) = A123087(2*n) = n - A123087(n). - Max Alekseyev, Mar 05 2023
From Benoit Cloitre, Nov 24 2002: (Start)
a(1)=1, a(n) = n - a(floor(n/2));
a(n) = (2/3)*n + (1/3)*A065359(n);
more generally, for m>=0, a(2^m*n) - 2^m*a(n) = A001045(m)*A065359(n) where A001045(m) = (2^m - (-1)^m)/3 is the Jacobsthal sequence;
a(A039004(n)) = (2/3)*A039004(n);
a(2*A039004(n)) = 2*a(A039004(n));
a(A003159(n)) = n;
a(A003159(n)-1) = n-1;
a(n) mod 2 = A010060(n) the Thue-Morse sequence;
a(n+1) - a(n) = A035263(n+1);
a(n+2) - a(n) = abs(A029884(n)).
(End)
G.f.: (1/(x-1)) * Sum_{i>=0} (-1)^i*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - Benoit Cloitre, Jun 03 2003
a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - Philippe Deléham, Mar 26 2004
a(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
If n = Sum_{i>=0} b_i*2^i is the binary expansion of n, then a(n) = 2n/3 + (1/3)Sum_{i>=0} b_i*(-1)^i. Thus a(n) = 2n/3 + O(log(n)). - Vladimir Shevelev, Apr 15 2010
Moreover, the equation a(3m)=2m has infinitely many solutions, e.g., a(3*2^k)=2*2^k; on the other hand, a((4^k-1)/3)=(2*(4^k-1))/9+k/3, i.e., limsup |a(n)-2n/3| = infinity. - Vladimir Shevelev, Feb 23 2011
a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - Philippe Deléham, Oct 19 2011
From Peter Bala, Feb 02 2013: (Start)
Product_{n >= 1} (1 + x^((2^n - (-1)^n)/3 )) = (1 + x)^2(1 + x^3)(1 + x^5)(1 + x^11)(1 + x^21)... = 1 + sum {n >= 1} x^a(n) = 1 + 2x + x^2 + x^3 + 2x^4 + 2x^5 + .... Hence this sequence lists the numbers representable as a sum of distinct Jacobsthal numbers A001045 = [1, 1', 3, 5, 11, 21, ...], where we distinguish between the two occurrences of 1 by writing them as 1 and 1'. For example, 9 occurs twice in the present sequence because 9 = 5 + 3 + 1 and 9 = 5 + 3 + 1'. Cf. A197911 and A080277. See also A120385.
(End)

Extended with formula by Christian G. Bower, Sep 15 1999
Corrected and extended by Reinhard Zumkeller, Aug 16 2006
Extended with formula by Philippe Deléham, Oct 19 2011
Entry revised to give a simpler definition by N. J. A. Sloane, Jan 03 2014

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 6, 3, 8, 16, 24, 24, 24, 16, 8, 20, 60, 100, 120, 120, 120, 100, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210

Offset: 0

Alois P. Heinz, Feb 12 2019

T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).

T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
T(4,4) = 3: 1234, 1243, 1324.
T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   1;
   1,   1;
   2,   2,   2;
   3,   6,   6,   6,   3;
   8,  16,  24,  24,  24,  16,   8;
  20,  60, 100, 120, 120, 120, 100,  60,  20;
  80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Marko Riedel, math.stackexchange.com, Average number of inversions in a random binary heap on 2^n-1 elements.
Marko Riedel, Average number of inversions in a random binary heap on 2^n-1 elements (PDF).
Eric Weisstein's World of Mathematics, Heap,
Wikipedia, Binary heap.
Wikipedia, Permutation.

Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
Row sums give A000142.
Central terms (also maxima) of rows give A324075.
Cf. A000523, A008302, A061168, A120385, A306343, A324074, A372640.
Average number of inversions of a full binary heap on 2^n-1 elements is A000337.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
     If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
     Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
     Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 15 2021, after Alois P. Heinz *)

T(n,k) = T(n,A061168(n)-k) for n > 0.

Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).

A123390 Triangle read by rows: n-th row starts with n and continues with half the previous value as long as that is even.

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Oct 13 2006

A fractal sequence, generated by the rule a(n) is a new maximum when a(n-1) is odd and a repetition of an earlier value when a(n-1) is even.
From Flávio V. Fernandes, Mar 13 2025: (Start)
a(n) is given by A003602(n) at A001511(n) diagram
  1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9
  . 1 . . . 2 . . . 3 . . . 4 . . .
  . . . 1 . . . . . . . 2 . . . . .
  . . . . . . . 1 . . . . . . . . .
  . . . . . . . . . . . . . . . 1 .
read by backwards 2^n, which is given by A118319(n) at A001511(n) diagram
  1 . 2 . 4 . 5 . 8 . 9 .11 .12 .16
  . 3 . . . 6 . . .10 . . .13 . . .
  . . . 7 . . . . . . .14 . . . . .
  . . . . . . .15 . . . . . . . . .
  . . . . . . . . . . . . . . .31 . - see formula. (End)

			Triangle starts
  1;
  2, 1;
  3;
  4, 2, 1;
  5;
  6, 3;
  7;
  8, 4, 2, 1;
  9;
  10, 5;
  11;
  12, 6, 3;
  13;

Alois P. Heinz, Rows n = 1..10000, flattened

Row lengths are A001511.
Row sums give A129527.
Cf. A120385.
Cf. A003602, A108918, A118319.

T:= proc(n) local m,l; m:=n; l:= m;
      while irem(m, 2, 'm')=0 do l:=l,m od: l
    end:
seq(T(n), n=1..40);  # Alois P. Heinz, Oct 09 2015

Flatten[Function[n, NestWhile[Append[#, Last[#]/2] &, {n}, EvenQ[Last[#]] &]][#] & /@ Range[20]] (* Birkas Gyorgy, Apr 13 2011 *)

a(1) = 1, for n > 1, if a(n-1) is even, a(n) = a(n-1)/2, otherwise a(n) = (max_{k

Ordinal transform of A082850.

a(n) = A003602(A108918(n)). - Flávio V. Fernandes, Mar 13 2025

A233932 Irregular table read by rows: T(n,k) is the binary representation of n shifted right k times and incremented if the last bit shifted away was set.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 4, 2, 1, 4, 2, 1, 1, 5, 2, 1, 1, 5, 3, 1, 1, 6, 3, 1, 1, 6, 3, 2, 1, 7, 3, 2, 1, 7, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 1, 1, 9, 4, 2, 1, 1, 9, 5, 2, 1, 1, 10, 5, 2, 1, 1, 10, 5, 3, 1, 1, 11, 5, 3, 1, 1, 11, 6, 3, 1, 1, 12, 6, 3, 1, 1, 12, 6, 3, 2, 1, 13, 6, 3, 2, 1, 13, 7, 3, 2, 1, 14, 7

Offset: 1

Ralf Stephan, Dec 18 2013

The last bit shifted away is the (k-1)-th bit from the right.
The length of the n-th row is A070939(n).
Terms in the n-th row add to n.
From Gary W. Adamson, Jun 07 2021: (Start)
A production matrix is the irregular triangle (n, A001511(k)) = 1 otherwise 0:
  1;
  0, 1;
  1;
  0, 0, 1;
  1;
  0, 1;
  1;
  0, 0, 0, 1;
  ...
Let the matrix = M, then take partial sums from the top -> down, by columns.
The result is A233932. If the 1's are replaced by any sequence, say 2n-1, the result using the same procedure is an analogous sequence with row sums equal to the partial sums of the replacement sequence. For example, with (1, 3, 5, 7, ...) the result is an array with row sums = the squares, (1, 4, 9, 16, 25, ...), as follows:
   1;
   1,  3;
   6,  3;
   6,  3,  7;
  15,  3,  7;
  15, 14,  7;
  28, 14,  7;
  28, 14,  7, 15;
  45, 14,  7, 15;
  45, 37,  7, 15;
  ...  (End)

			22 in binary is 10110, so the row length is 5. T(22, 1) = 11, T(22, 2) = 5 + 1 = 6, T(22, 3) = 2 + 1 = 3, T(22, 4) = 1, T(22, 5) = 0 + 1. So the 22nd row reads 11, 6, 3, 1, 1.
Table starts:
  1;
  1, 1;
  2, 1;
  2, 1, 1;
  3, 1, 1;
  3, 2, 1;
  4, 2, 1;
  4, 2, 1, 1;
  5, 2, 1, 1;
  5, 3, 1, 1;
  ...

Index entries for sequences related to binary expansion of n

Cf. A120385.

Cf. A079559.

PARI
```
T(n,k)=b=binary(n);n\2^k+b[#b-k+1]
```

row(n) = my(b=binary(n)); vector(#b, k, n\2^k+b[#b-k+1]); \\ Michel Marcus, Sep 03 2019

T(n,k) = round(n/2^k), 1 <= k <= floor(log_2(n)) + 1, where round(1/2)=1. - Ridouane Oudra, Sep 02 2019

Showing 1-5 of 5 results.

cp's OEIS Frontend

A080277 Partial sums of A038712.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A123390 Triangle read by rows: n-th row starts with n and continues with half the previous value as long as that is even.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A233932 Irregular table read by rows: T(n,k) is the binary representation of n shifted right k times and incremented if the last bit shifted away was set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula