cp's OEIS Frontend

T(n,k) <= A339334(n,k).

T(n,k) >= 2n - k, with equality if and only if n <= A001212(k).

a(n) = largest span (range) attained by a restricted additive 2-basis of length n; an additive 2-basis is restricted if its span is exactly twice its largest element. - Jukka Kohonen, Apr 23 2014

If one counts all subsets S of T={0,1,2,...n} such that each number in T is the sum of two elements of S, sequence A066062 is obtained.

Since each k-subset of S covers at most binomial(k + 1, 2) members of T, we have binomial(a(n) + 1, 2) >= n + 1. It follows that A002024(n-1) is a lower bound. - Rob Pratt, May 14 2004

This is an instance of the <= 2-stamp postage problem with n denominations. For n > 0, a(n) = 1 + the smallest i such that A001212(i) >= n (adding one adjusts for the fact that A001212 has offset 1). - Tim Peters (tim.one(AT)comcast.net), Aug 25 2006

A planar additive basis is a set of points with nonnegative integer coordinates such that their pairwise sums cover a given rectangle of points with integer coordinates. Pairwise sums of a point with itself are included.

a(n) <= 2n+1, because there is an L-shaped basis of that size.

a(n) <= 2n if n is even and nonzero, because of a square-shaped "boundary basis" with sides at coordinates 0 and n/2.

a(n) >= a(n-1). Hence this sequence is defined by its jumps: "Maximum k such that there exists an order two basis for the interval [1, k] with no multiplicity greater than n". This sequence has still too few known terms to have its own entry. It starts: 5, 55, 323. The next term is >= 1006 (in all likelihood it is greater).

a(n) is the minimum over all branches of length n in A265262 of the maximum number in each branch.

If the number 0 is allowed to be part of the basis then the "sum of at most two" from the definition should be changed to "sum of two".

It is believed that a(n) tends to infinity. Erdős and Turán conjectured in 1941 that any basis of order two for all the natural numbers cannot avoid large multiplicities. The two conjectures can easily be proved to be equivalent.

The bases yielding the highest n with given a(n) = k for each k are:

1: 1 3 5 (n <= 5)

2: 1 2 4 5 7 11 16 19 24 32 40 45 52 53 (n <= 55)

3: 1 2 3 5 6 8 9 17 20 22 28 29 40 47 53 57 69 83 90 99 107 117 131 141 152 162 172 182 193 203 217 227 237 248 258 268 279 289 303 313 (n <= 324)

For k = 4 the following basis serves for n <= 1006:

1 2 3 4 5 7 8 9 12 13 17 23 33 39 49 55 64 66 80 86 95 97 111 113 126 134 140 153 162 178 181 192 203 210 231 242 254 275 281 299 303 311 325 335 346 386 405 423 435 446 469 486 504 521 538 556 590 602 620 639 656 673 690 739 772 805 822 840 855 873 890 907 940 957 974 987 996

Benjamin Franklin, first Postmaster General of the United States, applied computational complexity theory to Economics by changing the business plan for American mail by changing from payment by distance to payment by weight. "Before stamps were used a person had to collect his mail at the post office and pay for it. Franklin stopped the money loss on unclaimed mail in Philadelphia by printing in his paper the names of persons who had mail awaiting them. He also developed a simple, accurate way of keeping post-office accounts. In 1753 Franklin was made deputy postmaster general for all the colonies." [Encyclopedia Britannica]

A fundamental result of Erdos and Graham is that every integer basis possesses only finitely many essential elements. Grekos refined this, showing that the number of essential elements in a basis or order h is bounded by a function of h only. Deschamps and Farhi (2007) proved a best possible upper bound on this function, which contains a constant whose digits are this sequence.

Abstract: Plagne recently determined the asymptotic behavior of the function E(h), which counts the maximum possible number of essential elements in an additive basis for N of order h. Here we extend his investigations by studying asymptotic behavior of the function E(h,k), which counts the maximum possible number of essential subsets of size k, in a basis of order h. For a fixed k and with h going to infinity, we show that

E(h,k) = Theta_{k} ([h^{k}/log h]^{1/(k+1)}). The determination of a more precise asymptotic formula is shown to depend on the solution of the well-known "postage stamp problem" in finite cyclic groups. On the other hand, with h fixed and k going to infinity, we show that E(h,k) ~ (h-1) (log k)/(log log k).