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 Free Access

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. Gerd Hofmeister, Über eine Menge von Abschnittsbasen, J. Reine Angew. Math. 213 (1963/1964), 43–57 (German). MR 0175873, https://doi.org/10.1515/crll.1964.213.43
  • 4. Gerd Hofmeister, Asymptotische Abschätzungen für dreielementige Extremalbasen in natürlichen Zahlen, J. Reine Angew. Math. 232 (1968), 77–101 (German). MR 0232745, https://doi.org/10.1515/crll.1968.232.77
  • 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. Christoph Kirfel, Extremale asymptotische Reichweitenbasen, Acta Arith. 60 (1992), no. 3, 279–288 (German). MR 1149861
  • 9. W. F. Lunnon, A postage stamp problem, Comput. J. 12 (1969), 377–380. MR 0253531, https://doi.org/10.1093/comjnl/12.4.377
  • 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. Svein Mossige, On extremal ℎ-bases 𝐴₄, Math. Scand. 61 (1987), no. 1, 5–16. MR 929394, https://doi.org/10.7146/math.scand.a-12188
  • 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. Øystein J. Rødseth, An upper bound for the ℎ-range of the postage stamp problem, Acta Arith. 54 (1990), no. 4, 301–306. MR 1058892
  • 16. J. Riddell and C. Chan, Some extremal 2-bases, Math. Comp. 32 (1978), no. 142, 630–634. MR 0476685, https://doi.org/10.1090/S0025-5718-1978-0476685-7
  • 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. Ernst S. Selmer, Associate bases in the postage stamp problem, J. Number Theory 42 (1992), no. 3, 320–336. MR 1189510, https://doi.org/10.1016/0022-314X(92)90097-9
  • 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