A172161 Greedy Coppersmith-Winograd sequence.

0, 1, 2, 3, 4, 6, 9, 13, 20, 30, 45, 67, 101, 151, 227, 340, 510, 765, 1148, 1722, 2583, 3874, 5811, 8717, 13075, 19613, 29419, 44129, 66193, 99290, 148935, 223402, 335103, 502655, 753982, 1130973, 1696460, 2544690, 3817035, 5725552

Offset: 1

Author

Warren D. Smith, Jan 27 2010

Keywords

• nonn
• easy

Comments

Coppersmith & Winograd asked for dense sets S of integers such that if A,B,C are three disjoint subsets of S, their sums are cannot all be equal. Such sets yield new matrix multiplication algorithms. This is the "greedy sequence" obeying this property, that is, we start with S = {0, 1} and adjoin new integers one at a time, always adjoining the least new integer such that the Coppersmith-Winograd property remains valid. It looks as though each term is approximately 1.5 times the preceding term. The sequence is clearly infinite because each term is no greater than the sum of all previous terms.

Amazingly, this sequence appears to agree with McRae's sequence A120134 after the "3". (This probably can be proved, but I haven't yet.) - Warren D. Smith, Jan 29 2010

Considering the A120134 tie-in comment, via the Maiga link, its alternate algorithm generates both a(n) and A120134(m) for n >= 1 and m >= 1.

That algorithm applies b(0)=2, b(1)=2, b(2)=3, b(3)=5, b(4)=8 then b(n) = floor(3*b(n-1)/2). Then a(n) = first differences of b(n), while A120134(m) begins from b(5) - b(4). - Bill McEachen, Dec 02 2022

This sequence is complete: every positive integer is the sum of a subset of its terms. - Charles R Greathouse IV, Dec 02 2022

Examples

			For a(6), if 5 were chosen, the sets {1, 4}, {2,3}, and {5} would all have the same sum. Clearly a(6) = 6 works because 0+1+2+3+4 = 10 < 2*6.
		

Links

• Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, 9 (1990) 251-280.
• Jon Maiga, Computer-generated formulas for A172161, Sequence Machine.

Crossrefs

Cf. A120134.

Programs

PARI

first(n)=if(n<6, return([0..n-1])); my(v=vector(n),s=3); v[2]=1; v[3]=2; v[4]=3; for(i=5,n, v[i]=(s+=v[i-1])\2+1); v \\ Charles R Greathouse IV, Dec 02 2022

Formula

Conjecture: a(n) ~ k*(3 / 2)^n for some k. - Bill McEachen, Dec 02 2022

a(n) = floor((Sum_{i 4. - Charles R Greathouse IV, Dec 02 2022

Extensions

Two more terms from Warren D. Smith, Jan 29 2010

Extended by Charles R Greathouse IV, Dec 02 2022