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,24

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

a(n) = 16 for n = 24, 40, 56, 135, 189, 297, 351, 459, ... (numbers of the form p^3*q, p and q primes with q > p).

a(n) = 17 for n = 54, 88, 104, 136, 152, 184, 232, 248, ... (numbers of the form p^i*q^j, p and q primes and (i, j) = (3, 1) or (1, 3).

a(n) = 30 for n = 36, 225, 441, 1225, 3025, 4225, 5929, ... (numbers of the form p^2*q^2, p and q primes.

It is possible to continue with a(n) = 74, 75, 78, 107, 110, 112, 114, ...

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

Example

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 4 following quadruples of divisors: (2,6,10,30), (3,6,15,30) and (5,10,15,30).

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

Prog

(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

Crossrefs

Cf. A275387, A336530.

Sequence in context: A072838 A023919 A306282 * A169767 A225611 A173293

Adjacent sequences: A336429 A336430 A336431 * A336433 A336434 A336435

Keyword

nonn

Author

Michel Lagneau, Oct 05 2020

Extensions

Terms corrected by David A. Corneth, Oct 31 2020

Status

approved