A349044 Non-Brauer numbers.

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

Offset: 1

Author

Glen Whitney, Nov 06 2021

Keywords

• nonn

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 star-chain or Brauer chain if in addition each j_i = i-1. A number is a Brauer number if among its shortest addition chains there is a Brauer chain, and non-Brauer 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.

Examples

			The shortest star-chains 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 star-chain.) 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.
		

Links

• Harry Altman, Integer Complexity, Addition Chains, and Well-Ordering, Ph.D. thesis, 2014.
• Neill Clift, Addition Chains
• W. Hansen, Zum Scholz-Brauerschen Problem, J. Reine Angew. Math. 202 (1959), 129-136.

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 non-Brauer chains, respectively.

Formula

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