The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).


Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Enumerating solutions to $p(a)+q(b)=r(c)+s(d)$

Author: Daniel J. Bernstein
Journal: Math. Comp. 70 (2001), 389-394
MSC (2000): Primary 11Y50; Secondary 11D25, 11D41, 11P05, 11Y16
Published electronically: June 12, 2000
MathSciNet review: 1709145
Full-text PDF

Abstract | References | Similar Articles | Additional Information


Let $p,q,r,s$ be polynomials with integer coefficients. This paper presents a fast method, using very little temporary storage, to find all small integers $(a,b,c,d)$ satisfying $p(a)+q(b)=r(c)+s(d)$. Numerical results include all small solutions to $a^4+b^4+c^4=d^4$; all small solutions to $a^4+b^4=c^4+d^4$; and the smallest positive integer that can be written in $5$ ways as a sum of two coprime cubes.

References [Enhancements On Off] (What's this?)

  • 1. Svante Carlsson, Average-case results on heapsort, BIT 27 (1987), 2-17. MR 88b:68017
  • 2. Randy L. Ekl, Equal sums of four seventh powers, Mathematics of Computation 65 (1996), 1755-1756. MR 97a:11050
  • 3. Randy L. Ekl, New results in equal sums of like powers, Mathematics of Computation 67 (1998), 1309-1315. MR 98m:11023
  • 4. Noam D. Elkies, On $A^4+B^4+C^4=D^4$, Mathematics of Computation 51 (1988), 825-835. MR 89h:11012
  • 5. Robert W. Floyd, Algorithm 245: Treesort3, Communications of the ACM 7 (1964), 701.
  • 6. Roger E. Frye, Finding $95800^4+217519^4+414560^4=422481^4$ on the Connection Machine, in [15], 106-116.
  • 7. Richard K. Guy, Unsolved problems in number theory, second edition, Springer-Verlag, New York, 1994. MR 96e:11002
  • 8. D. R. Heath-Brown, The density of zeros of forms for which weak approximation fails, Mathematics of Computation 59 (1992), 613-623. MR 93a:11055
  • 9. Donald E. Knuth, The art of computer programming, volume 3: sorting and searching, Addison-Wesley, Reading, Massachusetts, 1973. MR 56:4281
  • 10. Donald E. Knuth, The art of computer programming, volume 3: sorting and searching, second edition, Addison-Wesley, Reading, Massachusetts, 1998.
  • 11. Leon J. Lander, Thomas R. Parkin, Equal sums of biquadrates, Mathematics of Computation 20 (1966), 450-451.
  • 12. Leon J. Lander, Thomas R. Parkin, A counterexample to Euler's sum of powers conjecture, Mathematics of Computation 21 (1967), 101-103. MR 36:3721
  • 13. Leon J. Lander, Thomas R. Parkin, John L. Selfridge, A survey of equal sums of like powers, Mathematics of Computation 21 (1967), 446-459. MR 36:5060
  • 14. John Leech, Some solutions of Diophantine equations, Proceedings of the Cambridge Philosophical Society 53 (1957), 778-780. MR 19:837f
  • 15. Joanne L. Martin, Stephen F. Lundstrom, Supercomputing '88: proceedings, volume 2, IEEE Computer Society Press, Silver Spring, Maryland, 1988.
  • 16. Emmanuel Peyre, Yuri Tschinkel, Tamagawa numbers of diagonal cubic surfaces, numerical evidence, this journal, previous article.
  • 17. E. Rosenstiel, J. A. Dardis, C. R. Rosenstiel, The four least solutions in distinct positive integers of the Diophantine equation $s=x^3+y^3=z^3+w^3=u^3+v^3=m^3+n^3$, Bulletin of the Institute for Mathematics and its Applications 27 (1991), 155-157. MR 92i:11134
  • 18. Joseph H. Silverman, Integer points and the rank of Thue elliptic curves, Inventiones Mathematicae 66 (1982), 395-404. MR 83h:10036
  • 19. Joseph H. Silverman, Integer points on curves of genus $1$, Journal of the London Mathematical Society 28 (1983), 1-7. MR 84g:10033
  • 20. Morgan Ward, Euler's problem on sums of three fourth powers, Duke Mathematical Journal 15 (1948), 827-837. MR 10:283f
  • 21. Ingo Wegener, Bottom-up-heapsort, a new variant of heapsort, beating, on average, quicksort (if $n$ is not very small), Theoretical Computer Science 118 (1993), 81-98. MR 94c:68007
  • 22. John W. J. Williams, Algorithm 232: Heapsort, Communications of the ACM 7 (1964), 347-348.
  • 23. Aurel J. Zajta, Solutions of the diophantine equation $A^4+B^4=C^4+D^4$, Mathematics of Computation 41 (1983), 635-659. MR 85d:11025

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y50, 11D25, 11D41, 11P05, 11Y16

Retrieve articles in all journals with MSC (2000): 11Y50, 11D25, 11D41, 11P05, 11Y16

Additional Information

Daniel J. Bernstein
Affiliation: Department of Mathematics, Statistics, and Computer Science (M/C 249) The University of Illinois at Chicago, Chicago, IL 60607–7045

Received by editor(s): July 10, 1998
Received by editor(s) in revised form: January 4, 1999
Published electronically: June 12, 2000
Additional Notes: The author was supported by the National Science Foundation under grant DMS–9600083.
Article copyright: © Copyright 2000 D. J. Bernstein

American Mathematical Society