|
Search: id:A124162
|
|
|
| A124162 |
|
Number of quadruples [i,j,k,l] with all entries between 1 and n such that gcd(i,j) = gcd(k,l). |
|
+0
1
|
|
| 1, 10, 51, 132, 373, 590, 1287, 1992, 3209, 4402, 7323, 9004, 13949, 17558, 22159, 27696, 38897, 45018, 60931, 70100, 83653, 98142, 126391, 139928, 170489, 195170, 228139, 254428, 311661, 334886, 405087, 451008, 507329, 563530, 635795, 680772, 799861
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Based on a posting from Dan Asimov, Dec 03 2006, challenging people to find the limit a(n)/n^4.
|
|
FORMULA
|
Let c(n) = A018805(n). Then a(n) = Sum_{ 1 <= d <= n} c(floor(n/d))^2.
Comment from Gareth McCaughan, Dec 04 2006: To find a(n)/n^2, note that (1/n^4) # { p,q,r,s in [1,n] : (p,q) = (r,s) }
= (1/n^4) sum over d of # { p,q,r,s in [1,n] : (p,q) = (r,s) = d }
= (1/n^4) sum over d of (# { p,q in [1,n] : (p,q) = d })^2
= (1/n^4) sum over d of (# { p,q in [1,n/d] : (p,q) = 1 })^2
~ (1/n^4) sum over d of (6/pi^2 (n/d)^2)^2
= (36/pi^4) sum over d of 1/d^4 = (36/pi^4) (pi^4/90) = 2/5.
Comment from Eugene Salamin (gene_salamin(AT)yahoo.com), Dec 04 2006: More generally:
(i) The probability that gcd(i[1],...,i[n]) = gcd(j[1],...,j[n]) is zeta(2n)/zeta(n)^2.
(ii) The probability that k r-tuples of random integers all have the same gcd is zeta(kr)/zeta(r)^k.
(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).
|
|
CROSSREFS
|
Sequence in context: A143558 A106041 A143855 this_sequence A077044 A069038 A030183
Adjacent sequences: A124159 A124160 A124161 this_sequence A124163 A124164 A124165
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
njas, Dec 03 2006
|
|
EXTENSIONS
|
More terms from njas and several other people, Dec 04 2006
|
|
|
Search completed in 0.002 seconds
|
