American Citizen on Tue, 25 Mar 2025 00:58:03 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: question on trying to use quadratic residues to eliminate needless checks

Denis:

My apologies for not stating my question more clearly.

Let's look at n=44.

Using the divisors d[i] of 44^2 --> d = [1, 2, 4, 8, 11, 16, 22, 44, 88, 121, 176, 242, 484, 968, 1936] and the relationship of

(1)   m[i] = (n^2 - d[i]^2) / (2*d[i])

We find that the following seven (7) non-zero positive rational values are obtained:

(2) m[i] = [33, 105/2, 165/2, 117, 240, 483, 1935/2]

We now check to see if m[i]^2 + m[j]^2 = s^2 for i<>j.

This requires the squares sums check for a perfect square (21 in all) of

33 checked against 105/2, 165/2 117, 240, 483, 1935/2

105/2 checked against 165/2, 117, 240, 483, 1935/2

165/2 checked against 117, 240, 483, 1935/2

117 checked against 240, 483, 1935/2

240 checked against 483, 1935/2

483 checked against 1935/2

For n values, this is n(n-1)/2 checks, clearly inefficient, if using a full digit sum and then square root for multiple precision integers (or rationals)

In this case for 44, there are 21 checks to be made

Only 1 pair satisfies the criteria, it is 117^2 + 240^2 = 267^2 which results in the body cuboid 44 117 240 (body diagonal = sqrt(73225))

I am trying to shorten down the n(n-1)/2 checks using quadratic residues.

Can using quadratic residues help me avoid the computer time costly error of squaring large digit numbers and then finding the square root of their pair sum?

I hope I have explained this more clearly.

Randall


On 3/24/25 07:02, Denis Simon wrote:
Dear Randall,

I am not sure I understand your question.
You want to solve a^2+b^2=s^2, where a is given, and b,s are integers or half integers ?

In this case, you write your equation as
b^2 = s^2-a^2 = (s-a)(s+a)
and you loop over the divisors of b^2, say b^2 = p*q
then s = (p+q)/2 and a = (p-q)/2

Denis.