Re: Hansen chains do not always produce optimum addition chains

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

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.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: randomness of a series of numbers
    ... the above resource was the only place I can find about this "phase ... Get a copy of Donald E. Knuth, The Art of Computer Programming ... Third Edition. ...
    (sci.math)
  • Re: Periodicity of a^n mod c
    ... I have requested The Art of Computer Programming, Volume 2, Seminumerical ... Algorithms, from a nearby branch of my jursdiction's public library, for pickup ... at my local branch. ...
    (sci.math)
  • Re: Towards a Formula for Primes
    ... Niven has written a couple of good books ... on irrationality. ... I was reading "The Art of Computer Programming" by ...
    (sci.math)
  • Donald Knuth to speak at the Computer History Museum
    ... A Dozen Precursors of Fortran ... Donald Knuth is perhaps best known for having written the classic, ... In The Art of Computer Programming, ...
    (comp.lang.fortran)
  • Re: Big oh Notation
    ... Oskar Sigvardsson wrote: ... > Patashnik, excellent book. ... > three volumes so far) The Art Of Computer Programming. ...
    (comp.lang.java)