<HTML><BODY><DIV style='font-family: "Verdana"; font-size: 10pt;'><DIV>
<DIV>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).</DIV>
<DIV> </DIV>
<DIV>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):</DIV>
<DIV> </DIV>
<DIV>3</DIV>
<DIV>3 3</DIV>
<DIV>3 3 4</DIV>
<DIV>4 4 4 4</DIV>
<DIV>4 3 4 4 5</DIV>
<DIV>4 4 4 4 5 4</DIV>
<DIV>4 4 4 4 5 4 5</DIV>
<DIV>5 5 5 5 5 5 5 5</DIV>
<DIV>4 4 5 4 5 4 5 5 6</DIV>
<DIV>5 5 5 5 5 5 5 5 6 5</DIV>
<DIV>5 5 5 5 5 5 5 5 6 5 6</DIV>
<DIV>5 5 5 5 6 6 5 5 6 5 6 6</DIV>
<DIV>5 4 5 5 6 4 5 5 6 5 6 6 6</DIV>
<DIV> </DIV>
<DIV>This raises some questions:</DIV>
<DIV> </DIV>
<DIV>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?</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>Franklin T. Adams-Watters<BR>16 W. Michigan Ave.<BR>Palatine, IL 60067<BR>847-776-7645</DIV></DIV></DIV>
<hr style="MARGIN-TOP:10px" >
<b>Try the New Netscape Mail Today!</b><br />
Virtually Spam-Free | More Storage | Import Your Contact List<br /><a href="http://mail.netscape.com">http://mail.netscape.com</a>
</BODY></HTML>