cp's OEIS Frontend

A172161 Greedy Coppersmith-Winograd sequence.

%I A172161 #35 Dec 12 2022 23:03:36
%S A172161 0,1,2,3,4,6,9,13,20,30,45,67,101,151,227,340,510,765,1148,1722,2583,
%T A172161 3874,5811,8717,13075,19613,29419,44129,66193,99290,148935,223402,
%U A172161 335103,502655,753982,1130973,1696460,2544690,3817035,5725552
%N A172161 Greedy Coppersmith-Winograd sequence.
%C A172161 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.
%C A172161 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
%C A172161 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.
%C A172161 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
%C A172161 This sequence is complete: every positive integer is the sum of a subset of its terms. - _Charles R Greathouse IV_, Dec 02 2022
%H A172161 Don Coppersmith and Shmuel Winograd, <a href="https://doi.org/10.1016/S0747-7171(08)80013-2">Matrix multiplication via arithmetic progressions</a>, Journal of Symbolic Computation, 9 (1990) 251-280.
%H A172161 Jon Maiga, Computer-generated formulas for A172161, Sequence Machine.
%F A172161 Conjecture: a(n) ~ k*(3 / 2)^n for some k. - _Bill McEachen_, Dec 02 2022
%F A172161 a(n) = floor((Sum_{i<n} a(i))/2) + 1 for n > 4. - _Charles R Greathouse IV_, Dec 02 2022
%e A172161 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.
%o A172161 (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
%Y A172161 Cf. A120134.
%K A172161 nonn,easy
%O A172161 1,3
%A A172161 _Warren D. Smith_, Jan 27 2010
%E A172161 Two more terms from _Warren D. Smith_, Jan 29 2010
%E A172161 Extended by _Charles R Greathouse IV_, Dec 02 2022