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

KEYWORD

nonn

AUTHOR

Michel Lagneau, Aug 03 2016

STATUS

approved