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

Mossige, Svein

doi:10.1090/S0025-5718-99-01204-1

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

The Postage Stamp Problem:
An algorithm to determine the -range
on the -range formula
on the extremal basis problem for

Author: Svein Mossige
Journal: Math. Comp. 69 (2000), 325-337
MSC (1991): Primary 11B13, 11D85
Posted: August 23, 1999
MathSciNet review: 1680907
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given an integral ``stamp" basis with $1=a_1\ <\ a_2\ <\ldots <\ a_k$ and a positive integer , we define the -range 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 and , the extremal basis $A_{k}^{*}$ has the largest possible extremal -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 -range. We prove some properties of the -range formula, and we conjecture its form for the extremal -range. We consider parameter bases , where the basis elements are given functions of . For we conjecture the extremal parameter bases for $h\geq 11385$ .

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 , 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 , 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), http://dx.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 (94b:11012), http://dx.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. 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)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|