|
Kurt Foster on Sat, 18 Nov 2023 04:19:30 +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
|
- To: Pari Users <pari-users@pari.math.u-bordeaux.fr>
- Subject: Re: question on finding exhaustive search algorithm for a^2+b^2 = N
- From: Kurt Foster <drsardonicus@earthlink.net>
- Date: Fri, 17 Nov 2023 21:19:22 -0600
- Authentication-results: earthlink-vadesecure.net; auth=pass smtp.auth=drsardonicus@earthlink.net smtp.mailfrom=drsardonicus@earthlink.net;
- Delivery-date: Sat, 18 Nov 2023 04:19:30 +0100
- Dkim-signature: v=1; a=rsa-sha256; bh=mvjTnhM0X/xI6JxoAKnUvkhGcVEPfqkA/rYbyS lXmo0=; c=relaxed/relaxed; d=earthlink.net; h=from:reply-to:subject: date:to:cc:resent-date:resent-from:resent-to:resent-cc:in-reply-to: references:list-id:list-help:list-unsubscribe:list-subscribe:list-post: list-owner:list-archive; q=dns/txt; s=dk12062016; t=1700277566; x=1700882366; b=g002cdsaOVG9vx8HtzwDmQ0IStEhKnFZBDPsl6BqGCfyBiCsYoDN4tz RFzKKK+Cv8QuE0VsKgYKAn/JObvMhfSwRmCMzn3zsUrNZS06KPCh26iRt/9h/xqkvFzCAKT FQZIX9rk5JRXGi60R6Ta6W6glXF5nkEBjfJEC2xkAQAD38AwGkgfiFvwAAGJ2E0O+mFub+N 90jAf3VxPlxYeCQBWOQh5TxGyHYv/L6eQh7D0Xl92PPsP3TjVzEU0y9jfajh4bop9ijoRcF 7+oXDYGOT6xwD1eb3gEM4yVKSA7+2N2y1xSh825HG1Qyjlqbma+wu4LYt1OSAhAMct+DdKO csA==
- In-reply-to: <c7cf4c64-6785-4a19-82f3-cd68c0ee4d52@gmail.com>
- References: <c7cf4c64-6785-4a19-82f3-cd68c0ee4d52@gmail.com>
On Nov 17, 2023, at 7:11 PM, American Citizen wrote:
My goal is an exhaustive search of 2 squares = N algorithm
I dashed off some code which may be overkill (it absolutely clobbers
the problem) but seems to get the job done. I used your example as a
test.
? K=bnfinit(x^2+1);
? N=5*13*17*29*37;
? v=bnfisintnorm(K,N);
? w=vecsort(vector(#v,i,abs([polcoeff(v[i],0),polcoeff(v[i],1)])),1)
%4 = [[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]]
?
I note that if N = a^2 + b^2 with a < b, both [a, b] and [b, a] appear
on the list.