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

Author

Gus Wiseman, Dec 20 2020

Keywords

• nonn

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.

Examples

			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)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..69300
• Index entries for sequences computed from exponents in factorization of n

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.

Programs

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}]

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) && (dA353471(d), s += A339742(n/d, d))); (s)); \\ Antti Karttunen, May 02 2022

Formula

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

Extensions

More terms from Antti Karttunen, May 02 2022