Author |
Topic: Hypothenuse numbers (Read 1426 times) |
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Hypothenuse numbers
« on: Aug 14th, 2005, 9:26am » |
Quote Modify
|
For very large N, determine the likelihood that a randomly selected positive integer not exceeding N is a hypothenuse number*. * a number with a square that is the sum of two nonzero squares
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Hypothenuse numbers
« Reply #1 on: Aug 14th, 2005, 3:33pm » |
Quote Modify
|
If n=2kp1a1...prar q1b1...qsbs, where each pi is 1 mod 4, and each qj is 3 mod 4, then n2 has 4(1+2a1)...(1+2ar) representations as the sum of two squares. Since we always have the 4 trivial representations n2=02+(+/-n)2=(+/-n)2+02, n is an hypotenuse number iff some ai>0. Thus, the complement of the set of hypotenuse numbers are those with no prime factor congruent to 1 mod 4. Let p1,p2,... be an enumeration of these primes. Then the set Sn of numbers with no prime factor in {p1,...pn} has density Dn=(1-1/p1)...(1-1/pn). Since [sum] 1/pi diverges (and [sum] 1/pi2 converges), it follows that Dn goes to 0, and so the intersection of all the Sn has density 0. Thus, as N goes to infinity, the probability that a random n<N is an hypotenuse number goes to 1. It's probably something like 1 - 1/sqrt(log N), but don't quote me on that.
|
|
IP Logged |
|
|
|
|