

A349044


NonBrauer numbers.


0



12509, 13207, 13705, 15473, 16537, 20753, 22955, 23219, 23447, 24797, 25018, 26027, 26253, 26391, 26414, 26801, 27401, 27410, 30897, 30946, 31001, 32921, 33065, 33074, 41489, 41506, 43755, 43927, 45867, 46355, 46419, 46797, 46871, 46894, 47761, 49373, 49577, 49593, 49594, 49611, 50036, 50829, 51667
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

A sequence 1=a_0 < a_1 < a_2 < ... < a_l = n is an addition chain (of length l) for n if for each i, 0 < i <= l, there are j_i and k_i such that a_i = a_j_i + a_k_i. Such a chain is called a starchain or Brauer chain if in addition each j_i = i1. A number is a Brauer number if among its shortest addition chains there is a Brauer chain, and nonBrauer otherwise.
The length of a shortest Brauer chain for n is often denoted l^*(n). A003313(n) gives the length of a shortest addition chain for n. Thus n is in this sequence if and only if A003313(n) < l^*(n).
For entries at least through 41506, these numbers satisfy l^*(n) = A003313(n) + 1. It seems likely that larger differences between l^*(n) and A003313(n) occur for later entries in this sequence, but it is unclear whether any n with a larger difference have been found.
These differences between l^*(n) and A003313(n) are highlighted by the following formulation: consider a machine which starts with a 1 in "cache" and can then at each step execute one of two operations: (1) Add any number that has ever been in cache to the current contents of cache, or (2) Restore any number that has previously been in cache to the cache, replacing its prior contents. Then n is in this sequence if and only if there is a shortest program that results in n in cache that includes a "Restore" step. Note further that if there is an entry in this sequence such that l^*(n) > A003313(n)+1, then all shortest programs producing n in cache would contain a "Restore" operation. The definition of A293771 is based on a similar machine with a separate "Store" operation that puts the cache value into "memory," and one could formulate an analogous conjecture here that the "Restore" operation is never necessary for a shortest program. The existence or not of an n in this sequence such that l^*(n) > A003313(n)+1 would settle this question and provide mild evidence one way or the other on the conjecture in A293771.


LINKS

Table of n, a(n) for n=1..43.
Harry Altman, Integer Complexity, Addition Chains, and WellOrdering, Ph.D. thesis, 2014.
Neill Clift, Addition Chains
W. Hansen, Zum ScholzBrauerschen Problem, J. Reine Angew. Math. 202 (1959), 129136.


FORMULA

A079301(n) = 0 if and only if n occurs in this sequence.


EXAMPLE

The shortest starchains for 12509 have length 18; one example is 1,2,3,4,7,11,18,25,43,86,172,344,688,1376,1401,2777,5554,6955,12509. (By inspection, each number in this chain is the sum of the prior number and another number in the sequence, possibly also the prior number.) On the other hand, there are addition chains of length 17 for 12509, e.g., 1,2,4,6,12,13,24,48,96,192,384,768,781,1562,3124,6248,12496,12509. (Here a_5 = a_3+a_3, preventing this from being a starchain.) All numbers smaller than 12509 include a star chain among their shortest addition chains (by exhaustive search). Hence 12509 is the first number in this sequence.


CROSSREFS

Cf. A003313, the length of a shortest addition chain for n.
Cf. A079301, A079302, the number of shortest addition chains for n which are Brauer chains and which are nonBrauer chains, respectively.
Sequence in context: A178278 A335989 A220026 * A231956 A252164 A045217
Adjacent sequences: A349041 A349042 A349043 * A349045 A349046 A349047


KEYWORD

nonn


AUTHOR

Glen Whitney, Nov 06 2021


STATUS

approved



