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,5

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

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

Formula

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

Example

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).

Crossrefs

Cf. A003313, A118386, A118387.

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

Sequence in context: A016586 A073690 A079301 * A128932 A286150 A071950

Adjacent sequences: A079297 A079298 A079299 * A079301 A079302 A079303

Keyword

nonn

Author

David W. Wilson, Feb 09 2003

Extensions

More terms from Don Reble, Mar 31 2006

Name edited by Glen Whitney, Nov 08 2021

Status

approved