cp's OEIS Frontend

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).