A336432 Number of ordered quadruples of divisors (d_i, d_j, d_k, d_m) of n such that GCD(d_i, d_j, d_k, d_m) > 1.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 16, 0, 0, 0, 1, 0, 3, 0, 5, 0, 0, 0, 29, 0, 0, 0, 16, 0, 3, 0, 1, 1, 0, 0, 74, 0, 1, 0, 1, 0, 16, 0, 16, 0, 0, 0, 98, 0, 0, 1, 15, 0, 3, 0, 1, 0, 3, 0, 181, 0, 0, 1, 1, 0, 3, 0, 74, 1, 0, 0, 98, 0, 0, 0, 16, 0, 98, 0, 1, 0, 0, 0, 220, 0, 1, 1, 29, 0, 3, 0

Offset: 1

Author

Michel Lagneau, Oct 05 2020

Keywords

• nonn

Comments

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

Every term of the sequence is repeated indefinitely; for instance:

a(n) = 0 for n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, ... (numbers k such that product of proper divisors of k is <= k; i.e., product of divisors of k is <= k^2; see A007964).

a(n) = 1 for n = 12, 16, 18, 20, 28, 44, 45, 50, 52, 63, 68, 75, 76, 81, 92, 98, 99, ... (either 4th power of a prime, or product of a prime and the square of a different prime; see A080258).

a(n) = 5 for n = 32, 243, 3125, 16807, ... (fifth powers of primes; see A050997).

a(n) = 15 for n = 64, 729, 15625, 117649, ... (numbers with 7 divisors: 6th powers of primes; see A030516).

Examples

			a(30) = 3 because the divisors of 30 are {1, 2, 3, 5, 6, 10, 15, 30} and GCD(d_i, d_j, d_k, d_m) > 1 for the following 3 quadruples of divisors: (2,6,10,30), (3,6,15,30) and (5,10,15,30).
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A275387, A336530.

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-3 do:
   for j from i+1 to n0-2 do:
     for k from j+1 to n0-1 do:
       for l from k+1 to n0 do:
    if igcd(d[i],d[j],d[k],d[l])> 1
       then
       it:=it+1:
       else
      fi:
     od:
    od:
   od:
  od:
    printf(`%d, `,it):
od:

Mathematica

Array[Count[GCD @@ # & /@ Subsets[Divisors[#], {4}], ?(# > 1 &)] &, 100] (* _Amiram Eldar, Oct 31 2020 after Michael De Vlieger at A336530 *)

PARI

a(n) = my(d=divisors(n)); sum(i=1, #d-3, sum (j=i+1, #d-2, sum (k=j+1, #d-1, sum (m=k+1, #d, gcd([d[i], d[j], d[k], d[m]]) > 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]), 4)*(-1)^omega(d[i])); res} \\ David A. Corneth, Oct 31 2020

Extensions

Terms corrected by David A. Corneth, Oct 31 2020