Double Addition Chains

[franktaw at netscape.net]

Looking at addition chains, I got interested in the question, given two numbers m and n, what is the shortest addition chain that contains both m and n?  We'll call this l(m,n).
 
Taking wlog m<n, we can also skip the cases m=1 and m=2, since every addition chain includes 1 and 2 (except the trivial case with just 1).  So starting with 3,4, we have the following (assuming no errors):
 
3
3 3
3 3 4
4 4 4 4
4 3 4 4 5
4 4 4 4 5 4
4 4 4 4 5 4 5
5 5 5 5 5 5 5 5
4 4 5 4 5 4 5 5 6
5 5 5 5 5 5 5 5 6 5
5 5 5 5 5 5 5 5 6 5 6
5 5 5 5 6 6 5 5 6 5 6 6
5 4 5 5 6 4 5 5 6 5 6 6 6
 
This raises some questions:
 
First, note that some rows are constant: (trivially 2 and 3, not really 4 since l(1,4)=l(2,4)=2), 5, 7, 11.  Obviously, these rows must be record values for l(n) (cf A003064); and I have verified n=19 is also constant.  Does every number in A003064 have this property?  Do infinitely many?
 
Second, to this point, l(4,n) = l(n) for every n>4.  In other words, every n>4 has a minimal length addition chain that includes 4.  Is this true generally?  If not, for which n is it not true?  What about higher powers of 2?  (Non-powers of 2 need not apply.)  l(8,15) = 6 > l(15) = 5, but it might still be true for sufficiently large values of n.
 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060131/9ab3bee1/attachment.htm>