A339742 Number of factorizations of n into distinct primes or squarefree semiprimes.

1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 4, 1, 0, 2, 2, 2, 1, 1, 2, 2, 0, 1, 4, 1, 1, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 2, 0, 2, 2, 1, 3, 1, 2, 1, 0, 2, 4, 1, 1, 2, 4, 1, 0, 1, 2, 1, 1, 2, 4, 1, 0, 0, 2, 1, 3, 2, 2, 2, 0, 1, 3, 2, 1, 2, 2, 2, 0, 1, 1, 1, 1, 1, 4, 1, 0, 4

Offset

1,6

Comments

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

The following are equivalent characteristics for any positive integer n:

(1) the prime factors of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops and edges;

(2) n can be factored into distinct primes or squarefree semiprimes.

Links

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

Index entries for sequences computed from exponents in factorization of n

Formula

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

Example

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

Mathematica

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

Prog

(PARI)
A353471(n) = (numdiv(n)==2*omega(n));
A339742(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (d<u) && A353471(d), s += A339742(n/d, d))); (s)); \\ Antti Karttunen, May 02 2022

Crossrefs

Dirichlet convolution of A008966 with A339661.

A008966 allows only primes.

A339661 does not allow primes, only squarefree semiprimes.

A339740 lists the positions of zeros.

A339741 lists the positions of positive terms.

A339839 allows nonsquarefree semiprimes.

A339887 is the non-strict version.

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.

A339840 cannot be factored into distinct primes or semiprimes.

A339841 have exactly one factorization into primes or semiprimes.

The following count factorizations:

- A001055 into all positive integers > 1.

- A050320 into squarefree numbers.

- A050326 into distinct squarefree numbers.

- A320655 into semiprimes.

- A320656 into squarefree semiprimes.

- A320732 into primes or semiprimes.

- A322353 into distinct semiprimes.

- A339742 [this sequence] into distinct primes or squarefree semiprimes.

- A339839 into distinct primes or semiprimes.

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

- A000569 counts graphical partitions (A320922).

- A058696 counts all partitions of 2n (A300061).

- A209816 counts multigraphical partitions (A320924).

- A339656 counts loop-graphical partitions (A339658).

-

The following count partitions/factorizations of even length and give their Heinz numbers:

- A027187/A339846 has no additional conditions (A028260).

- A338914/A339562 can be partitioned into edges (A320911).

- A338916/A339563 can be partitioned into distinct pairs (A320912).

- A339559/A339564 cannot be partitioned into distinct edges (A320894).

- A339560/A339619 can be partitioned into distinct edges (A339561).

Cf. A000070, A001221, A005117, A320893, A320923, A338899, A339113, A339617, A353471.

Sequence in context: A332040 A263251 A318370 * A345164 A050326 A335452

Adjacent sequences: A339739 A339740 A339741 * A339743 A339744 A339745

Keyword

nonn

Author

Gus Wiseman, Dec 20 2020

Extensions

More terms from Antti Karttunen, May 02 2022

Status

approved