Re: Re: Finding the Number of Pythagorean Triples below a bound
- To: mathgroup at smc.vnet.net
- Subject: [mg68485] Re: [mg68345] Re: Finding the Number of Pythagorean Triples below a bound
- From: Titus Piezas <titus_piezas at yahoo.com>
- Date: Mon, 7 Aug 2006 01:40:59 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Hello Dan and Andrzej,
>I'd say up to 10^6 or maybe 10^7 the way to go is by looking at the
>factorization of c2=c^2+k. This way you only need iterate over c.
Yes, turns out the problem was equivalent to counting the number of representations of N as
a^2+b^2 = N
where 0<a<=b (I should have phrased it that way, but that is the benefit of high-sight) which I assume can be given by the function OrderedSumOfSquaresRepresentations[2,N]? Hence the code you have given me, in essence, is, say for k = 5,
Sum[OrderedSumOfSquaresRepresentations[2,c^2+5],{c,1,10^m-1}]
roughly speaking? (With finer details of removing from consideration those c^2+5 that are of from 4m+3, etc.)
>Here are some timings.
>
>In[54]:=Timing[countTriples[10^4,3]]
>Out[54]={0.591 Second,1154}
>
>In[93]:=Timing[countTriples[10^5,3]]
>Out[93]={8.562 Second,12115}
>
>In[94]:=Timing[countTriples[10^6,3]]
>Out[94]={131.91 Second,121054}
There is something odd with the first value. James' count (up to m=5) vs this gives the sequences,
{1219, 12115}
{1154, 12115, 121054}
Why the disparity? If the ratio S(N)/N would converge, it should start as 0.121... (Note however, that James' table has bound 10^m *not* 10^m-1.}
-Tito