D. J. Bernstein
More number-theoretic computations


The latest published sortedsums package is sortedsums-0.53.tar.gz.

I have a paper explaining the algorithms used here.

What is it?

sortedsums is a collection of tools for enumerating small solutions to certain types of Diophantine equations. For example, there are 14519 primitive solutions (a,b,c,d) to 5a^3 + 6b^3 = 7c^3 + 8d^3 > 0 with max{|a|,|b|,|c|,|d|} <= 10000; ``cubepqrs 5 6 7 8 10000'' prints all of them in just 69 minutes on a Pentium-100.

Given integers p[0], p[1], ..., p[n-1] and q[0], q[1], ..., q[n-1], sortedpq enumerates pairs (i,j) in increasing order of p[i]+q[j]. It uses extra space for just n integers and 2n indices. sortedpp is a faster version of sortedpq when p = q; it enumerates pairs (i,j) with i >= j, in increasing order of p[i]+p[j].

solvepqrs enumerates (i,j,k,l) such that p[i]+q[j] = r[k]+s[l], in increasing order of p[i]+q[j]. solvepppp, solvepprs, solvepqpq, and solvepprr are faster versions of solvepqrs.

Several sample applications are included in the sortedsums package:

This work was supported by the National Science Foundation under grant DMS-9600083.


I have a table of all 516 primitive solutions to a^4 + b^4 = c^4 + d^4 with 0 < b <= a, 0 < d <= c, and c < a <= 1000000. 218 of the solutions were found previously by Lander, Parkin, Selfridge, and Zajta.

The fourth power of 8707481 is a sum of three positive fourth powers. Same for 12197457, 16003017, and 16430513. Other small known solutions are 422481 (Frye), 2813001 (MacLeod), 20615673 (Elkies), and 638523249 (MacLeod). There are no other primitive solutions below 21000000. This computation used some observations by Morgan Ward.

48988659276962496 (discovered independently by Wilson), 391909274215699968, and 490593422681271000 can be written in 5 ways as the sum of two positive cubes.