Bill Allombert on Sat, 18 Nov 2023 09:49:33 +0100


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

Re: question on finding exhaustive search algorithm for a^2+b^2 = N 

On Fri, Nov 17, 2023 at 05:11:55PM -0800, American Citizen wrote:
> Thank you all for being patient with me.
> 
> I wrote an algorithm to find two squares summing to N
> 
> sol2(N) = Set(abs(vecsort(qfbsolve(Qfb(1,0,1),N,3),,4)))

This is not quite right. For each solution [a,b], qfbsolve returns one
of [a,b], [-b,a], [-a,-b], [b,-a] and also one of
   [b,a], [-a,b], [-b,-a], [a,-b]
so taking the absolute value you get one of
[a,b], [b,a] and one of [b,a], [a,b] 
so you will get twice the same solution half of the time.

> Carefully writing a program which exhaustively searches comes up with the
> following 32 solutions:
> 
> [[64, 1087], [103, 1084], [167, 1076], [191, 1072], [236, 1063], [281,
> 1052], [292, 1049], [359, 1028], [449, 992], [512, 961], [568, 929], [601,
> 908], [607, 904], [664, 863], [673, 856], [743, 796], [796, 743], [856,
> 673], [863, 664], [904, 607], [908, 601], [929, 568], [961, 512], [992,
> 449], [1028, 359], [1049, 292], [1052, 281], [1063, 236], [1072, 191],
> [1076, 167], [1084, 103], [1087, 64]]

Your list includes both [64, 1087] and [1087, 64].

If you want both [a,b] and [b,a] do that

sol2(N) = Set(concat([[x,Vecrev(x)]| x <- abs(qfbsolve(Qfb(1,0,1),N,3))]))

if you want only [a,b] with a<=b, do

sol2(N) = Set([vecsort(x)| x <- abs(qfbsolve(Qfb(1,0,1),N,3))])

? sol2(5*13*17*29*37)
%56 = [[64,1087],[103,1084],[167,1076],[191,1072],[236,1063],[281,1052],[292,1049],[359,1028],[449,992],[512,961],[568,929],[601,908],[607,904],[664,863],[673,856],[743,796]]
? #%
%57 = 16

Cheers,
Bill