A333766 -id:A333766 - cp's OEIS frontend

A357186 Take the k-th composition in standard order for each part k of the n-th composition in standard order, then add up everything.

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

Offset: 0

Gus Wiseman, Sep 28 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			Composition 92 in standard order is (2,1,1,3), with compositions ((2),(1),(1),(1,1)) so a(92) = 2 + 1 + 1 + 1 + 1 = 6.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
This is the sum of A029837 over the n-th composition in standard order.
Vertex degrees are A133494.
The version for Heinz numbers of partitions is A325033.
Row sums of A357135.
First differences are A357187.
Cf. A000120, A001511, A003963, A029931, A048896, A058891, A070939, A096111, A329395, A333766, A335404, A357137.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[stc/@stc[n]/.List->Plus,{n,0,100}]

a(n) = A029837(A357134(n)).

A374994 Total cost when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the frequency-count updating strategy.

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 3, 3, 4, 5, 3, 5, 4, 5, 4, 4, 5, 6, 6, 6, 5, 5, 6, 6, 5, 6, 4, 6, 5, 5, 5, 5, 6, 7, 7, 7, 4, 9, 8, 7, 6, 8, 4, 7, 7, 8, 7, 7, 6, 7, 7, 7, 6, 6, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 10, 9, 8, 7, 6, 7, 10, 7, 10, 9, 8, 7, 9, 7, 9, 6, 6

Offset: 0

Pontus von Brömssen, Jul 27 2024

nonn

The cost of a request equals the position of the requested element in the list.

After a request, the requested element is moved so that the list is kept ordered by decreasing number of requests so far. In case of ties, the most recently requested element is placed before all other elements with the same number of requests.

			For n=931 (the smallest n for which A374992(n), A374993(n), A374995(n), and a(n) are all distinct), the 931st composition is (1, 1, 2, 4, 1, 1), giving the following development of the list:
   list   | position of requested element
  --------+------------------------------
  1 2 3 4 |         1
  ^       |
  1 2 3 4 |         1
  ^       |
  1 2 3 4 |         2
    ^     |
  1 2 3 4 |         4
        ^ |
  1 4 2 3 |         1
  ^       |
  1 4 2 3 |         1
  ^       |
  ---------------------------------------
          a(931) = 10

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, 1998, pp. 401-403.

Ran Bachrach and Ran El-Yaniv, Online list accessing algorithms and their applications: recent empirical evidence, Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, SODA ’97, New Orleans, LA, January 5-7, 1997, 53-62.
Wikipedia, Self-organizing list.

Analogous sequences for other updating strategies: A374992, A374993, A374995, A374996.

Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A374999.

The sum of a(j) over all j such that A000120(j) = k (number of requests) and A333766(j) <= m (upper bound on the requested elements) equals m^k * k * (m+1)/2. This is a consequence of the fact that the first m positions of the list are occupied by the elements 1, ..., m, as long as no element larger than m has been requested so far.

a(n) = a(A025480(n-1)) + A374999(n) for n >= 1.

A374995 Total cost when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), where a requested element at position i is moved to position floor((i+1)/2).

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 3, 3, 4, 4, 3, 5, 4, 5, 4, 4, 5, 5, 6, 5, 5, 5, 6, 6, 5, 5, 4, 6, 5, 6, 5, 5, 6, 6, 7, 6, 5, 7, 7, 6, 6, 8, 4, 6, 7, 8, 7, 7, 6, 6, 7, 6, 6, 6, 7, 7, 6, 6, 5, 7, 6, 7, 6, 6, 7, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 8, 6, 8, 8, 7, 7, 9, 6, 10, 6, 6, 7

Offset: 0

Pontus von Brömssen, Jul 27 2024

nonn

The cost of a request equals the position of the requested element in the list.

After a request for an element at position i in the list (1-based), that element is moved to position floor((i+1)/2). Apparently, Bachrach and El-Yaniv consider the similar strategy where a requested element at position i is moved to position floor(i/2)+1 (MOVE-FRACTION(2) in their terminology). With this strategy, the element at the front of the list will stay there forever.

			For n=931 (the smallest n for which A374992(n), A374993(n), A374994(n), and a(n) are all distinct), the 931st composition is (1, 1, 2, 4, 1, 1), giving the following development of the list:
   list   | position of requested element
  --------+------------------------------
  1 2 3 4 |         1
  ^       |
  1 2 3 4 |         1
  ^       |
  1 2 3 4 |         2
    ^     |
  2 1 3 4 |         4
        ^ |
  2 4 1 3 |         3
      ^   |
  2 1 4 3 |         2
    ^     |
  ---------------------------------------
          a(931) = 13

Ran Bachrach and Ran El-Yaniv, Online list accessing algorithms and their applications: recent empirical evidence, Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms, SODA ’97, New Orleans, LA, January 5-7, 1997, 53-62.
Wikipedia, Self-organizing list.

Analogous sequences for other updating strategies: A374992, A374993, A374994, A374996.

Cf. A000120, A025480, A066099 (compositions in standard order), A333766, A375000.

The sum of a(j) over all j such that A000120(j) = k (number of requests) and A333766(j) <= m (upper bound on the requested elements) equals m^k * k * (m+1)/2. This is a consequence of the fact that the first m positions of the list are occupied by the elements 1, ..., m, as long as no element larger than m has been requested so far.

a(n) = a(A025480(n-1)) + A375000(n) for n >= 1.

A374999 Position of the last requested element when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the frequency-count updating strategy.

Original entry on oeis.org

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

Offset: 1

Pontus von Brömssen, Jul 27 2024

nonn

See A374994 for details.

Analogous sequences for other updating strategies: A374997, A374998, A375000.

Cf. A025480, A066099 (compositions in standard order), A333766, A374994.

a(n) = A374994(n) - A374994(A025480(n-1)).

Sum_{j=1..m} a(n*2^j+2^(j-1)) = m*(m+1)/2 if m >= A333766(n). This is a consequence of the fact that the first m positions of the list are occupied by the elements 1, ..., m, as long as no element larger than m has been requested so far.

A375000 Position of the last requested element when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), where a requested element at position i is moved to position floor((i+1)/2).

Original entry on oeis.org

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

Offset: 1

Pontus von Brömssen, Jul 27 2024

nonn

See A374995 for details.

Analogous sequences for other updating strategies: A374997, A374998, A374999.

Cf. A025480, A066099 (compositions in standard order), A333766, A374995.

a(n) = A374995(n) - A374995(A025480(n-1)).

Sum_{j=1..m} a(n*2^j+2^(j-1)) = m*(m+1)/2 if m >= A333766(n). This is a consequence of the fact that the first m positions of the list are occupied by the elements 1, ..., m, as long as no element larger than m has been requested so far.

A333767 Length of shortest run of zeros after a one in the binary expansion of n. a(0) = 0.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 0, 4, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 1, 0, 2, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 1, 0, 2, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0

Offset: 0

Gus Wiseman, Apr 06 2020

nonn

			The binary expansion of 148 is (1,0,0,1,0,1,0,0), so a(148) = 1.

Positions of first appearances (ignoring index 0) are A000079.
Positions of terms > 0 are A022340.
Minimum prime index is A055396.
The  maximum part minus 1 is given by A087117.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Compositions without 1's are A022340.
- Sum is A070939.
- Product is A124758.
- Runs are counted by A124767.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Runs-resistance is A333628.
- Maximum is A333766.
- Minimum is A333768.
- Weakly decreasing compositions are A114994.
- Weakly increasing compositions are A225620.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
Cf. A029931, A048793, A228351, A328594, A333217, A333218, A333219, A333632.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[If[n==0,0,Min@@stc[n]-1],{n,0,100}]

For n > 0, a(n) = A333768(n) - 1.

A349153 Numbers k such that the k-th composition in standard order has sum equal to twice its reverse-alternating sum.

Original entry on oeis.org

0, 11, 12, 14, 133, 138, 143, 148, 155, 158, 160, 168, 179, 182, 188, 195, 198, 204, 208, 216, 227, 230, 236, 240, 248, 2057, 2066, 2071, 2077, 2084, 2091, 2094, 2101, 2106, 2111, 2120, 2131, 2134, 2140, 2149, 2154, 2159, 2164, 2171, 2174, 2192, 2211, 2214

Offset: 1

Gus Wiseman, Nov 17 2021

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

The reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(k-i) y_i.

			The terms and corresponding compositions begin:
    0: ()
   11: (2,1,1)
   12: (1,3)
   14: (1,1,2)
  133: (5,2,1)
  138: (4,2,2)
  143: (4,1,1,1,1)
  148: (3,2,3)
  155: (3,1,2,1,1)
  158: (3,1,1,1,2)
  160: (2,6)
  168: (2,2,4)
  179: (2,1,3,1,1)
  182: (2,1,2,1,2)
  188: (2,1,1,1,3)

These compositions are counted by A262977 up to 0's.
Except for 0, a subset of A345917.
The unreversed version is A348614.
The unreversed negative version is A349154.
The negative version is A349155.
A non-reverse unordered version is A349159, counted by A000712 up to 0's.
An unordered version is A349160, counted by A006330 up to 0's.
A003242 counts Carlitz compositions.
A011782 counts compositions.
A025047 counts alternating or wiggly compositions, complement A345192.
A034871, A097805, and A345197 count compositions by alternating sum.
A103919 counts partitions by alternating sum, reverse A344612.
A116406 counts compositions with alternating sum >=0, ranked by A345913.
A138364 counts compositions with alternating sum 0, ranked by A344619.
Cf. A000070, A000346, A001250, A001700, A008549, A027306, A058622, A088218, A114121, A120452, A294175.
Statistics of standard compositions:
- The compositions themselves are the rows of A066099.
- Number of parts is given by A000120, distinct A334028.
- Sum and product of parts are given by A070939 and A124758.
- Maximum and minimum parts are given by A333766 and A333768.
- Heinz number is given by A333219.
Classes of standard compositions:
- Partitions and strict partitions are ranked by A114994 and A333256.
- Multisets and sets are ranked by A225620 and A333255.
- Strict and constant compositions are ranked by A233564 and A272919.
- Carlitz compositions are ranked by A333489, complement A348612.
- Alternating compositions are ranked by A345167, complement A345168.

stc[n_]:=Differences[ Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
sats[y_]:=Sum[(-1)^(i-Length[y])*y[[i]],{i,Length[y]}];
Select[Range[0,1000],Total[stc[#]]==2*sats[stc[#]]&]

A357138 Minimal run-length of the n-th composition in standard order; a(0) = 0.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Gus Wiseman, Sep 18 2022

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			Composition 92 in standard order is (2,1,1,3), so a(92) = 1.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for more sequences related to standard compositions.
The version for Heinz numbers of partitions is A051904, for parts A055396.
For parts instead of run-length we have A333768, maximal A333766.
The opposite (maximal) version is A357137.
For first instead of minimal we have A357180, last A357181.
Cf. A000120, A001511, A003754, A029931, A051903, A056239, A061395, A070939, A297173, A356844, A357136.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[If[n==0,0,Min[Length/@Split[stc[n]]]],{n,0,100}]

A357181 Last run-length of the n-th composition in standard order.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 5, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 3, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 6, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1

Offset: 0

Gus Wiseman, Sep 24 2022

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			Composition 87 in standard order is (2,2,1,1,1), so a(87) = 3.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
For parts instead of run-lengths we have A001511, first A065120.
For Heinz numbers of partitions we have A071178, first A067029.
This is the last part of row n of A333769.
For maximal instead of last we have A357137, minimal A357138.
The first instead of last run-length is A357180.
A051903 gives maximal part of prime signature.
A061395 gives maximal prime index.
A124767 counts runs in standard compositions.
A286470 gives maximal difference of prime indices.
A333766 gives maximal part of standard composition, minimal A333768.
A353847 ranks run-sums of standard compositions.
Cf. A000120, A003754, A029931, A070939, A329395, A356841, A356844, A357134, A357135, A357136.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[If[n==0,0,Last[Length/@Split[stc[n]]]],{n,0,100}]

A375001 Square array read by antidiagonals: T(n,k) is the position of the last requested element when the elements of the k-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the move-ahead(n) updating strategy; n >= 0, k >= 1.

Original entry on oeis.org

1, 2, 1, 1, 2, 1, 3, 1, 2, 1, 1, 3, 1, 2, 1, 2, 2, 3, 1, 2, 1, 1, 2, 2, 3, 1, 2, 1, 4, 1, 2, 2, 3, 1, 2, 1, 1, 4, 1, 2, 2, 3, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 2, 1, 1, 1, 2, 4, 1, 2, 2, 3, 1, 2, 1, 3, 1, 1, 2, 4, 1, 2, 2, 3, 1, 2, 1, 1, 3, 1, 1, 2, 4, 1, 2, 2, 3, 1, 2, 1

Offset: 0

Pontus von Brömssen, Jul 27 2024

See A374996 for details.

			Array begins:
  n\k| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
  ---+--------------------------------------------
   0 | 1  2  1  3  1  2  1  4  1  2  1  3  1  2  1
   1 | 1  2  1  3  2  2  1  4  1  1  1  3  2  2  1
   2 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   3 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   4 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   5 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   6 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   7 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   8 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
   9 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
  10 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
  11 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
  12 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
  13 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
  14 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1
  15 | 1  2  1  3  2  2  1  4  2  1  1  3  2  2  1

Cf. A007814, A025480, A374998 (row n=1), A333766, A374996, A374997.

T(0,k) = A007814(k) + 1.
T(1,k) = A374998(k).
T(n,k) = A374997(k) if n >= A333766(k)-1.
T(n,k) = A374996(n,k) - A374996(n,A025480(k-1)).
Sum_{j=1..m} T(n,k*2^j+2^(j-1)) = m*(m+1)/2 if m >= A333766(k). This is a consequence of the fact that the first m positions of the list are occupied by the elements 1, ..., m, as long as no element larger than m has been requested so far.

cp's OEIS Frontend

A357186 Take the k-th composition in standard order for each part k of the n-th composition in standard order, then add up everything.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A374994 Total cost when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the frequency-count updating strategy.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A374995 Total cost when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), where a requested element at position i is moved to position floor((i+1)/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A374999 Position of the last requested element when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), using the frequency-count updating strategy.

Views

Author

Keywords

Comments

Crossrefs

Formula

A375000 Position of the last requested element when the elements of the n-th composition (in standard order) are requested from a self-organizing list initialized to (1, 2, 3, ...), where a requested element at position i is moved to position floor((i+1)/2).

Views

Author

Keywords

Comments

Crossrefs

Formula

A333767 Length of shortest run of zeros after a one in the binary expansion of n. a(0) = 0.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A349153 Numbers k such that the k-th composition in standard order has sum equal to twice its reverse-alternating sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A357138 Minimal run-length of the n-th composition in standard order; a(0) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A357181 Last run-length of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links