A335516 Number of normal patterns contiguously matched by the prime indices of n in increasing or decreasing order, counting multiplicity.

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

Offset

1,2

Comments

First differs from A181796 at a(180) = 9, A181796(180) = 10.

First differs from A335549 at a(90) = 7, A335549(90) = 8.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to contiguously match a pattern P if there is a contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) contiguously matches (1,1,2) and (2,1,1) but not (2,1,2), (1,2,1), (1,2,2), or (2,2,1).

Links

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

Wikipedia, Permutation pattern

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Example

The a(n) patterns for n = 2, 30, 12, 60, 120, 540, 1500:
  ()   ()     ()     ()      ()       ()        ()
  (1)  (1)    (1)    (1)     (1)      (1)       (1)
       (12)   (11)   (11)    (11)     (11)      (11)
       (123)  (12)   (12)    (12)     (12)      (12)
              (112)  (112)   (111)    (111)     (111)
                     (123)   (112)    (112)     (112)
                     (1123)  (123)    (122)     (122)
                             (1112)   (1112)    (123)
                             (1123)   (1122)    (1123)
                             (11123)  (1222)    (1222)
                                      (11222)   (1233)
                                      (12223)   (11233)
                                      (112223)  (12333)
                                                (112333)

Mathematica

primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i, {i, Length[Union[q]]}];
Table[Length[Union[mstype/@ReplaceList[primeMS[n], {___, s___, ___}:>{s}]]], {n, 100}]

Crossrefs

The version for standard compositions is A335458.

The not necessarily contiguous version is A335549.

Patterns are counted by A000670 and ranked by A333217.

A number's prime indices are given in the rows of A112798.

Contiguous subsequences of standard compositions are A124771.

Contiguous sub-partitions of prime indices are counted by A335519.

Minimal avoided patterns of prime indices are counted by A335550.

Patterns contiguously matched by partitions are counted by A335838.

Cf. A000005, A056239, A056986, A108917, A124770, A181796, A269134, A333224, A334299, A335457, A335837.

Sequence in context: A327394 A088873 A085082 * A335549 A181796 A319686

Adjacent sequences: A335513 A335514 A335515 * A335517 A335518 A335519

Keyword

nonn

Author

Gus Wiseman, Jun 26 2020

Status

approved