Proportionally modular diophantine inequalities and the SternBrocot tree
Authors:
M. Bullejos and J. C. Rosales
Journal:
Math. Comp. 78 (2009), 12111226
MSC (2000):
Primary 11D75, 20M14
Published electronically:
August 12, 2008
MathSciNet review:
2476582
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Given positive integers and to compute a generating system for the numerical semigroup whose elements are all positive integer solutions of the inequality is equivalent to computing a Bézout sequence connecting two reduced fractions. We prove that a proper Bézout sequence is completely determined by its ends and we give an algorithm to compute the unique proper Bézout sequence connecting two reduced fractions. We also relate Bézout sequences with paths in the SternBrocot tree and use this tree to compute the minimal positive integer solution of the above inequality.
 1.
A. Bogomolny, SternBrocot Tree. Binary Encoding; see the website: www.cuttheknot.org/blue/encoding.shtml.
 2.
Ronald
L. Graham, Donald
E. Knuth, and Oren
Patashnik, Concrete mathematics, 2nd ed., AddisonWesley
Publishing Company, Reading, MA, 1994. A foundation for computer science.
MR
1397498 (97d:68003)
 3.
J.
L. RamírezAlfonsín, Complexity of the Frobenius
problem, Combinatorica 16 (1996), no. 1,
143–147. MR 1394516
(97d:11058), http://dx.doi.org/10.1007/BF01300131
 4.
J.
L. Ramírez Alfonsín, The Diophantine Frobenius
problem, Oxford Lecture Series in Mathematics and its Applications,
vol. 30, Oxford University Press, Oxford, 2005. MR 2260521
(2007i:11052)
 5.
J.
C. Rosales, P.
A. GarcíaSánchez, J.
I. GarcíaGarcía, and J.
M. UrbanoBlanco, Proportionally modular Diophantine
inequalities, J. Number Theory 103 (2003),
no. 2, 281–294. MR 2020273
(2004k:20127), http://dx.doi.org/10.1016/j.jnt.2003.06.002
 6.
J. C. Rosales, P. A. GarcíaSánchez and J. M. UrbanoBlanco, The set of solutions of a proportionally modular diophantine inequality, Journal of Number Theory 128 (2008), 453467.
 7.
J. C. Rosales and P. Vasco, The smallest positive integer that is a solution of a proportionally modular diophantine inequality, to appear in Mathematical Inequalities & Applications (2008), www.elemath.com.
 8.
J. J. Sylvester, Mathematical questions with their solutions, Educational Times 41 (1884), 21.
 1.
 A. Bogomolny, SternBrocot Tree. Binary Encoding; see the website: www.cuttheknot.org/blue/encoding.shtml.
 2.
 R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics, 2nd edition, AddisonWesley, 1994. MR 1397498 (97d:68003)
 3.
 J. L. Ramírez Alfonsín, Complexity of the Frobenius problem, Combinatorica 16 (1) (1996), 143147. MR 1394516 (97d:11058)
 4.
 J. L. Ramírez Alfonsín, The diophantine Frobenius problem, Oxford Univ. Press. (Vol. 30) 2005. MR 2260521 (2007i:11052)
 5.
 J. C. Rosales, P. A. GarcíaSánchez, J. I. GarcíaGarcía and J. M. UrbanoBlanco, Proportionally modular diophantine inequalities, Journal of Number Theory 103 (2003), 281294. MR 2020273 (2004k:20127)
 6.
 J. C. Rosales, P. A. GarcíaSánchez and J. M. UrbanoBlanco, The set of solutions of a proportionally modular diophantine inequality, Journal of Number Theory 128 (2008), 453467.
 7.
 J. C. Rosales and P. Vasco, The smallest positive integer that is a solution of a proportionally modular diophantine inequality, to appear in Mathematical Inequalities & Applications (2008), www.elemath.com.
 8.
 J. J. Sylvester, Mathematical questions with their solutions, Educational Times 41 (1884), 21.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11D75,
20M14
Retrieve articles in all journals
with MSC (2000):
11D75,
20M14
Additional Information
M. Bullejos
Affiliation:
Departamento de Álgebra, Universidad de Granada, 18071 Granada, Spain
Email:
bullejos@ugr.es
J. C. Rosales
Affiliation:
Departamento de Álgebra, Universidad de Granada, 18071 Granada, Spain
Email:
jrosales@ugr.es
DOI:
http://dx.doi.org/10.1090/S002557180802173X
PII:
S 00255718(08)02173X
Keywords:
Diophantine inequation,
numerical semigroup,
SternBrocot tree
Received by editor(s):
January 3, 2008
Received by editor(s) in revised form:
April 4, 2008
Published electronically:
August 12, 2008
Additional Notes:
This work was partially supported by research projects MTM200503227 and MTM200762346
Article copyright:
© Copyright 2008
American Mathematical Society
