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