|
%I #33 Jan 01 2021 14:23:03
%S 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,
%T 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,
%U 15,2,15,0,8,2,15,0,49,0,2,8,8,2,15,0,32,6,2
%N Numbers of ordered pairs of divisors d < e of n such that gcd(d, e) > 1.
%C Number of elements in the set {(x, y): x|n, y|n, x < y, gcd(x, y) > 1}.
%C Every element of the sequence is repeated indefinitely, for instance:
%C a(n)=0 if n prime;
%C a(n)=1 if n = p^2 for p prime (A001248);
%C a(n)=2 if n is a squarefree semiprime (A006881);
%C a(n)=3 if n = p^3 for p prime (A030078);
%C a(n)=6 if n = p^4 for p prime (A030514);
%C a(n)=8 if n is a number which is the product of a prime and the square of a different prime (A054753);
%C a(n)=10 if n = p^5 for p prime (A050997);
%C a(n)=15 if n is in the set {A007304} union {64} = {30, 42, 64, 66, 70,...} = {Sphenic numbers} union {64};
%C a(n)=18 if n is the product of the cube of a prime (A030078) and a different prime (see A065036);
%C a(n)=21 if n = p^7 for p prime (A092759);
%C a(n)=24 if n is square of a squarefree semiprime (A085986);
%C a(n)=32 if n is the product of the 4th power of a prime (A030514) and a different prime (see A178739);
%C a(n)=36 if n = p^9 for p prime (A179665);
%C a(n)=44 if n is the product of exactly four primes, three of which are distinct (A085987);
%C a(n)=45 if n is a number with 11 divisors (A030629);
%C a(n)=49 if n is of the form p^2*q^3, where p,q are distinct primes (A143610);
%C a(n)=50 if n is the product of the 5th power of a prime (A050997) and a different prime (see A178740);
%C a(n)=55 if n if n = p^11 for p prime(A079395);
%C a(n)=72 if n is a number with 14 divisors (A030632);
%C a(n)=80 if n is the product of four distinct primes (A046386);
%C a(n)=83 if n is a number with 15 divisors (A030633);
%C a(n)=89 if n is a number with prime factorization pqr^3 (A189975);
%C a(n)=96 if n is a number that are the cube of a product of two distinct primes (A162142);
%C a(n)=98 if n is the product of the 7th power of a prime and a distinct prime (p^7*q) (A179664);
%C 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);
%C 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);
%C a(n)=128 if n is the product of the 8th power of a prime and a distinct prime (p^8*q) (A179668);
%C 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);
%C 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).
%C It is possible to continue with a(n) = 162, 178, 209, 224, 227, 238, 239, 260, 289, 309, 320, 333,...
%H Charles R Greathouse IV, <a href="/A275387/b275387.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = A066446(n) - A063647(n).
%F 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
%e 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).
%p with(numtheory):nn:=100:
%p for n from 1 to nn do:
%p x:=divisors(n):n0:=nops(x):it:=0:
%p for i from 1 to n0 do:
%p for j from i+1 to n0 do:
%p if gcd(x[i],x[j])>1
%p then
%p it:=it+1:
%p else
%p fi:
%p od:
%p od:
%p printf(`%d, `,it):
%p od:
%t 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 *)
%o (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
%o (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
%Y 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.
%Y Cf. A333976 (same with d <= e).
%K nonn
%O 1,6
%A _Michel Lagneau_, Aug 03 2016
|
