A165885 Minimum sum of a set of positive integers such that every positive integer <= n is the sum of 1 or 2 elements of the set

0, 1, 1, 3, 3, 6, 6, 8, 8, 12, 12, 15, 15, 19, 20, 24, 24, 30, 30, 34, 35, 41, 42, 47, 47, 52, 52, 60, 60, 64, 65, 72, 72, 77, 78, 86, 88, 91, 92, 100, 100

Offset

0,4

Comments

If it is possible to make every value from 1 to n using at most 2 of the coins used in a country, what is the minimum possible value of the sum of the coins in this country?

By considering sets {1, 2, ..., r, 2r, 3r, ..., (s-1)r}, it is conjectured that the asymptotic behavior is a(n) ~ 3/4 * 2^(1/3) * n^(4/3).

Links

Table of n, a(n) for n=0..40.

PuzzleUp, 2009 No 10, Coins

Example

a(8) = 8: {1,3,4}

Mathematica

a[n_] := Min[Total /@ Select[Subsets[Range[n], Floor[(n + 1)/2]], Complement[Range[n], Total /@ Join[Subsets[ #, {1, 2}], Transpose[{#, #}]]] == {} &]]

Crossrefs

Sequence in context: A219381 A219852 A023842 * A227128 A061795 A110261

Adjacent sequences: A165882 A165883 A165884 * A165886 A165887 A165888

Keyword

nonn,more

Author

David Bevan, Sep 29 2009

Status

approved