Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

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(s): Svein Mossige.
Journal: Math. Comp. 69 (2000), 325-337.
MSC (1991): Primary 11B13, 11D85
Posted: August 23, 1999
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

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 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: 10.1090/S0025-5718-99-01204-1
PII: S 0025-5718(99)01204-1
Received by editor(s): March 13, 1996
Posted: August 23, 1999
Copyright of article: Copyright 1999, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google