Linear cost addition chains

[franktaw at netscape.net]

Well, conjecture 2 is wrong - the minimum cost addition chain for 2n 
always generates n first, and then doubles it.

A quick outline of a proof:

* The minimum cost t(n) >= 2n-1, with equality only if n is a power of 
2.
* Define t_3(n) to be the minimum cost of an addition chain for n which 
includes 3.  Then t_3(n) < 8/3 n for n >= 3.  The induction step uses a 
doubling for n even, a chain ending k,2k,2k+1,4k+1 for n = 4k+1, and a 
chain ending k,2k,2k+3,4k+3 for n = 4k+3.  It follows that t(n) < 8/3 n.
* For n even, t(n) < 7/3 n.  Use the previous result for n/2, and add a 
doubling step.
* Any addition chain that does not end with a doubling has a cost of at 
least 7/3 n - 1, with equality only for n = 3 2^j.  Look at the two 
terms just before n; these must sum to at least n, with the 3rd from 
the last being at least n/3.
* The minimum cost addition chain for 3 2^j is 1,2,3,6,12,...,3 2^j.

Combining the last three, the minimal cost for even n is always 
obtained by ending with a doubling step.

It follows that conjecture 1 is correct: in particular, the minimum 
cost addition chain for 382 has length (at least) 12, while the minimum 
length chain for 382 is 11.

Franklin T. Adams-Watters


-----Original Message-----
From: franktaw at netscape.net

What is the minimum cost addition chain for n, where the cost is the 
sum of the numbers in the addition chain? 
...
Based on past experience with addition chains, I would conjecture the 
following: 
 
1. There are n for which the minimum cost addition chain does not have 
shortest length. 
2. There are even n for which the minimum cost addition chain does not 
first generate n/2. 
3. The number of minimum cost addition chains for a given n is 
unbounded - but it grows much more slowly than the number of minimum 
length chains; in fact, going out on a limb, I conjecture: 
4. The average number of minimum cost addition chains for the first n 
numbers is bounded. 
...

________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.