[seqfan] Re: A puzzle from Emissary

[Charles Greathouse]

Two (presumably) hard sequences, for any given generalization to
arbitrary bases, would be "the constant C in base n" and "the constant
C in base n, ignoring finitely many integers".

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Wed, Nov 30, 2011 at 4:50 PM,  <franktaw at netscape.net> wrote:
> I should have noted that k=5 is a special case. You can't get 8 from 11111,
> but you can get 16, and you can get 8 from any other odd number with 5 ones.
>
> (The argument below fails for k=5 at the last step; adding even a single 4
> makes the total too big, and you can't in general add more than two ones.)
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: franktaw <franktaw at netscape.net>
>
> Here's another approach to the same result.
>
> Given a number with k 1's, 2^(n-1) < k <= 2^n, we show that it is
> always possible to obtain 2^n as a sum.
>
> The base case is to have all the ones individually, summing to k.
>
> We can always increase this by using at most 2 of the ones to get a sum
> 1 larger. Just take any 1 that is not at the end, and make it the first
> bit of a two-bit number. Whether the following bit is 0 or 1, the total
> has increased by 1.
>
> We can also always use at most 3 of the ones to make the sum 4 larger.
> If we have 11x, the resulting 3-bit number is 4 larger than its number
> of bits. For 1011, use the final 11 and another bit the same way. If we
> have 100, making it a 3-bit number adds 3, and at most 2 more bits are
> required to add 1 more (as above). Finally, if we have 1010x, 10 + 10x
> adds 4.
>
> It is then a simple combinatorial matter to show that any k can be
> increased to the next power of 2 without using up all the bits.
>
> Franklin T. Adams-Watters
>
>> Andrew Weimholt
>>
>> I can prove that at most 2 transforms are needed to reach 1. (i.e.
>
> that C=2).
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>