wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Hypothenuse numbers
        
(Message started by: JocK on Aug 14^th, 2005, 9:26am)

Title: Hypothenuse numbers
Post by JocK on Aug 14^th, 2005, 9:26am

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

Title: Re: Hypothenuse numbers
Post by Eigenray on Aug 14^th, 2005, 3:33pm

If n=2^kp₁^a1...p_r^ar q₁^b1...q_s^bs, where each p_i is 1 mod 4, and each q_j is 3 mod 4, then n² has 4(1+2a₁)...(1+2a_r) representations as the sum of two squares. Since we always have the 4 trivial representations n²=0²+(+/-n)²=(+/-n)²+0², n is an hypotenuse number iff some a_i>0.

Thus, the complement of the set of hypotenuse numbers are those with no prime factor congruent to 1 mod 4. Let p₁,p₂,... be an enumeration of these primes. Then the set S_n of numbers with no prime factor in {p₁,...p_n} has density D_n=(1-1/p₁)...(1-1/p_n).
Since [sum] 1/p_i diverges (and [sum] 1/p_i² converges), it follows that D_n goes to 0, and so the intersection of all the S_n 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.