cp's OEIS Frontend

A050296 Maximum cardinality of a strongly triple-free subset of {1, 2, ..., n}.

%I A050296 #25 Aug 11 2025 10:30:07
%S A050296 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,
%T A050296 17,18,19,20,21,21,22,22,23,23,24,24,25,26,27,27,28,28,29,30,31,31,32,
%U A050296 32,33,33,34,34,35,35,36,36,37,37,38,39,40,41,42,42,43,43,44
%N A050296 Maximum cardinality of a strongly triple-free subset of {1, 2, ..., n}.
%C A050296 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_, Oct 25 2002
%C A050296 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_, Oct 25 2002
%H A050296 Steven R. Finch, <a href="/FinchTriple.html">Triple-Free Sets of Integers</a>. - Steven Finch, Apr 20 2019
%H A050296 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Triple-FreeSet.html">Triple-Free Set</a>.
%e A050296 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. - _Steven Finch_, Feb 26 2009
%t A050296 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}] (* _Steven Finch_, Feb 26 2009 *)
%Y A050296 Cf. A050291-A050295.
%Y A050296 A157282 is the weakly triple-free analog of this sequence. - _Steven Finch_, Feb 26 2009
%K A050296 nonn
%O A050296 1,3
%A A050296 _Eric W. Weisstein_
%E A050296 More terms from _Rob Pratt_, Oct 25 2002