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

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

Links

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

Formula

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

a(n) = Sum_{d1|n, d2|n, d1<d2} (1-[gcd(d1,d2) = 1]), where [ ] is the Iverson bracket. - Wesley Ivan Hurt, Jan 01 2021

Example

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

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

Prog

(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

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

Sequence in context: A333409 A197117 A343879 * A051709 A318326 A329646

Adjacent sequences: A275384 A275385 A275386 * A275388 A275389 A275390

Keyword

nonn

Author

Michel Lagneau, Aug 03 2016

Status

approved