A079301 a(n) = number of shortest addition chains for n that are Brauer chains.

1, 1, 1, 1, 2, 2, 5, 1, 3, 4, 15, 3, 9, 14, 4, 1, 2, 7, 31, 6, 26, 40, 4, 4, 13, 22, 5, 23, 114, 12, 64, 1, 2, 4, 43, 12, 33, 87, 18, 8, 20, 78, 4, 69, 14, 8, 183, 5, 11, 34, 4, 35, 171, 16, 139, 32, 148

Offset

1,5

Comments

In a general addition chain, each element > 1 is a sum of two previous elements. In a Brauer chain, each element > 1 is a sum of the immediately previous element and another previous element.

Links

Glen Whitney, Table of n, a(n) for n = 1..18286 (Terms 1..1024 from D. W. Wilson)

Eric Weisstein's World of Mathematics, Brauer Chain

Glen Whitney, C program to compute A079300, also generates this sequence.

Example

All five of the shortest addition chains for 7 are Brauer 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). Hence a(7) = 5.
13 has ten shortest addition chains: (1,2,3,5,8,13), (1,2,3,5,10,13), (1,2,3,6,7,13), (1,2,3,6,12,13), (1,2,4,5,9,13), (1,2,4,6,7,13), (1,2,4,6,12,13), (1,2,4,8,9,13), (1,2,4,8,12,13), and (1,2,4,5,8,13). Of these, all but the last are Brauer chains. Hence a(13) = 9.
12509 has 28 shortest addition chains, none of which are Brauer chains. Hence a(12509) = 0.

Crossrefs

Sequence in context: A173169 A016586 A073690 * A079300 A128932 A286150

Adjacent sequences: A079298 A079299 A079300 * A079302 A079303 A079304

Keyword

nonn

Author

David W. Wilson, Feb 09 2003

Extensions

Definition disambiguated by Glen Whitney, Nov 06 2021

Status

approved