A014616 a(n) = solution to the postage stamp problem with 2 denominations and n stamps.

2, 4, 7, 10, 14, 18, 23, 28, 34, 40, 47, 54, 62, 70, 79, 88, 98, 108, 119, 130, 142, 154, 167, 180, 194, 208, 223, 238, 254, 270, 287, 304, 322, 340, 359, 378, 398, 418, 439, 460, 482, 504, 527, 550, 574, 598, 623, 648, 674, 700, 727, 754, 782, 810, 839, 868

Offset: 1

Author

Eric W. Weisstein

Keywords

• nonn
• nice
• easy

Comments

Fred Lunnon [W. F. Lunnon] defines "solution" to be the smallest value not obtainable by the best set of stamps. The solutions given are one lower than this, that is, the sequence gives the largest number obtainable without a break using the best set of stamps.

a(n-2), for n >= 3, is the number of independent entries of a bisymmetric n X n matrix B_n with B_n[1,1] and B_n[n,n] fixed. Hence a(n-2) = A002620(n+1) - 2. See the Jul 07 2015 comment on A002620. For n=1 and n=2 this matrix B_n is fixed. Bisymmetric matrices B_n, with B_n[1,1] and B_n[n,n] fixed, are, for n >= 3, determined by giving the a(n-2) entries for [1,2], ...., [1,n-1]; [2,2], ..., [2,n-1]; [3,3], ..., [3,n-2]; ..., [ceiling(n/2),n-(ceiling(n/2)-1)]. - Wolfdieter Lang, Aug 16 2015

a(n-1) is the largest possible n-th element in an additive basis of order 2. - Charles R Greathouse IV, May 05 2020

Examples

			Bisymmetric matrix B_5, with B_5[1,1] and B_5[5,5] fixed, have a(3) free entries: for rows 1 and 2: each 3, row 3:  1, altogether 3 + 3 + 1 = 7 = a(5-2). Mark the corresponding matrix entries with x, and obtain a pattern symmetric around the central vertical. - _Wolfdieter Lang_, Aug 16 2015
		

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section C12, pp. 185-190.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..10000
• Mario Bravo, Thierry Champion, and Roberto Cominetti, Universal bounds for fixed point iterations via optimal transport metrics, arXiv:2108.00300 [math.OC], 2021.
• Erich Friedman, Postage stamp problem
• W. F. Lunnon, A postage stamp problem, Comput. J. 12 (1969) 377-380.
• Alfred Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. I., Journal für die reine und angewandte Mathematik (1955), Volume: 194, page 40-65. See p. 47.
• Hugh Thomas and Stephanie van Willigenburg, Compact symmetric solutions to the postage stamp problem, arXiv:0706.3250 [math.NT], 2007-2008.
• Amitabha Tripathi, A Note on the Postage Stamp Problem, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.3.
• Eric Weisstein's World of Mathematics, Postage stamp problem.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).
• Index to sequences related to the Postage Stamp Problem.

Crossrefs

A row or column of the array A196416 (possibly with 1 subtracted from it).

Cf. A002620, A004116, A024206, A028884, A046691.

Programs

Haskell

a014616 n = (n * (n + 6) + 1) `div` 4 -- Reinhard Zumkeller, Apr 07 2013

Magma

[(2*n*(n+6)-(-1)^n+1)/8: n in [1..60]]; // Vincenzo Librandi, Jul 09 2011

Mathematica

a[n_?OddQ] := (n^2 + 6*n + 1)/4; a[n_?EvenQ] := n*(n + 6)/4; Table[a[n], {n, 1, 56}] (* Jean-François Alcover, Dec 14 2011, after first formula *)
LinearRecurrence[{2,0,-2,1},{2,4,7,10},60] (* Harvey P. Dale, Oct 04 2015 *)

PARI

a(n)=(n^2 + 6*n + 1)\4 \\ Charles R Greathouse IV, Feb 06 2017

Formula

a(n) = floor((n^2 + 6*n + 1)/4).

a(n) = A002620(n+3) - 2 = A024206(n+2) - 1 = (2*n*(n+6)-(-1)^n+1)/8.

G.f.: x*(-2 + x^2)/((1 + x)*(x - 1)^3). - R. J. Mathar, Jul 09 2011

a(n) = floor(A028884(n+1)/4). - Reinhard Zumkeller, Apr 07 2013

a(n)+a(n+1) = A046691(n+1). - R. J. Mathar, Mar 13 2021

a(n) = 2*n + A002620(n-1). - Michael Chu, Apr 28 2022

a(n) = A004116(n) + 1. - Michael Chu, May 02 2022

E.g.f.: (x*(7 + x)*cosh(x) + (1 + 7*x + x^2)*sinh(x))/4. - Stefano Spezia, Nov 09 2022

Sum_{n>=1} 1/a(n) = 67/36 - cot(sqrt(2)*Pi)*Pi/(2*sqrt(2)). - Amiram Eldar, Dec 10 2022

Extensions

Entry improved by comments from John Seldon (johnseldon(AT)onetel.com), Sep 15 2004

More terms from John W. Layman, Apr 13 1999