D. J. Bernstein

More number-theoretic computations
# sortedsums

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:

- cubepqrs enumerates solutions to pa^3 + qb^3 = rc^3 + sd^3, given
(p,q,r,s). cubepppp, cubepprs, and cubepqpq are faster versions of
cubepqrs.
- two3 enumerates positive integers that can be written in many ways
as sums of two cubes. two3p enumerates integers that can be written
in many ways as sums of two positive cubes.
- two4 enumerates integers that can be written in two ways as sums of
two positive fourth powers. euler4 enumerates fourth powers that
can be written as sums of three positive fourth powers.

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

## Results

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.