A336530 Number of triples of divisors d_i < d_j < d_k of n such that gcd(d_i, d_j, d_k) > 1.

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 0, 0, 0, 4, 0, 5, 0, 5, 0, 0, 0, 23, 0, 0, 1, 5, 0, 12, 0, 10, 0, 0, 0, 36, 0, 0, 0, 23, 0, 12, 0, 5, 5, 0, 0, 62, 0, 5, 0, 5, 0, 23, 0, 23, 0, 0, 0, 87, 0, 0, 5, 20, 0, 12, 0, 5, 0, 12, 0, 120, 0, 0, 5, 5, 0, 12, 0, 62, 4

Offset: 1

Author

Michel Lagneau, Oct 04 2020

Keywords

• nonn

Comments

Number of elements in the set {(x, y, z): x|n, y|n, z|n, x < y < z, GCD(x, y, z) > 1}.

Every element of the sequence is repeated indefinitely, for instance:

a(n) = 0 for n = 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, ... (Numbers with at most 2 prime factors (counted with multiplicity). See A037143);

a(n) = 1 for n = 8, 27, 125, 343, 1331, 2197, 4913,... (cubes of primes. See A030078);

a(n) = 4 for n = 16, 81, 625, 2401, 14641, 28561, ... (prime(n)^4. See A030514);

a(n) = 5 for n = 12, 18, 20, 28, 44, 45, ... (Numbers which are the product of a prime and the square of a different prime (p^2 * q). See A054753);

a(n) = 12 for n = 30, 42, 66, 70, 78, 102, 105, 110,... (Sphenic numbers: products of 3 distinct primes. See A007304);

a(n) = 20 for n = 64, 729, 15625, 117649, ... (Numbers with 7 divisors. 6th powers of primes. See A030516);

a(n) = 23 for n = 24, 40, 54, 56, 88, 104, 135, 136, ... (Product of the cube of a prime (A030078) and a different prime. See A065036);

a(n) = 36 for n = 36, 100, 196, 225, 441, 484, 676,... (Squares of the squarefree semiprimes (p^2*q^2). See A085986);

a(n) = 62 for n = 48, 80, 112, 162, 176, 208, 272, ... (Product of the 4th power of a prime (A030514) and a different prime (p^4*q). See A178739);

a(n) = 87 for n = 60, 84, 90, 126, 132, 140, 150, 156, ... (Product of exactly four primes, three of which are distinct (p^2*q*r). See A085987);

a(n) = 120 for n = 72, 108, 200, 392, 500, 675, 968, ... (Numbers of the form p^2*q^3, where p,q are distinct primes. See A143610);

It is possible to continue with a(n) = 130, 235, 284, 289, 356, ...

Examples

			a(12) = 5 because the divisors of 12 are {1, 2, 3, 4, 6, 12} and GCD(d_i, d_j, d_k) > 1 for the 5 following triples of divisors: (2,4,6), (2,4,12), (2,6,12), (3,6,12) and (4,6,12).
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A275387.

Programs

Maple

with(numtheory):nn:=100:
for n from 1 to nn do:
it:=0:d:=divisors(n):n0:=nops(d):
  for i from 1 to n0-2 do:
   for j from i+1 to n0-1 do:
     for k from j+1 to n0 do:
    if igcd(d[i],d[j],d[k])> 1
       then
       it:=it+1:
       else
      fi:
     od:
     od:
     od:
    printf(`%d, `,it):
   od:

Mathematica

Array[Count[GCD @@ # & /@ Subsets[Divisors[#], {3}], ?(# > 1 &)] &, 81] (* _Michael De Vlieger, Oct 05 2020 *)

PARI

a(n) = my(d=divisors(n)); sum(i=1, #d-2, sum (j=i+1, #d-1, sum (k=j+1, #d, gcd([d[i], d[j], d[k]]) > 1))); \\ Michel Marcus, Oct 31 2020

PARI

a(n) = {my(f = factor(n), vp = vecprod(f[,1]), d = divisors(vp), res = 0);
for(i = 2, #d, res-=binomial(numdiv(n/d[i]), 3)*(-1)^omega(d[i])); res} \\ David A. Corneth, Nov 01 2020

Extensions

Name clarified by editors, Oct 31 2020