A339839 Number of factorizations of n into distinct primes or semiprimes.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 0, 2, 2, 2, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 5, 1, 2, 2, 0, 2, 4, 1, 2, 2, 4, 1, 2, 1, 2, 2, 2, 2, 4, 1, 1, 0, 2, 1, 5, 2, 2, 2, 2, 1, 5, 2, 2, 2, 2, 2, 0, 1, 2, 2, 2, 1, 4, 1, 2, 4

Offset

1,6

Comments

A semiprime (A001358) is a product of any two prime numbers.

Links

Antti Karttunen, Table of n, a(n) for n = 1..100000

Index entries for sequences computed from exponents in factorization of n

Formula

a(n) = Sum_{d|n squarefree} A322353(n/d).

Example

The a(n) factorizations for n = 6, 16, 30, 60, 180, 210, 240, 420:
  6    5*6    4*15    4*5*9    6*35     4*6*10    2*6*35
  2*3  2*15   6*10    2*6*15   10*21    2*4*5*6   3*4*35
       3*10   2*5*6   2*9*10   14*15    2*3*4*10  4*5*21
       2*3*5  3*4*5   3*4*15   5*6*7              4*7*15
              2*3*10  3*6*10   2*3*35             5*6*14
                      2*3*5*6  2*5*21             6*7*10
                               2*7*15             2*10*21
                               3*5*14             2*14*15
                               3*7*10             2*5*6*7
                               2*3*5*7            3*10*14
                                                  3*4*5*7
                                                  2*3*5*14
                                                  2*3*7*10

Mathematica

facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], UnsameQ@@#&&SubsetQ[{1, 2}, PrimeOmega/@#]&]], {n, 100}]

Prog

(PARI) A339839(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (d<u) && (bigomega(d)<3), s += A339839(n/d, d))); (s)); \\ Antti Karttunen, Feb 10 2023

Crossrefs

A008966 allows only primes.

A320732 is the non-strict version.

A339742 does not allow squares of primes.

A339840 lists the positions of zeros.

A001358 lists semiprimes, with squarefree case A006881.

A002100 counts partitions into squarefree semiprimes.

A013929 cannot be factored into distinct primes.

A293511 are a product of distinct squarefree numbers in exactly one way.

A320663 counts non-isomorphic multiset partitions into singletons or pairs.

A339841 have exactly one factorization into primes or semiprimes.

The following count factorizations:

- A001055 into all positive integers > 1.

- A320655 into semiprimes.

- A320656 into squarefree semiprimes.

- A322353 into distinct semiprimes.

- A339839 [this sequence] into distinct primes or semiprimes.

The following count vertex-degree partitions and give their Heinz numbers:

- A000569 counts graphical partitions (A320922).

- A339656 counts loop-graphical partitions (A339658).

Cf. A000070, A001222, A028260, A320893, A338898, A339617, A339661, A339740, A339741, A339846.

Sequence in context: A344772 A307610 A125029 * A062893 A328512 A302041

Adjacent sequences: A339836 A339837 A339838 * A339840 A339841 A339842

Keyword

nonn

Author

Gus Wiseman, Dec 20 2020

Extensions

Data section extended up to a(105) by Antti Karttunen, Feb 10 2023

Status

approved