Bimonotone enumeration

Author:
Michael Eisermann

Journal:
Math. Comp. **78** (2009), 591-613

MSC (2000):
Primary 68P10; Secondary 11Y50, 68W10, 11Y16, 11D45

Published electronically:
June 16, 2008

MathSciNet review:
2448723

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Solutions of a diophantine equation , with in some finite range, can be efficiently enumerated by sorting the values of and in ascending order and searching for collisions. This article considers functions that are bimonotone in the sense that whenever and . A two-variable polynomial with non-negative coefficients is a typical example. The problem is to efficiently enumerate all pairs such that the values appear in increasing order. We present an algorithm that is memory-efficient and highly parallelizable. In order to enumerate the first values of , the algorithm only builds up a priority queue of length at most . In terms of bit-complexity this ensures that the algorithm takes time and requires memory , which considerably improves on the memory bound provided by a naïve approach, and extends the semimonotone enumeration algorithm previously considered by R.L.Ekl and D.J.Bernstein.

**1.**Daniel J. Bernstein,*Enumerating solutions to 𝑝(𝑎)+𝑞(𝑏)=𝑟(𝑐)+𝑠(𝑑)*, Math. Comp.**70**(2001), no. 233, 389–394. MR**1709145**, 10.1090/S0025-5718-00-01219-9**2.**Randy L. Ekl,*Equal sums of four seventh powers*, Math. Comp.**65**(1996), no. 216, 1755–1756. MR**1361807**, 10.1090/S0025-5718-96-00768-5**3.**Ronald L. Graham, Donald E. Knuth, and Oren Patashnik,*Concrete mathematics*, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1989. A foundation for computer science. MR**1001562****4.**Richard K. Guy,*Unsolved problems in number theory*, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR**2076335****5.**G. H. Hardy and E. M. Wright,*An introduction to the theory of numbers*, Oxford, at the Clarendon Press, 1954. 3rd ed. MR**0067125****6.**Donald E. Knuth,*The art of computer programming. Vol. 1: Fundamental algorithms*, Second printing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR**0286317****7.**Donald E. Knuth,*The art of computer programming. Volume 3*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR**0445948****8.**John Leech,*Some solutions of Diophantine equations*, Proc. Cambridge Philos. Soc.**53**(1957), 778–780. MR**0090602****9.**E. Rosenstiel, J. A. Dardis, and C. R. Rosenstiel,*The four least solutions in distinct positive integers of the Diophantine equation 𝑠=𝑥³+𝑦³=𝑧³+𝑤³=𝑢³+𝑣³=𝑚³+𝑛³*, Bull. Inst. Math. Appl.**27**(1991), no. 7, 155–157. MR**1125858****10.**David W. Wilson,*The fifth taxicab number is 48988659276962496*, J. Integer Seq.**2**(1999), Article 99.1.9, 1 HTML document (electronic). MR**1722364**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
68P10,
11Y50,
68W10,
11Y16,
11D45

Retrieve articles in all journals with MSC (2000): 68P10, 11Y50, 68W10, 11Y16, 11D45

Additional Information

**Michael Eisermann**

Affiliation:
Institut Fourier, Université Grenoble I, France

Email:
Michael.Eisermann@ujf-grenoble.fr

DOI:
https://doi.org/10.1090/S0025-5718-08-02162-5

Keywords:
Sorting and searching,
diophantine equation,
bimonotone function,
sorted enumeration,
semimonotone enumeration,
bimonotone enumeration

Received by editor(s):
July 27, 2005

Received by editor(s) in revised form:
June 22, 2007

Published electronically:
June 16, 2008

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.