Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Re: Finding the Number of Pythagorean Triples below a bound

• To: mathgroup at smc.vnet.net
• Subject: [mg68382] Re: [mg68345] Re: Finding the Number of Pythagorean Triples below a bound
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Thu, 3 Aug 2006 06:07:05 -0400 (EDT)
• References: <eaeqa3$53v$1@smc.vnet.net><200607300848.EAA25171@smc.vnet.net> <eakfgm$rl6$1@smc.vnet.net> <200608020923.FAA28520@smc.vnet.net> <79C36C70-E091-4A82-8EC5-0EDC743D081D@mimuw.edu.pl>
• Sender: owner-wri-mathgroup at wolfram.com

On 2 Aug 2006, at 20:01, Andrzej Kozlowski wrote:

>
> On 2 Aug 2006, at 11:23, titus_piezas at yahoo.com wrote:
>
>> Hello all,
>>
>> My thanks to Peter and Andrzej, as well as those who privately  
>> emailed
>> me.
>>
>> To recall, the problem was counting the number of solutions to a
>> bivariate polynomial equal to a square,
>>
>> Poly(a,b) = c^2
>>
>> One form that interested me was the Pythagorean-like equation:
>>
>> a^2 + b^2 = c^2 + k
>>
>> for {a,b} a positive integer, 0<a<=b, and k any small integer. I was
>> wondering about the density of solutions to this since I knew in the
>> special case of k=0, let S(N) be the number of primitive solutions  
>> with
>> c < N, then S(N)/N = 1/(2pi) as N -> inf.
>>
>> For k a squarefree integer, it is convenient that any solution is  
>> also
>> primitive. I used a simple code that allowed me to find S(10^m) with
>> m=1,2,3 for small values of k (for m=4 took my code more than 30 mins
>> so I aborted it). The data is given below:
>>
>> Note: Values are total S(N) for *both* k & -k:
>>
>> k = 2
>> S(N) = 4, 30, 283
>>
>> k = 3
>> S(N) = 3, 41, 410
>>
>> k = 5
>> S(N) = 3, 43, 426
>>
>> k = 6
>> S(N) = 3, 36, 351
>>
>> Question: Does S(N)/N for these also converge? For example, for the
>> particular case of k = -6, we have
>>
>> S(N) = 2, 20, 202
>>
>> which looks suspiciously like the ratio might be converging.
>>
>> Anybody know of a code for this that can find m=4,5,6 in a reasonable
>> amount of time?
>>
>>
>> Yours,
>>
>> Titus
>>
>
>
> Here is a piece code which utilises the ideas I have described in  
> my previous posts:
>
> ls = Prime /@ Range[3, 10];
>
> test[n_] :=
>       Not[MemberQ[JacobiSymbol[n, ls], -1]] && Element[Sqrt[n],
> Integers]
>
> f[P_, k_] := Sum[If[(w =
>    a^2 + b^2 - k) < P^2 && test[w], 1, 0], {a, 1, P}, {b, a,
>           Floor[Sqrt[P^2 - a^2]]}]
>
> g[m_, k_] := f[10^m, k] + f[10^m, -k]
>
> We can easily confirm the results of your computations,.e.g. for k=2.
>
>
> Table[g[i,2],{i,3}]
>
>
> {4,30,283}
>
>
> Since you have not revealed the "simple code" you have used it is  
> hard to tell if the above one is any better. It is however,  
> certainly capable of solving the problem for m=4:
>
>
> g[4,2]//Timing
>
>
> {4779.39 Second,2763}
>
> The time it took on my 1 Gigahertz PowerBook was over 70 minutes,  
> which is longer than you thought "reasonable", so I am still not  
> sure if this is any improvement on what you already have. The time  
> complexity of this algorithm seems somewhat larger than exponential  
> so I would expect that it will take about 6 hours to deal with n=5  
> on my computer, and perhaps 2 weeks to deal with n=6.
>
> Andrzej Kozlowski
>
>
>


I mistakenly copied and pasted a wrong (earlier) definition of f.  
Here is the correct one:

f[P_, k_] := Block[{w}, Sum[If[GCD[a, b, k] ==
     1 && (w = a^2 +
          b^2 - k) < P^2 && test[w], 1, 0], {a, 1,
           P}, {b, a, Floor[Sqrt[P^2 - a^2]]}]]

The definition of g is as before:

g[m_, k_] := f[10^m, k] + f[10^m, -k]

Andrzej Kozlowski

• Follow-Ups:
  • Re: Re: Re: Finding the Number of Pythagorean Triples below a bound
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>

• References:
  • Re: Finding the Number of Pythagorean Triples below a bound
    • From: titus_piezas@yahoo.com