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

Author

Sen-Peng Eu, Apr 27 2001

Keywords

• nonn

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

Examples

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

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

Extensions

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