A376449 Smallest sum of addition chain for n.

0, 1, 3, 3, 6, 6, 10, 7, 12, 11, 17, 12, 19, 17, 21, 15, 24, 21, 29, 21, 31, 28, 34, 24, 36, 32, 39, 31, 46, 36, 48, 31, 48, 41, 52, 39, 56, 48, 58, 41, 62, 52, 64, 50, 66, 57, 74, 48, 73, 61, 75, 58, 82, 66, 83, 59, 86, 75, 90, 66, 93, 79, 94, 63, 96, 81, 101, 75, 103, 87, 112, 75, 112, 93, 111

Offset

1,3

Comments

There are multiple ways to get a shortest addition chain (A003313), this sequence is the smallest sum of the possible chains.

Links

Roy van Rijn, Table of n, a(n) for n = 1..100

Formula

For n = 2^s, a(n)=s-1

Example

Here are the smallest examples:
1 : 0 []
2 : 1 [1]
3 : 3 [1, 2]
4 : 3 [1, 2]
5 : 6 [1, 2, 3]
6 : 6 [1, 2, 3]
7 : 10 [1, 2, 3, 4]
8 : 7 [1, 2, 4]
9 : 12 [1, 2, 4, 5]
10 : 11 [1, 2, 3, 5]
11 : 17 [1, 2, 3, 5, 6]
12 : 12 [1, 2, 3, 6]
13 : 19 [1, 2, 3, 6, 7]
14 : 17 [1, 2, 3, 4, 7]
15 : 21 [1, 2, 3, 6, 9]
16 : 15 [1, 2, 4, 8]
17 : 24 [1, 2, 4, 8, 9]
18 : 21 [1, 2, 4, 5, 9]
19 : 29 [1, 2, 3, 4, 8, 11]
20 : 21 [1, 2, 3, 5, 10]
... etc

Crossrefs

Cf. A003313

Sequence in context: A290966 A049318 A325861 * A079551 A182843 A358558

Adjacent sequences: A376446 A376447 A376448 * A376450 A376451 A376452

Keyword

nonn

Author

Roy van Rijn, Sep 23 2024

Status

approved