login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A050296 Maximum cardinality of a strongly triple-free subset of {1, 2, ..., n}. 7
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; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

Table of n, a(n) for n=1..71.

Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]

Eric Weisstein's World of Mathematics, Free Set.

EXAMPLE

a(9)=6 since there are three grid graphs, two with a single vertex {7}, {5} and the other with rows {1,3,9}, {2,6}, {4}, {8}. The adjacencies are eliminated by marking 2, 3, 8. [From Steven Finch, Feb 26 2009]

MATHEMATICA

e[m_]:=(6*m+(-1)^m-3)/2 f[k_, n_, m_]:=1+Floor[FullSimplify[Log[n/3^k/e[m]]/Log[2]]] g[n_, m_]:=Floor[FullSimplify[Log[n/e[m]]/Log[3]]] peven[n_, m_]:=Sum[Quotient[f[k, n, m]+Mod[k+1, 2], 2], {k, 0, g[n, m]}] podd[n_, m_]:=Sum[Quotient[f[k, n, m]+Mod[k, 2], 2], {k, 0, g[n, m]}] p[n_]:=Sum[Max[peven[n, m], podd[n, m]], {m, 1, Ceiling[n/3]}] Table[p[n], {n, 1, 71}] [From Steven Finch, Feb 26 2009]

CROSSREFS

Cf. A050291-A050295.

A157282 is the weakly triple-free analog of this sequence. [From Steven Finch, Feb 26 2009]

Sequence in context: A344374 A305557 A099249 * A057062 A283993 A255572

Adjacent sequences:  A050293 A050294 A050295 * A050297 A050298 A050299

KEYWORD

nonn

AUTHOR

Eric W. Weisstein

EXTENSIONS

More terms from Rob Pratt, Oct 25 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 1 07:45 EDT 2021. Contains 346384 sequences. (Running on oeis4.)