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, 106, 107, 113, 118, 122, 123, 129, 131, 139, 140, 145, 148, 150, 158, 162, 165, 168, 170, 180, 183, 186

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

From Martin Fuller, Jul 26 2025: (Start)

A slightly better upper bound can be obtained from the following set: {1, 2, ..., r-1; n+1-r*(s-1), n+1-r*(s-2), ..., n+1-r} where r*s <= n+1 < r*(s+1). If n+1-r*s <= r/2-1 then n+1-r*s can be removed from the set.

There is an optimal set of this form for 54 of the first 100 terms of the sequence. (End)

Links

Martin Fuller, Table of n, a(n) for n = 0..100

Martin Fuller, Python program

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[{#, #}]]] == {} &]]

Prog

(Python) # See Fuller link.

Crossrefs

Sequence in context: A219381 A219852 A023842 * A227128 A061795 A110261

Adjacent sequences: A165882 A165883 A165884 * A165886 A165887 A165888

Keyword

nonn

Author

David Bevan, Sep 29 2009

Extensions

a(41) onwards from Martin Fuller, Jul 26 2025

Status

approved