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

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, 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, 3, 1, 6, 0, 12, 0, 1, 6, 3, 1, 6, 0, 3, 0, 1, 0, 18, 1, 1

Offset

1,12

Comments

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.

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

Links

Felix Huber, Table of n, a(n) for n = 1..10000

Formula

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).

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

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

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.

Example

For n = 60 the prime factor multiset is [2, 2, 3, 5]. The distinct partitions are grouped by block count.
1 block:
  [2, 2, 3, 5].
2 blocks:
  [2, 2, 3] | [5] with gcd(12, 5) = 1;
  [2, 2, 5] | [3] with gcd(20, 3) = 1;
  [2, 3, 5] | [2] with gcd(30, 2) = 2;
  [2, 2] | [3, 5] with gcd(4, 15) = 1;
  [2, 3] | [2, 5] with gcd(6, 10) = 2.
3 blocks:
  [2, 2] | [3] | [5] with gcd(4, 3) = 1, gcd(4, 5) = 1, gcd(3, 5) = 1;
  [2, 3] | [2] | [5] with gcd(6, 2) = 2, gcd(6, 5) = 1, gcd(2, 5) = 1;
  [2, 5] | [2] | [3] with gcd(10, 2) = 2, gcd(10, 3) = 1, gcd(2, 3) = 1.
Summing all pairwise gcd contributions yields a(60) = 18.

Maple

A395033 := proc(n)
    local a, f, i, j, l, p, r, x;
    l := ifactors(n)[2];
    if nops(l) <= 1 then return 0 end if;
    p := [seq(seq(x[1], 1 .. x[2]), x in l)];
    a := 0;
    for r in combinat:-setpartition(p) do
        f := [seq(mul(x, x in r[i]), i = 1 .. nops(r))];
        a := a + add(add(gcd(f[i], f[j]), j = i + 1 .. nops(f)), i = 1 .. nops(f) - 1)
    end do;
    a
end proc:
seq(A395033(n), n = 1 .. 86);

Crossrefs

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

Sequence in context: A397133 A391073 A309887 * A317595 A385860 A263753

Adjacent sequences: A395030 A395031 A395032 * A395034 A395035 A395036

Keyword

nonn

Author

Felix Huber, May 04 2026

Status

approved