A079302 a(n) = number of shortest addition chains for n that are non-Brauer chains.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 3, 0, 0, 0, 1, 2, 0, 0, 18, 0, 13, 0, 0, 0, 0, 0, 6, 5, 2, 0, 3, 6, 0, 0, 0, 0, 37, 0, 1, 2, 0, 3, 34, 0, 17, 0, 25, 44, 4, 0, 15, 32, 7, 0, 0, 0, 0, 0, 3, 0, 244, 0, 7, 13, 2, 8, 0, 6, 129, 0, 3, 6

Offset: 1

Author

David W. Wilson, Feb 09 2003

Keywords

• nonn

Comments

In a general addition chain, each element > 1 is a sum of two previous elements (the two may be the same element). In a Brauer chain, each element > 1 is a sum of the immediately previous element and another previous element. Conversely, a non-Brauer chain has at least one element that is the sum of two elements earlier than the preceding one.

Examples

			7 has five shortest addition chains: (1,2,3,4,7), (1,2,3,5,7), (1,2,3,6,7), (1,2,4,5,7), and (1,2,4,6,7). All of these are Brauer chains. Hence a(7) = 0.
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, only the last is non-Brauer. Hence a(13) = 1.
12509 has 28 shortest addition chains, all of which happen to be non-Brauer (in fact, it is the smallest natural number for which all shortest addition chains are non-Brauer). Hence a(12509) = A079300(12509) = 28.
		

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.

Crossrefs

Cf. A079300, the total number of minimal addition chains.

Extensions

Definition disambiguated by Glen Whitney, Nov 06 2021