Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The Postage Stamp Problem:
An algorithm to determine the $h$-range
on the $h$-range formula
on the extremal basis problem for $k=4$


Author: Svein Mossige
Journal: Math. Comp. 69 (2000), 325-337
MSC (1991): Primary 11B13, 11D85
DOI: https://doi.org/10.1090/S0025-5718-99-01204-1
Published electronically: August 23, 1999
MathSciNet review: 1680907
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given an integral ``stamp" basis $A_k$ with $1=a_1\ <\ a_2\ <\ldots <\ a_k$ and a positive integer $h$, we define the $h$-range $n(h,A_k)$ as

\begin{displaymath}n(h,A_k)=\max\{N\in {\mathbf N} \mid n \leq N \Longrightarrow n= \sum _{1}^{k}x_{i}a_{i},\, \sum _{1}^{k}x_{i}\leq h,\;\;n,\;x_{i} \in {\mathbf N}_{0}\}.\end{displaymath}

${\mathbf N}_{0}={\mathbf N}\cup \{0\}$. For given $h$ and $k$, the extremal basis $A_{k}^{*}$ has the largest possible extremal $h$-range

\begin{displaymath}n(h,k)=n(h,A_{k}^{*})=\max _{A_k} n(h,A_k).\end{displaymath}

We give an algorithm to determine the $h$-range. We prove some properties of the $h$-range formula, and we conjecture its form for the extremal $h$-range. We consider parameter bases $A_k=A_k(h)$, where the basis elements $a_i$ are given functions of $h$. For $k=4$ we conjecture the extremal parameter bases for $h\geq 11385$.


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

  • 1. R. Braunschädel, Zum Reichweitenproblem, Diplomarbeit, Math. Inst., Joh. Gutenberg-Univ., Mainz 1988.
  • 2. M.F.Challis, Two new techniques for computing extremal $h$-bases $A_k$, Computer J. 36 (1993), 117-126.
  • 3. G. Hofmeister, Über eine Menge von Abschnittbasen, J. Reine Angew. Math. 213 (1963) 43-57. MR 31:149
  • 4. G. Hofmeister, Asymptotische Abschätzungen für dreielementige Extremalbasen in natürlichen Zahlen, J. Reine Angew. Math. 232 (1968) 77-101. MR 38:1068
  • 5. G. Hofmeister, Zum Reichweitenproblem, Mainzer Seminarberichte in Additiven Zahlentheorie, 1 (1983), 30-52.
  • 6. G. Hofmeister, C. Kirfel and H. Kolsdorf, Extremale Reichweiten, Inst. Rep. No 60, Dept. of pure Math., Univ. of Bergen, 1991.
  • 7. C. Kirfel, On Extremal Bases for the $h$-range Problem, I, II, Inst. Rep. Nos. 53, 55, Dept. of pure Math., Univ. of Bergen, 1989, 1990.
  • 8. C. Kirfel, Extremale asymptotische Reichweitenbasen, Acta Arith. (1992) 279-288. MR 92m:11012
  • 9. W.F. Lunnon, A Postage Stamp Problem, Compt. J. 12 (1969), 377-380. MR 40:6745
  • 10. S. Mossige, Algorithms for computing the $h$-range of the Postage Stamp Problem, Math. Comp., 36 (1981), 575-582. MR 82e:11095
  • 11. S. Mossige, On the extremal $h$-range of the Postage Stamp Problem with four Stamp denominations, Dissertation, Inst. Rep. No. 41, Dept. of pure Math., Univ. of Bergen, 1986.
  • 12. S. Mossige, On extremal $h$-bases $A_{4}$, Math. Scand. 61 (1987), 5-16. MR 89e:11008
  • 13. S. Mossige, The Postage Stamp Problem. An algorithm to determine the $h$-range. On the $h$-range formula. On the extremal basis problem for $k=4$, Inst. Rep. No. xx, Dept. of pure Math., Univ. of Bergen, 1995, 1-74.
  • 14. A. Mrose, Die Bestimmung der extremalen regulären Abschnittbasen mit Hilfe einer Klasse von Kettenbruchdeterminanten, Dissertation, Freie Universität Berlin, 1969.
  • 15. Ø. Rødseth, An upper bound for the $h$-range of the Postage Stamp Problem, Acta Arith. 54 (1990), 301-306. MR 91h:11013
  • 16. J. Riddell and C. Chan, Some extremal 2-bases, Math. Comp. 32(1978), 630-634. MR 57:16244
  • 17. E.S. Selmer, The Local Postage Stamp Problem, I-III, Inst. Rep. Nos. 42, 44, 47, Dept. of Pure Math., Univ. of Bergen, 1986, 1990.
  • 18. E.S. Selmer, Associate Bases in the Postage Stamp Problem, J. Number Theory, 42, 3,(1992), 320-336. MR 94b:11012
  • 19. E.S. Selmer, Asymptotic $h$-ranges and dual bases, Inst. Rep. No. 56, Dept. of Pure Math., Univ. of Bergen, 1990.
  • 20. A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, I, J. Reine Angew. Math. 194 (1955), 40-65. MR 17:713a

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11B13, 11D85

Retrieve articles in all journals with MSC (1991): 11B13, 11D85


Additional Information

Svein Mossige
Affiliation: University of Bergen, Department of Mathematics, Joh. Brunsgt. 12, N-5008 Bergen, Norway
Email: svein.mossige@mi.uib.no

DOI: https://doi.org/10.1090/S0025-5718-99-01204-1
Received by editor(s): March 13, 1996
Published electronically: August 23, 1999
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society