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

Author

Roy van Rijn, Sep 23 2024

Keywords

• nonn

Comments

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

Examples

			Here are the smallest examples:
   n : a(n)
   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]
  ...
		

Links

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

Crossrefs

Cf. A003313, A008057.

Formula

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

For odd n, a(n) = A008057((n-1)/2) - n + 1. - Pontus von Brömssen, Apr 22 2025