Re: Hansen chains do not always produce optimum addition chains

"Gerry Myerson" <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:gerry-CEF499.16202701082005@xxxxxxxxxxxxxxxxxxxxx
> In article <42edacbd$1@xxxxxxxxxxxxxxxxxx>,
> "Neill Clift [MSFT]" <neillc@xxxxxxxxxxxxx> wrote:
>
>> In The Art of Computer Programming, Third Edition, Vol. 2, 4.6.3,
>> Page 485, question 42 is:
>> 'Is l(2n-1) ? n - 1 - l(n) for all positive integers n? Does equality
>> always hold? Does l(n) = l0(n)?'.
>
> You must be using some symbols that don't come through on my machine.
> The question in Knuth (although I'm looking at 2nd edition) is
>
> 'Is l(2^n - 1) less than or equal to n - 1 + l(n) for all positive
> integers n? Does equality always hold? Does l(n) = l^0(n)?'

I pasted from a word document for the letter I mailed to Knuth.
So thats how the <= got converted to ?.

>
> I can't help you with anything, but I wonder whether you have seen
> the discussion at problem C6 of the 3rd edition of Guy's Unsolved
> Problems in Number Theory. Guy has a long bibliography.

When I searched for Hansen chains to make sure this was the
correct name for them (l^0 chains is how Knuth names them) I saw
mention that this book contains something. I haven't seen it and
coulding find any more details of it. I have ordered the book.
>
> If you've discovered something that's not in Guy's book,
> he'd probably appreciate it if you send him whatever
> you've got written up for inclusion in a 4th edition.
>
I dropped him a note and look forward to looking at the book.


.

Relevant Pages