login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Table of n, a(n) for n=1..37.

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: A106041 A264044 A143855 * A077044 A069038 A213563

Adjacent sequences:  A124159 A124160 A124161 * A124163 A124164 A124165

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Dec 03 2006

EXTENSIONS

More terms from N. J. A. Sloane and several other people, Dec 04 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 13 16:34 EDT 2019. Contains 327966 sequences. (Running on oeis4.)