A395033 - OEIS

%I #15 May 09 2026 18:27:42

%S 0,0,0,0,0,1,0,0,0,1,0,3,0,1,1,0,0,4,0,3,1,1,0,3,0,1,0,3,0,6,0,0,1,1,

%T 1,12,0,1,1,3,0,6,0,3,4,1,0,3,0,6,1,3,0,4,1,3,1,1,0,18,0,1,4,0,1,6,0,

%U 3,1,6,0,12,0,1,6,3,1,6,0,3,0,1,0,18,1,1

%N a(n) is the sum of all pairwise gcds arising from partitions of the multiset of prime factors of n.

%C This sequence is a weighted analog of A001055, summing a gcd-based weight over unordered factorizations obtained from partitions of the multiset of prime factors, where identical primes are treated as indistinguishable. Thus, groupings that differ only by permuting or by splitting equal prime factors into separate blocks are not counted separately.

%C For squarefree n, this coincides with the unordered factorizations counted by A001055.

%H Felix Huber, <a href="/A395033/b395033.txt">Table of n, a(n) for n = 1..10000</a>

%F For squarefree n with k = A001221(n), a(n) = Sum_{i=1..k} S2(k, i)*binomial(i, 2), where S2(k, i) are the Stirling numbers of the second kind (A008277).

%F a(n) = 0 <=> n in A000961.

%F a(n) = 1 <=> n in A006881.

%F For n in A007304, A046386, A046387, A067885 (squarefree n with k = 3, 4, 5, 6 distinct prime factors), a(n) = 6, 31, 160, 856, respectively.

%e For n = 60 the prime factor multiset is [2, 2, 3, 5]. The distinct partitions are grouped by block count.

%e 1 block:

%e   [2, 2, 3, 5].

%e 2 blocks:

%e   [2, 2, 3] | [5] with gcd(12, 5) = 1;

%e   [2, 2, 5] | [3] with gcd(20, 3) = 1;

%e   [2, 3, 5] | [2] with gcd(30, 2) = 2;

%e   [2, 2] | [3, 5] with gcd(4, 15) = 1;

%e   [2, 3] | [2, 5] with gcd(6, 10) = 2.

%e 3 blocks:

%e   [2, 2] | [3] | [5] with gcd(4, 3) = 1, gcd(4, 5) = 1, gcd(3, 5) = 1;

%e   [2, 3] | [2] | [5] with gcd(6, 2) = 2, gcd(6, 5) = 1, gcd(2, 5) = 1;

%e   [2, 5] | [2] | [3] with gcd(10, 2) = 2, gcd(10, 3) = 1, gcd(2, 3) = 1.

%e Summing all pairwise gcd contributions yields a(60) = 18.

%p A395033 := proc(n)

%p     local a, f, i, j, l, p, r, x;

%p     l := ifactors(n)[2];

%p     if nops(l) <= 1 then return 0 end if;

%p     p := [seq(seq(x[1], 1 .. x[2]), x in l)];

%p     a := 0;

%p     for r in combinat:-setpartition(p) do

%p         f := [seq(mul(x, x in r[i]), i = 1 .. nops(r))];

%p         a := a + add(add(gcd(f[i], f[j]), j = i + 1 .. nops(f)), i = 1 .. nops(f) - 1)

%p     end do;

%p     a

%p end proc:

%p seq(A395033(n), n = 1 .. 86);

%Y Cf. A000110, A000961, A001055, A001221, A001222, A005117, A006881, A007304, A008277, A046386, A046387, A050873, A067885.

%K nonn

%O 1,12

%A _Felix Huber_, May 04 2026