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

Offset

1,19

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.

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

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.

Crossrefs

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

Sequence in context: A080300 A116864 A255308 * A138806 A181105 A142971

Adjacent sequences: A079299 A079300 A079301 * A079303 A079304 A079305

Keyword

nonn

Author

David W. Wilson, Feb 09 2003

Extensions

Definition disambiguated by Glen Whitney, Nov 06 2021

Status

approved