A391626 Numbers k such that the k-th composition in standard order is the first sums of some composition into parts > 1.

8, 16, 32, 64, 128, 136, 256, 264, 272, 512, 520, 528, 544, 1024, 1032, 1040, 1056, 1088, 2048, 2056, 2064, 2080, 2112, 2176, 2184, 4096, 4104, 4112, 4128, 4160, 4224, 4232, 4352, 4368, 8192, 8200, 8208, 8224, 8256, 8320, 8328, 8448, 8456, 8464, 8704, 8720

Offset

1,1

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 some integer b such that the b-based partial alternating sums of the k-th composition in standard order are all > 1. 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..46.

Example

The 8464-th composition in standard order is (5,4,5), which is the first sums of (3,2,2,3), so 8464 is in the sequence.
The terms together with standard compositions begin:
     8: (4)
    16: (5)
    32: (6)
    64: (7)
   128: (8)
   136: (4,4)
   256: (9)
   264: (5,4)
   272: (4,5)
   512: (10)
   520: (6,4)
   528: (5,5)
   544: (4,6)

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]}];
nag[m_]:=Select[Table[pas[m, b], {b, 1, Max[m]}], Min@@#>1&]!={};
Select[Range[1000], nag[stc[#]]&]

Crossrefs

These compositions are counted by A391235, complement A391641.

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.

A390673 ranks compositions with distinct first sums, count A390567.

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

A390678 ranks compositions with no 1's that are not first sums.

A391642 counts compositions with standard first sums.

For nonnegative sequences we have:

- no choices: A390747, counted by A391645.

- a unique choice: A391622, counted by A391643.

- more than one choice: A391623, counted by A391682.

For compositions (allowing 1's) we have:

- more than one choice: A391628, ranks A391627

- unique choice: A391644, ranks A390745

- no choices: A391680, ranks A390677

- at least one choice: A391683, ranks A390676 (union of A390568)

Cf. A000120, A029931, A070939, A070211, A390307, A390446, A390448, A390675, A391620, A391621, A391983.

Sequence in context: A345053 A256817 A281016 * A048169 A089882 A335850

Adjacent sequences: A391623 A391624 A391625 * A391627 A391628 A391629

Keyword

nonn

Author

Gus Wiseman, Jan 07 2026

Status

approved