|
Search: id:A050296
|
|
|
| A050296 |
|
Maximum cardinality of a strongly triple-free subset of {1, 2, ..., n}. |
|
+0
6
|
|
| 1, 1, 2, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 10, 11, 11, 12, 12, 13, 13, 14, 15, 16, 16, 16, 16, 17, 18, 19, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 26, 27, 27, 28, 28, 29, 30, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 39, 40, 41, 42, 42, 43, 43, 44
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Computed using the following integer programming formulation, where the decision variable x[i] is 1 if i is a member of the strongly triple-free subset, 0 otherwise. Maximize sum {i in 1..n} x[i] subject to x[i] + x[3i] <= 1 for i in 1..n such that 3i in 1..n, x[i] + x[2i] <= 1 for i in 1..n such that 2i in 1..n, x[i] in {0,1} for i in 1..n. - Rob Pratt.
The problem can also be thought of as finding a maximum independent set in a graph with nodes 1..n and edges of the form (i,3i) and (i,2i). - Rob Pratt.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
CROSSREFS
|
Cf. A050291-A050295.
Sequence in context: A085972 A136378 A099249 this_sequence A057062 A065855 A034137
Adjacent sequences: A050293 A050294 A050295 this_sequence A050297 A050298 A050299
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Eric Weisstein (eric(AT)weisstein.com)
|
|
EXTENSIONS
|
More terms from Rob Pratt (Rob.Pratt(AT)sas.com), Oct 25 2002
|
|
|
Search completed in 0.002 seconds
|
