A275387 Numbers of ordered pairs of divisors d < e of n such that gcd(d, e) > 1.

0, 0, 0, 1, 0, 2, 0, 3, 1, 2, 0, 8, 0, 2, 2, 6, 0, 8, 0, 8, 2, 2, 0, 18, 1, 2, 3, 8, 0, 15, 0, 10, 2, 2, 2, 24, 0, 2, 2, 18, 0, 15, 0, 8, 8, 2, 0, 32, 1, 8, 2, 8, 0, 18, 2, 18, 2, 2, 0, 44, 0, 2, 8, 15, 2, 15, 0, 8, 2, 15, 0, 49, 0, 2, 8, 8, 2, 15, 0, 32, 6, 2

Offset: 1

Author

Michel Lagneau, Aug 03 2016

Keywords

• nonn

Comments

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

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

a(n)=0 if n prime;

a(n)=1 if n = p^2 for p prime (A001248);

a(n)=2 if n is a squarefree semiprime (A006881);

a(n)=3 if n = p^3 for p prime (A030078);

a(n)=6 if n = p^4 for p prime (A030514);

a(n)=8 if n is a number which is the product of a prime and the square of a different prime (A054753);

a(n)=10 if n = p^5 for p prime (A050997);

a(n)=15 if n is in the set {A007304} union {64} = {30, 42, 64, 66, 70,...} = {Sphenic numbers} union {64};

a(n)=18 if n is the product of the cube of a prime (A030078) and a different prime (see A065036);

a(n)=21 if n = p^7 for p prime (A092759);

a(n)=24 if n is square of a squarefree semiprime (A085986);

a(n)=32 if n is the product of the 4th power of a prime (A030514) and a different prime (see A178739);

a(n)=36 if n = p^9 for p prime (A179665);

a(n)=44 if n is the product of exactly four primes, three of which are distinct (A085987);

a(n)=45 if n is a number with 11 divisors (A030629);

a(n)=49 if n is of the form p^2*q^3, where p,q are distinct primes (A143610);

a(n)=50 if n is the product of the 5th power of a prime (A050997) and a different prime (see A178740);

a(n)=55 if n if n = p^11 for p prime(A079395);

a(n)=72 if n is a number with 14 divisors (A030632);

a(n)=80 if n is the product of four distinct primes (A046386);

a(n)=83 if n is a number with 15 divisors (A030633);

a(n)=89 if n is a number with prime factorization pqr^3 (A189975);

a(n)=96 if n is a number that are the cube of a product of two distinct primes (A162142);

a(n)=98 if n is the product of the 7th power of a prime and a distinct prime (p^7*q) (A179664);

a(n)=116 if n is the product of exactly 2 distinct squares of primes and a different prime (p^2*q^2*r) (A179643);

a(n)=126 if n is the product of the 5th power of a prime and different distinct prime of the 2nd power (p^5*q^2) (A179646);

a(n)=128 if n is the product of the 8th power of a prime and a distinct prime (p^8*q) (A179668);

a(n)=150 if n is the product of the 4th power of a prime and 2 different distinct primes (p^4*q*r) (A179644);

a(n)=159 if n is the product of the 4th power of a prime and a distinct prime of power 3 (p^4*q^3) (A179666).

It is possible to continue with a(n) = 162, 178, 209, 224, 227, 238, 239, 260, 289, 309, 320, 333,...

Examples

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

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001248, A006881, A007304, A030078, A030514, A030632, A046386, A050997, A054753, A063647, A065036, A066446, A079395, A085986, A085987, A092759, A143610, A162142, A178739, A178740, A179644, A179646, A179664, A189975.

Cf. A333976 (same with d <= e).

Programs

Maple

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

Mathematica

Table[Sum[Sum[(1 - KroneckerDelta[GCD[i, k], 1]) (1 - Ceiling[n/k] + Floor[n/k]) (1 - Ceiling[n/i] + Floor[n/i]), {i, k - 1}], {k, n}], {n, 100}] (* Wesley Ivan Hurt, Jan 01 2021 *)

PARI

a(n)=my(d=divisors(n)); sum(i=2,#d, sum(j=1,i-1, gcd(d[i],d[j])>1)) \\ Charles R Greathouse IV, Aug 03 2016

PARI

a(n)=my(f=factor(n)[,2],t=prod(i=1,#f,f[i]+1)); t*(t-1)/2 - (prod(i=1,#f,2*f[i]+1)+1)/2 \\ Charles R Greathouse IV, Aug 03 2016

Formula

a(n) = A066446(n) - A063647(n).

a(n) = Sum_{d1|n, d2|n, d1Wesley Ivan Hurt, Jan 01 2021