Linear cost addition chains (somewhat long)

Wed Jan 3 22:46:34 CET 2007

What is the minimum cost addition chain for n, where the cost is the 
sum of the numbers in the addition chain?

It wouldn't surprise me if somebody has already looked at this problem, 
but the primary sequence is not in the OEIS, nor are any of the obvious 
variants.

There is a vaguely related sequence in the database, A005766, where the 
cost of generating i+j is i*j, but this proves amenable to a simple 
strategy: if n is even, generate the chain for n/2 and append n; if n 
is odd, generate the chain for (n-1)/2 and append (n+1)/2 and n.  No 
such simple strategy appears to be possible here.

This is might actually be a realistic problem in some contexts.  There 
are numerous contexts where the size of x^n is proportional to n, and 
the optimal multiplication algorithm for large values is proportional 
to n.  However, in the cases I know of, the multiplication algorithm is 
of the form "transform the inputs, perform a simple component-wise 
operation on the results, and transform back".  For such an algorithm, 
it will be faster to exponentiate by transforming, performing the 
component-wise operation for the exponentiation, and transforming back.

Here are optimal solutions for n = 1 to 64.  The first column is n, 
second is the minimum sum for an addition chain, and following are all 
addition chains with the minimum sum:

 1   1  1
 2   3  1 2
 3   6  1 2 3
 4   7  1 2 4
 5  11  1 2 3 5
 6  12  1 2 3 6
 7  17  1 2 3 4 7
 8  15  1 2 4 8
 9  21  1 2 3 6 9, 1 2 4 5 9
10  21  1 2 3 5 10
11  28  1 2 3 4 7 11, 1 2 3 5 6 11
12  24  1 2 3 6 12
13  32  1 2 3 5 8 13, 1 2 3 6 7 13
14  31  1 2 3 4 7 14
15  36  1 2 3 5 10 15, 1 2 3 6 9 15
16  31  1 2 4 8 16
17  41  1 2 4 8 9 17
18  39  1 2 3 6 9 18, 1 2 4 5 9 18
19  48  1 2 3 4 8 11 19
20  41  1 2 3 5 10 20
21  52  1 2 3 4 7 14 21
22  50  1 2 3 4 7 11 22, 1 2 3 5 6 11 22
23  57  1 2 3 5 10 13 23
24  48  1 2 3 6 12 24
25  61  1 2 3 5 10 15 25
26  58  1 2 3 5 8 13 26, 1 2 3 6 7 13 26
27  66  1 2 3 6 9 18 27, 1 2 4 5 9 18 27, 1 2 3 6 12 15 27
28  59  1 2 3 4 7 14 28
29  75  1 2 3 4 7 14 15 29, 1 2 3 4 7 11 18 29
30  66  1 2 3 5 10 15 30, 1 2 3 6 9 15 30
31  81  1 2 3 5 8 13 18 31
32  63  1 2 4 8 16 32
33  81  1 2 4 8 16 17 33
34  75  1 2 4 8 9 17 34
35  87  1 2 3 4 7 14 21 35
36  75  1 2 3 6 9 18 36, 1 2 4 5 9 18 36
37  94  1 2 4 5 8 16 21 37
38  86  1 2 3 4 8 11 19 38
39  97  1 2 3 5 8 13 26 39, 1 2 3 6 7 13 26 39
40  81  1 2 3 5 10 20 40
41 103  1 2 3 5 10 20 21 42, 1 2 4 5 9 18 23 41
42  94  1 2 3 4 7 14 21 42
43 107 1 2 3 5 10 20 23 43
44  94  1 2 3 4 7 11 22 44, 1 2 3 5 6 11 22 44
45 111 1 2 3 5 10 15 30 45, 1 2 3 6 9 15 30 45, 1 2 3 6 9 18 27 45, 1 2 
4 5 9 18 27 45, 1 2 3 6 12 15 27 45
46 103  1 2 3 5 10 13 23 46
47 122  1 2 3 5 7 10 20 27 47, 1 2 3 4 7 11 22 25 47, 1 2 3 5 6 11 22 
25 47
48  96  1 2 3 6 12 24 48
49 122  1 2 3 6 12 24 25 49
50 111 1 2 3 5 10 15 25 50
51 126  1 2 4 8 9 17 34 51, 1 2 3 6 12 24 27 51
52 110  1 2 3 5 8 13 26 52, 1 2 3 6 7 13 26 52
53 135  1 2 3 5 6 12 24 29 53
54 120  1 2 3 6 9 18 27 54, 1 2 4 5 9 18 27 54, 1 2 3 6 12 15 27 54
55 138  1 2 3 4 7 11 22 33 55, 1 2 3 5 6 11 22 33 55
56 115  1 2 3 4 7 14 28 56
57 143  1 2 3 4 8 19 38 57
58 133  1 2 3 4 7 14 15 29 58, 1 2 3 4 7 11 18 29 58
59 149  1 2 3 4 7 14 28 31 59
60 126  1 2 3 5 10 15 30 60, 1 2 3 6 9 15 30 60
61 154  1 2 3 5 7 14 28 33 61
62 143  1 2 3 5 8 13 18 31 62
63 157  1 2 3 4 7 14 21 42 63, 1 2 3 4 7 14 28 35 63
64 127  1 2 4 8 16 32 64

These are done by hand, so there may be errors.  Verification and 
extension would be appreciated.

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.

Note that one of conjectures 1 and 2 must hold, unless both have many 
ties, since there are cases where n and 2n have the same length minimum 
length addition chain.

Franklin T. Adams-Watters

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

Someone recently gave me a random programming problem: to find the 
number of unique
values of an infix expression (like say 1+2-3*4) parenthesized in all 
possible ways
(in this example it's three: {-9 -3 0} because of the five ways two 
produce duplicate
results).  The operators were restricted to {+ - *}, the operands to 
positive integers.

Somewhat arbitrary, but a fun puzzle...

Anyway, I was wondering: is there a method for constructing such 
expressions such
that over parenthesization they give the maximum possible Catalan(N) 
unique values?

What is the maximum achievable if the operators are restricted to {+ 
*} or {- *}?

Perhaps there are also interesting puzzles with restrictions on the 
operands, such
as when they are all the same value, or powers of two, or the like...