A339887 Number of factorizations of n into primes or squarefree semiprimes.

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, 4, 1, 1, 2, 2, 2, 3, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 5, 1, 2, 2, 1, 2, 4, 1, 2, 2, 4, 1, 3, 1, 2, 2, 2, 2, 4, 1, 2, 1, 2, 1, 5, 2, 2, 2

Offset

1,6

Comments

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.

Conjecture: also the number of semistandard Young tableaux whose entries are the prime indices of n (A323437).

Is this a duplicate of A323437? - R. J. Mathar, Jan 05 2021

Links

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

Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Formula

a(A002110(n)) = A000085(n), and in general if n is a product of k distinct primes, a(n) = A000085(k).

a(n) = Sum_{d|n} A320656(n/d), so A320656 is the Moebius transform of this sequence.

Example

The a(n) factorizations for n = 36, 60, 180, 360, 420, 840:
  6*6       6*10      5*6*6       6*6*10        2*6*35      6*10*14
  2*3*6     2*5*6     2*6*15      2*5*6*6       5*6*14      2*2*6*35
  2*2*3*3   2*2*15    3*6*10      2*2*6*15      6*7*10      2*5*6*14
            2*3*10    2*3*5*6     2*3*6*10      2*10*21     2*6*7*10
            2*2*3*5   2*2*3*15    2*2*3*5*6     2*14*15     2*2*10*21
                      2*3*3*10    2*2*2*3*15    2*5*6*7     2*2*14*15
                      2*2*3*3*5   2*2*3*3*10    3*10*14     2*2*5*6*7
                                  2*2*2*3*3*5   2*2*3*35    2*3*10*14
                                                2*2*5*21    2*2*2*3*35
                                                2*2*7*15    2*2*2*5*21
                                                2*3*5*14    2*2*2*7*15
                                                2*3*7*10    2*2*3*5*14
                                                2*2*3*5*7   2*2*3*7*10
                                                            2*2*2*3*5*7

Mathematica

sqpe[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[sqpe[n/d], Min@@#>=d&]], {d, Select[Divisors[n], PrimeQ[#]||SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Table[Length[sqpe[n]], {n, 100}]

Crossrefs

See link for additional cross-references.

Only allowing only primes gives A008966.

Not allowing primes gives A320656.

Unlabeled multiset partitions of this type are counted by A320663/A339888.

Allowing squares of primes gives A320732.

The strict version is A339742.

A001055 counts factorizations.

A001358 lists semiprimes, with squarefree case A006881.

A002100 counts partitions into squarefree semiprimes.

A338899/A270650/A270652 give the prime indices of squarefree semiprimes.

Cf. A000070, A000961, A001221, A096373, A320893, A338914, A339740, A339741, A339841, A339846.

Sequence in context: A318369 A007875 A323437 * A259936 A354870 A050320

Adjacent sequences: A339884 A339885 A339886 * A339888 A339889 A339890

Keyword

nonn

Author

Gus Wiseman, Dec 22 2020

Status

approved