cp's OEIS Frontend

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that are not relatively prime. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Feb 17 2024

Equivalently, a(n) is the number of ways to express the cyclic group Z_n as a direct sum of its Hall subgroups. A Hall subgroup of a finite group G is a subgroup whose order is coprime to its index.

a(n) is the number of ways to partition the set of distinct prime factors of n.

Also the number of singleton or pairwise coprime factorizations of n. - Gus Wiseman, Sep 24 2019

Positions of nonzero terms in A322437 or A322438.

Mats Granvik has conjectured that these are all the positive integers k such that sigma_0(k) - 2 > (bigomega(k) - 1) * omega(k), where sigma_0 = A000005, omega = A001221, and bigomega = A001222. - Gus Wiseman, Nov 12 2019

Numbers with more semiprime divisors than prime divisors. - Wesley Ivan Hurt, Jun 10 2021

First differs from A305193 at a(36) = 4, A305193(36) = 5.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Nov 07 2018

First differs from A322438 at a(144) = 3, A322438(144) = 4.

From Antti Karttunen, Dec 11 2020: (Start)

Zeros occur on numbers that are either of the form p^k, or q * p^k, or p*q*r, for some primes p, q, r, and exponent k >= 0. [Note also that in all these cases, when x > 1, A307408(x) = 2+A307409(x) = 2 + (A001222(x) - 1)*A001221(x) = A000005(x)].

Proof:

It is easy to see that for such numbers it is not possible to obtain two such distinct factorizations, that no factor of the other would not divide some factor of the other.

Conversely, the complement set of above is formed of such composites n that have at least one unitary divisor that is either of the form

(1) p^x * q^y, with x, y >= 2,

or

(2) p^x * q^y * r^z, with x >= 2, and y, z >= 1,

or

(3) p^x * q^y * r^z * s^w, with x, y, z, w >= 1,

where p, q, r, s are distinct primes. Let's indicate with C the remaining portion of k coprime to p, q, r and s (which could be also 1). Then in case (1) we can construct two factorizations, the first having factors (p*q*C) and (p^(x-1) * q^(y-1)), and the second having factors (p^x * C) and (q^y) that are guaranteed to satisfy the condition that no factor in the other factorization divides any of the factors of the other factorization. For case (2) pairs like {(p * q^y * C), (p^(x-1) * r^z)} and {(p^x * C), (q^y * r^z)}, and for case (3) pairs like {(p^x * q^y * C), (r^z * s^w)} and {(p^x * r^z * C), (q^y * s^w)} offer similar examples, therefore a(n) > 0 for all such cases.

(End)

First differs from A322437 at a(144) = 4, A322437(144) = 3.

First differs from A379958 at a(120) = 2, A379958(120) = 1.

Given a finite multiset S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. This sequence counts factorizations S whose distinct factors are pairwise indivisible and such that G(S) is a connected graph.

This multiset (row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.