A079300 a(n) = number of shortest addition chains ending in n.

1, 1, 1, 1, 2, 2, 5, 1, 3, 4, 15, 3, 10, 14, 4, 1, 2, 7, 33, 6, 29, 40, 4, 4, 14, 24, 5, 23, 132, 12, 77, 1, 2, 4, 43, 12, 39, 92, 20, 8, 23, 84, 4, 69, 14, 8, 220, 5, 12, 36, 4, 38, 205, 16, 156, 32, 173, 352, 37, 24, 91, 233, 87, 1, 2, 4, 23, 6, 29, 134, 1258, 18, 49, 104, 32

Offset: 1

Author

David W. Wilson, Feb 09 2003

Keywords

• nonn

Comments

An addition chain is a finite sequence of whole numbers starting with 1 in which each subsequent term is the sum of two (not necessarily distinct) earlier terms. - Glen Whitney, Nov 08 2021

Examples

			7 has a(7) = 5 shortest addition chains: (1,2,3,4,7), (1,2,3,5,7), (1,2,3,6,7), (1,2,4,5,7), (1,2,4,6,7).
		

Links

• Glen Whitney, Table of n, a(n) for n = 1..18286 (Terms 1..1024 from D. W. Wilson)
• Achim Flammenkamp, Compressed table of a(n) (for all n such that A003313(n) < 23, including all n < 196591)
• Achim Flammenkamp, Shortest addition chains
• Eric Weisstein's World of Mathematics, Addition Chain
• Glen Whitney, C program to compute counts of addition chains

Crossrefs

Cf. A003313, A118386, A118387.

Cf. A079301, A079302, the number of shortest addition chains of Brauer and non-Brauer type, respectively.

Formula

a(n) = A079301(n) + A079302(n). - Glen Whitney, Nov 06 2021

Extensions

More terms from Don Reble, Mar 31 2006

Name edited by Glen Whitney, Nov 08 2021