Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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 (31 #149)
  • 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 (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. Christoph Kirfel, Extremale asymptotische Reichweitenbasen, Acta Arith. 60 (1992), no. 3, 279–288 (German). MR 1149861 (92m:11012)
  • 9. W. F. Lunnon, A postage stamp problem, Comput. J. 12 (1969), 377–380. MR 0253531 (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. Svein Mossige, On extremal ℎ-bases 𝐴₄, Math. Scand. 61 (1987), no. 1, 5–16. MR 929394 (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. Ø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 (91h:11013)
  • 16. J. Riddell and C. Chan, Some extremal 2-bases, Math. Comp. 32 (1978), no. 142, 630–634. MR 0476685 (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. Ernst S. Selmer, Associate bases in the postage stamp problem, J. Number Theory 42 (1992), no. 3, 320–336. MR 1189510 (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. Alfred Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. I, II, J. Reine Angew. Math. 194 (1955), 40–65, 111–140 (German). MR 0075228 (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

PII: S 0025-5718(99)01204-1
Received by editor(s): March 13, 1996
Published electronically: August 23, 1999
Article copyright: © Copyright 1999 American Mathematical Society