Re: Re: Finding the Number of Pythagorean Triples below a bound
- To: mathgroup at smc.vnet.net
- Subject: [mg68479] Re: [mg68345] Re: Finding the Number of Pythagorean Triples below a bound
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Mon, 7 Aug 2006 01:40:38 -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 13:33, Andrzej Kozlowski wrote:
>
> 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.
>
>>
>> >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 have looked carefully at Daniel's code and I found I needn't have
bothered ;-
On my PowerBook Daniel's code gives:
countTriples[10^4,3]//Timing
{0.94218 Second,1219}
which shows that my computer is about half the speed of his but also
that somehow he probably pasted the wrong output into his posting?
Everything about the code seems perfect.
In fact, I am sure we could probably make it even faster if we looked
inside the code for OrderedSumOfSquaresRepresentations and changed
it so that it would count the number of representations rather than
make a list of them. But I am not sure that the extra speed we would
gain would be worth the extra effort.
Andrzej Kozlowski
- Follow-Ups:
- Re: Re: Re: Finding the Number of Pythagorean Triples below a bound
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Re: Re: Re: Finding the Number of Pythagorean Triples below a bound