Re: Re: Finding the Number of Pythagorean Triples below a bound
- To: mathgroup at smc.vnet.net
- Subject: [mg68480] Re: [mg68345] Re: Finding the Number of Pythagorean Triples below a bound
- From: danl at wolfram.com
- Date: Mon, 7 Aug 2006 01:40:41 -0400 (EDT)
- References: <20060806080123.15221.qmail@web50704.mail.yahoo.com> <18D1E833-7EBC-45EC-83A3-949C201D34EE@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
>
> On 6 Aug 2006, at 10:01, Titus Piezas wrote:
>
>> 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.)
>
> Well, no, it is rather:
>
> Sum[Length[OrderedSumOfSquaresRepresentations[2,c^2+5]],{c,1,10^m-1}]
>
> In fact I forgot that there was OrderedSumOfSquaresRepresentations as
> well as SumOfSquaresRepresentations, which is the main reason why I
> did not think it would be very useful. Another reason is that, I
> expected, computing Length of many lists and then adding these
> Lengths up should be slower than just counting the total number of
> elements.
Length[] is quite fast (constant time) to compute, so that aspect at least
should not be an issue.
>> >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.}
>
> My code also gives:
>
>
> countTriplesP[4,3]
>
> 1219
>
> Changing 10^m-1 to 10^m should give a value at least as large, and in
> fact gives the same answer.
>
>
> which suggests that something still needs to be looked carefully at
> in Daniel's code. I can't do it now but will think about it when I can.
>
> Andrzej
>
I think I see the problem. Looking at the In/Out numbers I notice the 10^4
case was run much earlier than the others. I am guessing it was run when I
had not fully debugged the code and was getting results that were too
small (pecifically, I was missing the cases with factors of form 4*k+3
that appear to even powers). I may simply have failed to rerun that one
before cutting-and-pasting into my note.
If you run the code I sent and get the correct result that will confirm
the matter. I'll try it later as right now I am not on a machine with a
reliable Mathematica installation.
Daniel