login
Number of quadruples [i,j,k,l] with all entries between 1 and n such that gcd(i,j) = gcd(k,l).
1

%I #22 Mar 30 2021 19:43:06

%S 1,10,51,132,373,590,1287,1992,3209,4402,7323,9004,13949,17558,22159,

%T 27696,38897,45018,60931,70100,83653,98142,126391,139928,170489,

%U 195170,228139,254428,311661,334886,405087,451008,507329,563530,635795,680772,799861

%N Number of quadruples [i,j,k,l] with all entries between 1 and n such that gcd(i,j) = gcd(k,l).

%C Based on a posting from Dan Asimov, Dec 03 2006, challenging people to find the limit a(n)/n^4.

%H Chai Wah Wu, <a href="/A124162/b124162.txt">Table of n, a(n) for n = 1..10000</a>

%F Let c(n) = A018805(n). Then a(n) = Sum_{d=1..n} c(floor(n/d))^2.

%F Comment from Gareth McCaughan, Dec 04 2006: (Start)

%F To find a(n)/n^2, note that (1/n^4) # { p,q,r,s in [1,n] : (p,q) = (r,s) }

%F = (1/n^4) Sum_{d} # { p,q,r,s in [1,n] : (p,q) = (r,s) = d }

%F = (1/n^4) Sum_{d} (# { p,q in [1,n] : (p,q) = d })^2

%F = (1/n^4) Sum_{d} (# { p,q in [1,n/d] : (p,q) = 1 })^2

%F ~ (1/n^4) Sum_{d} ((6/Pi^2)*(n/d)^2)^2

%F = (36/Pi^4) Sum_{d} 1/d^4 = (36/Pi^4)*(Pi^4/90) = 2/5. (End)

%F Comment from Eugene Salamin (gene_salamin(AT)yahoo.com), Dec 04 2006: (Start)

%F More generally:

%F (i) The probability that gcd(i[1],...,i[n]) = gcd(j[1],...,j[n]) is zeta(2n)/zeta(n)^2.

%F (ii) The probability that k r-tuples of random integers all have the same gcd is zeta(kr)/zeta(r)^k.

%F (iii) The probability that the gcd of an r-tuple of random integers divides the gcd of an n-tuple of random integers is zeta(n+r)/zeta(n). (End)

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Dec 03 2006

%E More terms from _N. J. A. Sloane_ and several other people, Dec 04 2006