|
| |
|
|
A172161
|
|
Greedy Coppersmith-Winograd sequence.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
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
|
|
|
LINKS
|
Jon Maiga, Computer-generated formulas for A172161, Sequence Machine.
|
|
|
FORMULA
|
Conjecture: a(n) ~ k*(3 / 2)^n for some k. - Bill McEachen, Dec 02 2022
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
