Re: Re: Finding the Number of Pythagorean Triples below a bound
- To: mathgroup at smc.vnet.net
- Subject: [mg68478] 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:35 -0400 (EDT)
- References: <20060806080123.15221.qmail@web50704.mail.yahoo.com>
- 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.
>
> >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