A391623 Positive integers k such that there is more than one nonnegative sequence whose first sums are the k-th composition in standard order.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 46, 47, 48, 52, 53, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 82, 84

Offset

1,2

Comments

The first sums of a nonempty sequence (a, b, c, d, ...) are (a+b, b+c, c+d, ...).

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.

Also numbers k such that there is a unique integer b such that the b-based partial alternating sums of the k-th composition in standard order are all nonnegative. Here, the b-based partial alternating sums of a finite sequence q are given by pas(q,b)_j = (-1)^j * b + Sum_{i=1..j} (-1)^(i+j) * q_i. This is a signed version of the partial sums transformation, inverse to the "first sums" transformation.

Links

Table of n, a(n) for n=1..67.

Formula

Complement of (A390747 U A391622).

Example

For n = 54, the composition (1,2,1,2) is the first sums of (0,1,1,0,2) only, so 54 is not in the sequence.
For n = 150, all sequences with first sums (3,2,1,2) are of the form (b,3-b,-1+b,2-b,b) for some b. This is nonnegative for b = 1 or b = 2, so 150 is in the sequence.

Mathematica

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
pas[y_, k_]:=Table[(-1)^j*k+Sum[(-1)^(i+j)*y[[i]], {i, j}], {j, 0, Length[y]}];
Select[Range[100], Length[Select[Table[pas[stc[#], b], {b, 0, Max[stc[#]]}], Min@@#>=0&]]>1&]

Crossrefs

For no choices we have A390747, count A391645.

These are positions of terms > 1 in A391621.

For a unique choice we have A391622, count A391643.

These compositions are counted by A391682.

For compositions we have:

- at least one choice: A390676, count A391683

- no choices: A390677, count A391680

- unique choice: A390745, count A391644

- more than one choice: A391627, count A391628

A011782 counts compositions.

A066099 lists all compositions in standard order.

A357213 counts compositions by sum of first sums.

A390432 lists first sums of standard compositions.

A390449 ranks first sums of prime indices, listed by A390307 or A390362.

A390673 ranks compositions with distinct first sums, counted by A390567.

A390674 ranks compositions with equal first sums, counted by A342527.

A391642 counts compositions with standard first sums.

Cf. A000120, A001511, A029837, A029931, A070939, A390448, A390568, A390675, A390678, A391983.

Sequence in context: A371968 A335467 A374768 * A256474 A085824 A351290

Adjacent sequences: A391620 A391621 A391622 * A391624 A391625 A391626

Keyword

nonn

Author

Gus Wiseman, Jan 02 2026

Status

approved