login
Number of factorizations of n into distinct primes or squarefree semiprimes.
12

%I #24 May 02 2022 17:28:30

%S 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,

%T 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,

%U 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

%N Number of factorizations of n into distinct primes or squarefree semiprimes.

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

%C The following are equivalent characteristics for any positive integer n:

%C (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;

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

%H Antti Karttunen, <a href="/A339742/b339742.txt">Table of n, a(n) for n = 1..69300</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

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

%e The a(n) factorizations for n = 6, 30, 60, 210, 420 are respectively 2, 4, 3, 10, 9:

%e (6) (5*6) (6*10) (6*35) (2*6*35)

%e (2*3) (2*15) (2*5*6) (10*21) (5*6*14)

%e (3*10) (2*3*10) (14*15) (6*7*10)

%e (2*3*5) (5*6*7) (2*10*21)

%e (2*3*35) (2*14*15)

%e (2*5*21) (2*5*6*7)

%e (2*7*15) (3*10*14)

%e (3*5*14) (2*3*5*14)

%e (3*7*10) (2*3*7*10)

%e (2*3*5*7)

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

%t Table[Length[sqps[n]],{n,100}]

%o (PARI)

%o A353471(n) = (numdiv(n)==2*omega(n));

%o 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

%Y Dirichlet convolution of A008966 with A339661.

%Y A008966 allows only primes.

%Y A339661 does not allow primes, only squarefree semiprimes.

%Y A339740 lists the positions of zeros.

%Y A339741 lists the positions of positive terms.

%Y A339839 allows nonsquarefree semiprimes.

%Y A339887 is the non-strict version.

%Y A001358 lists semiprimes, with squarefree case A006881.

%Y A002100 counts partitions into squarefree semiprimes.

%Y A013929 cannot be factored into distinct primes.

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

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

%Y A339840 cannot be factored into distinct primes or semiprimes.

%Y A339841 have exactly one factorization into primes or semiprimes.

%Y The following count factorizations:

%Y - A001055 into all positive integers > 1.

%Y - A050320 into squarefree numbers.

%Y - A050326 into distinct squarefree numbers.

%Y - A320655 into semiprimes.

%Y - A320656 into squarefree semiprimes.

%Y - A320732 into primes or semiprimes.

%Y - A322353 into distinct semiprimes.

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

%Y - A339839 into distinct primes or semiprimes.

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

%Y - A000569 counts graphical partitions (A320922).

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

%Y - A209816 counts multigraphical partitions (A320924).

%Y - A339656 counts loop-graphical partitions (A339658).

%Y -

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

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

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

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

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

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

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

%K nonn

%O 1,6

%A _Gus Wiseman_, Dec 20 2020

%E More terms from _Antti Karttunen_, May 02 2022