A353401 Number of integer compositions of n with all prime run-lengths.

1, 0, 1, 1, 1, 1, 4, 3, 6, 9, 10, 18, 27, 35, 54, 83, 107, 176, 242, 354, 515, 774, 1070, 1648, 2332, 3429, 4984, 7326, 10521, 15591, 22517, 32908, 48048, 70044, 101903, 149081, 216973, 316289, 461959, 672664, 981356, 1431256, 2086901, 3041577, 4439226, 6467735

Offset: 0

Author

Gus Wiseman, May 15 2022

Keywords

• nonn

Examples

			The a(0) = 1 through a(9) = 9 compositions (empty column indicated by dot, 0 is the empty composition):
  0   .  11   111   22   11111   33     11122     44       333
                                 222    22111     1133     11133
                                 1122   1111111   3311     33111
                                 2211             11222    111222
                                                  22211    222111
                                                  112211   1111122
                                                           1112211
                                                           1122111
                                                           2211111
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

Crossrefs

The case of runs equal to 2 is A003242 aerated.

The <= 1 version is A003242 ranked by A333489.

The version for parts instead of run-lengths is A023360, both A353429.

The version for partitions is A055923.

The > 1 version is A114901, ranked by A353427.

The <= 2 version is A128695, matching A335464.

The > 2 version is A353400, partitions A100405.

Words with all distinct run-lengths: A032020, A044813, A098859, A130091, A329739, A351013, A351017.

A005811 counts runs in binary expansion.

A008466 counts compositions with some part > 2.

A011782 counts compositions.

A167606 counts compositions with adjacent parts coprime.

A329738 counts uniform compositions, partitions A047966.

Cf. A078012, A165413, A175413, A274174, A333381, A333755, A353390, A353391, A353392, A353402, A353403.

Programs

Maple

b:= proc(n, h) option remember; `if`(n=0, 1, add(`if`(i<>h, add(
     `if`(isprime(j), b(n-i*j, i), 0), j=2..n/i), 0), i=1..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, May 18 2022

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Length/@Split[#],_?(!PrimeQ[#]&)]&]],{n,0,15}]

Extensions

a(21)-a(45) from Alois P. Heinz, May 18 2022