A060802 To weigh from 1 to n, make the heaviest weight as small as possible, under the condition of using fewest pieces of different, single weights; a(n) = weight of the heaviest weight.

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 7, 8, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 10, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 18, 18, 18, 19, 19, 20, 20, 21

Offset

1,2

Comments

Starting at n = 2^x (x > 2) you get: 3 entries of 2^floor(log_2(x)-2)+2, then 2 entries of each subsequent integer until you reach the halfway point between 2^x and 2^(x+1), then 1 entry of each subsequent integer until you reach 2^(x+1)-1. Proved (see link). - David Consiglio, Jr., Jan 08 2015

Links

David Consiglio, Jr., Table of n, a(n) for n = 1..1024

David Consiglio, Jr., Python that quickly provides weights given the proof by Schoenfield

David Consiglio, Jr., Proof for sequence generation - Schoenfield and Consiglio

Formula

After the 8th term:

If 2^x <= n <= (2^x)+2 then a(n) = 2 ^ floor(base2log(x)-2)+2 (see A052548)

If (2^x)+2 < n and n+1 < (2^x + 2^x+1)/2 then a(n) and a(n+1) = a(n-1)+1

If (2^x+2^x+1)/2 <= n then a(n) = a(n-1)+1. - David Consiglio, Jr., Jan 08 2015

Example

a(20)=7 because every number from 1 to 20 can be obtained from {1,2,4,6,7}.

Crossrefs

Sequence in context: A026099 A049727 A260690 * A132073 A087817 A091497

Adjacent sequences: A060799 A060800 A060801 * A060803 A060804 A060805

Keyword

nonn

Author

Sen-Peng Eu, Apr 27 2001

Extensions

a(32)-a(1024) from David Consiglio, Jr., Jan 08 2015

Status

approved