A333175 - OEIS

A333175

If n = Product (p_j^k_j) then a(n) = Sum (a(n/p_j^k_j)), with a(1) = 1.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 6, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 6, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 6, 1, 2, 2, 1, 2, 6, 1, 2, 2, 6, 1, 2, 1, 2, 2, 2, 2, 6, 1, 2, 1, 2, 1, 6, 2, 2, 2, 2, 1, 6, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

Number of ordered prime factorizations of radical of n.

Number of permutations of the prime indices of n (counting multiplicity) avoiding the patterns (1,2,1) and (2,1,2). These are permutations with all equal parts contiguous. Depends only on sorted prime signature (A118914). - Gus Wiseman, Jun 27 2020

LINKS

Robert Israel, Table of n, a(n) for n = 1..10000

Wikipedia, Permutation pattern

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

FORMULA

a(1) = 1; a(n) = Sum_{d|n, d < n, gcd(d, n/d) = 1} A069513(n/d) * a(d).

a(n) = A000142(A001221(n)).

EXAMPLE

From Gus Wiseman, Jun 27 2020 (Start)

The a(n) permutations of prime indices for n = 2, 12, 60:

(1) (112) (1123)

(211) (1132)