A050291 -id:A050291 - cp's OEIS frontend

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

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

Offset: 1

Eric W. Weisstein

nonn

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

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

			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

Steven R. Finch, Triple-Free Sets of Integers. - Steven Finch, Apr 20 2019
Eric Weisstein's World of Mathematics, Triple-Free Set.

Cf. A050291-A050295.

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

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 *)

More terms from Rob Pratt, Oct 25 2002

A365069 Number of subsets of {1..n} containing n and some element equal to the sum of two or more distinct other elements. A variation of non-binary sum-full subsets without re-usable elements.

Original entry on oeis.org

0, 0, 0, 1, 2, 7, 17, 41, 88, 201, 418, 892, 1838, 3798, 7716, 15740

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365071. The binary case is A364756. Allowing elements to be re-used gives A365070. A version for partitions (but not requiring n) is A237668.

			The subset {2,4,6} has 6 = 4 + 2 so is counted under a(6).
The subset {1,2,4,7} has 7 = 4 + 2 + 1 so is counted under a(7).
The subset {1,4,5,8} has 5 = 4 + 1 so is counted under a(8).
The a(0) = 0 through a(6) = 17 subsets:
  .  .  .  {1,2,3}  {1,3,4}    {1,4,5}      {1,5,6}
                    {1,2,3,4}  {2,3,5}      {2,4,6}
                               {1,2,3,5}    {1,2,3,6}
                               {1,2,4,5}    {1,2,4,6}
                               {1,3,4,5}    {1,2,5,6}
                               {2,3,4,5}    {1,3,4,6}
                               {1,2,3,4,5}  {1,3,5,6}
                                            {1,4,5,6}
                                            {2,3,4,6}
                                            {2,3,5,6}
                                            {2,4,5,6}
                                            {1,2,3,4,6}
                                            {1,2,3,5,6}
                                            {1,2,4,5,6}
                                            {1,3,4,5,6}
                                            {2,3,4,5,6}
                                            {1,2,3,4,5,6}

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The complement w/ re-usable parts is A288728, first differences of A007865.
First differences of A364534.
The binary complement is A364755, first differences of A085489.
The binary version is A364756, first differences of A088809.
The version with re-usable parts is A365070, first differences of A093971.
The complement is counted by A365071, first differences of A151897.
A124506 counts nonnegative combination-free subsets, differences of A326083.
A365046 counts nonnegative combination-full subsets, differences of A364914.
For partitions: A108917, A236912, A237113, A237668, A364532, A364913.
Strict partitions: A116861, A364272, A364349, A364350, A364839, A364916.
Cf. A050291, A326080, A363226, A364346, A364348, A364670.

Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#, {2,Length[#]}]]!={}&]],{n,0,10}]

a(n) = 2^(n-1) - A365070(n).

First differences of A364534.

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Original entry on oeis.org

0, 1, 2, 3, 6, 9, 15, 23, 40, 55, 94, 132, 210, 298, 476, 644, 1038, 1406, 2149, 2965, 4584, 6077, 9426, 12648, 19067, 25739, 38958, 51514, 78459, 104265, 155436, 208329, 312791, 411886, 620780, 823785, 1224414, 1631815, 2437015, 3217077, 4822991

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365069. The binary version is A364755, complement A364756. For re-usable parts we have A288728, complement A365070.

			The subset {1,3,4,6} has 4 = 1 + 3 so is not counted under a(6).
The subset {2,3,4,5,6} has 6 = 2 + 4 and 4 = 1 + 3 so is not counted under a(6).
The a(0) = 0 through a(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {2,3,4}  {1,2,5}  {5,6}
                                 {1,3,5}  {1,2,6}
                                 {2,4,5}  {1,3,6}
                                 {3,4,5}  {1,4,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}
                                          {3,4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..85
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

First differences of A151897.
The version with re-usable parts is A288728 first differences of A007865.
The binary version is A364755, first differences of A085489.
The binary complement is A364756, first differences of A088809.
The complement is counted by A365069, first differences of A364534.
The complement w/ re-usable parts is A365070, first differences of A093971.
A108917 counts knapsack partitions, strict A275972.
A124506 counts combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
Partitions: A236912, A237113, A237668, A364532, A364272, A364349, A364913.
Cf. A050291, A095944, A103580, A324741, A326080, A326117, A341507, A364533.

Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#,{2,Length[#]}]]=={}&]], {n,0,10}]

a(n) + A365069(n) = 2^(n-1).

First differences of A151897.

a(14) onwards added (using A151897) by Andrew Howroyd, Jan 13 2024

A050295 Number of strongly triple-free subsets of {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 3, 5, 8, 16, 24, 48, 76, 132, 198, 396, 588, 1176, 1764, 2940, 4680, 9360, 13680, 27360, 43776, 72960, 109440, 218880, 330240, 660480, 990720, 1693440, 2709504, 5419008, 8128512, 16257024, 25823232, 43038720, 64558080, 129116160, 194365440, 388730880

Offset: 0

Eric W. Weisstein

nonn

A set S is strongly triple-free if x in S implies 2x not in S and 3x not in S.
Conjecture: for k=1,2,3,..., a(6k+1)=2a(6k) and a(6k+5)=2a(6k+4) (these relations hold through a(35)). - John W. Layman, Jun 22 2002
From Pradhan Prashanth Kumar (pradhan.ptr(AT)gmail.com), Feb 03 2008:
The conjecture is true. Proof:
Let b(6k+1) = Number of strongly triple-free subsets of {1,2,...,6k+1} which do not contain 6k+1 and c(6k+1) = Number of strongly triple-free subsets of {1,2,...,6k+1} which contain 6k+1. Now a(6k+1) = b(6k+1) + c(6k+1) and b(6k+1) = a(6k).
1) c(6k+1)<=a(6k) : Take any strongly triple-free subset of {1,2,..,6k+1}, which contains 6k+1 and delete 6k+1. The new set is a subset of {1,2,...,6k} and is trongly triple-free. Hence c(6k+1)<=a(6k).
2) c(6k+1)>=a(6k) : Take any strongly triple-free subset of {1,2,...,6k}. Add 6k+1 to it. Since 6k+1 is not divisible by 2 or 3, this new set is still strongly triple-free. Hence c(6k+1)>=a(6k).
This shows that c(6k+1) = a(6k) and therefore a(6k+1) = b(6k+1)+c(6k+1) = 2a(6k). QED
Another proof for the conjecture: a(6k+r) = 2a(6k+r-1) when r={1,5} (with a(0)=1) would be: Any positive integer of form (6k+1) or (6k+5) is neither divisible by 2 nor by 3. Hence adding the number (6k+1) or (6k+5) to the each strongly triple-free subset of {1, ..., 6k} or {1, ..., 6k+4} does not violate the property and hence we would have 2a(6k) or 2a(6k+4) such subsets for a(6k+1) or a(6k+5). - Ramasamy Chandramouli, Aug 30 2008
A068060 is the weakly triple-free analog of this sequence. - Steven Finch, Mar 02 2009

Alois P. Heinz, Table of n, a(n) for n = 0..75
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Eric Weisstein's World of Mathematics, Triple-Free Set.

Cf. A050291-A050296, A068060.

More terms from John W. Layman, Jun 22 2002

a(0)=1 prepended by Alois P. Heinz, Jan 17 2019

A326115 Number of maximal double-free subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 4, 4, 6, 6, 12, 12, 12, 12, 24, 24, 32, 32, 64, 64, 64, 64, 128, 128, 192, 192, 384, 384, 384, 384, 768, 768, 960, 960, 1920, 1920, 1920, 1920, 3840, 3840, 5760, 5760, 11520, 11520, 11520, 11520, 23040, 23040, 30720, 30720

Offset: 0

Gus Wiseman, Jun 06 2019

nonn

A set is double-free if no element is twice any other element.

			The a(1) = 1 through a(9) = 6 sets:
  {1}  {1}  {13}  {23}   {235}   {235}   {2357}   {13457}  {134579}
       {2}  {23}  {134}  {1345}  {256}   {2567}   {13578}  {135789}
                                 {1345}  {13457}  {14567}  {145679}
                                 {1456}  {14567}  {15678}  {156789}
                                                  {23578}  {235789}
                                                  {25678}  {256789}

Charlie Neder, Table of n, a(n) for n = 0..1000

Cf. A000931, A007865, A050291, A103580, A120641, A308546, A320340, A323092.

Cf. A325865, A326020, A326022, A326083.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],Intersection[#,2*#]=={}&]]],{n,0,10}]

From Charlie Neder, Jun 11 2019: (Start)
a(n) = Product {k < n/2} A000931(8+floor(log_2(n/(2k+1)))).
a(2k+1) = a(2k), a(8k+4) = a(8k+3). (End)

a(16)-a(49) from Charlie Neder, Jun 11 2019

A088810 Number of subsets of {1, ..., n} that are double-free but not sum-free.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 6, 18, 35, 84, 137, 323, 591, 1313, 2033, 4360, 7406, 15581, 23682, 49184, 84017, 171744, 259818, 528784, 853143, 1727011, 2601181, 5243126, 8784832, 17662987, 26541257, 53279330, 86241323, 172871156, 259534578, 519917139

Offset: 0

Reinhard Zumkeller, Oct 19 2003

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..88
Eric Weisstein's World of Mathematics, Double-Free Set
Eric Weisstein's World of Mathematics, Sum-Free Set
Reinhard Zumkeller, Illustration of initial terms

a(n) = A050291(n) - A007865(n) = A088809(n) - A088812(n).

Terms a(28) and beyond from Fausto A. C. Cariboni, Sep 27 2020

A088813 Number of subsets of {1, ..., n} that are double-free or sum-free.

Original entry on oeis.org

1, 2, 4, 7, 14, 26, 43, 79, 137, 246, 398, 733, 1237, 2314, 3586, 6730, 11051, 21096, 31985, 61654, 102730, 199555, 301062, 589746, 942876, 1858881, 2793703, 5524251, 9193512, 18256867, 27396918, 54517922, 88020937, 175434632, 263194662, 525173052

Offset: 0

Reinhard Zumkeller, Oct 19 2003

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..75
Eric Weisstein's World of Mathematics, Double-Free Set
Eric Weisstein's World of Mathematics, Sum-Free Set

a(n) = 2^n - A088812(n) = A050291(n)+A085489(n)-A007865(n).

Terms a(28) and beyond from Fausto A. C. Cariboni, Sep 29 2020

A050293 Number of 3-fold-free subsets of {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 4, 6, 12, 24, 36, 72, 144, 240, 480, 960, 1440, 2880, 5760, 8640, 17280, 34560, 57600, 115200, 230400, 345600, 691200, 1382400, 2073600, 4147200, 8294400, 13271040, 26542080, 53084160, 79626240, 159252480, 318504960, 477757440, 955514880, 1911029760

Offset: 0

Eric W. Weisstein

nonn

A set is 3-fold-free if it does not contain any subset of the form {x, 3x}.

			a(6) = 36. There are 64 subsets of {1, 2, 3, 4, 5, 6}. We exclude the 16 that contain {1, 3} and the 16 that contain {2, 6}. We've double-counted the 4 that contain {1, 2, 3, 6}. This yields 64 - 16 - 16 + 4 = 36.

B. Reznick and R. Holzsager, r-fold free sets of positive integers, Math. Magazine 68 (1995) 71-72.

Alois P. Heinz, Table of n, a(n) for n = 0..3789
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Eric Weisstein's World of Mathematics, Triple-Free Set.

Cf. A050291-A050296, A068060.

More terms from David Wasserman, Feb 14 2002
Corrected and edited by Steven Finch, Feb 25 2009
a(0)=1 prepended by Alois P. Heinz, Jan 16 2019

A050294 Maximum cardinality of a 3-fold-free subset of {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 9, 9, 10, 11, 11, 12, 13, 14, 15, 16, 16, 17, 18, 18, 19, 20, 20, 21, 22, 22, 23, 24, 24, 25, 26, 27, 28, 29, 29, 30, 31, 31, 32, 33, 34, 35, 36, 36, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 44, 44, 45, 46, 47, 48, 49, 49, 50, 51, 51, 52, 53, 54, 55

Offset: 1

Eric W. Weisstein

nonn

For a given r>1, a set is r-fold-free if it does not contain any subset of the form {x, r*x}.
If r is in A050376, then an r-fold-free set with the highest cardinality is obtained by removing from {1,...,n} all numbers for which r is an infinitary divisor (for the definition of the infinitary divisor of n, see comment to A037445). In general, an r-fold-free set with the highest cardinality is obtained by removing from {1,...,n} all numbers for which r is an oex divisor (for the definition of the oex divisor of n, see A186643). - Vladimir Shevelev Feb 22 2011 and Feb 28 2011.
Equals A051068 shifted by 1. - Michel Dekking, Feb 18 2019

			a(26)=26-a(floor(26/3))=26-a(8)=26-6=20.

Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Bruce Reznick, Problem 1440, Mathematics Magazine, Vol. 67 (1994).
B. Reznick and R. Holzsager, r-fold free sets of positive integers, Math. Magazine 68 (1995) 71-72.
Eric Weisstein's World of Mathematics, Triple-Free Set.

Cf. A050291-A050296.

a(n)=if(n==0,0,n-a(floor(n/3))); \\ Joerg Arndt, Apr 27 2013

Take r = 3 in a(n) = (r n + sum [k = 0 to m] (-1)^k b(k)) / (r + 1), where [b(m) b(m-1) ... b(0)] is the base-r representation of n. - Rob Pratt, Apr 21 2004

Take r=3 in a(n) = n-a(floor(n/r)); a(n)=n-floor(n/r)+floor(n/r^2)-floor(n/r^3)+... [Vladimir Shevelev, Feb 22 2011].

More terms from John W. Layman, Oct 25 2002

Corrected and edited by Steven Finch, Feb 25 2009

A358392 Number of nonempty subsets of {1, 2, ..., n} with GCD equal to 1 and containing the sum of any two elements whenever it is at most n.

Original entry on oeis.org

1, 1, 2, 3, 7, 9, 19, 27, 46, 63, 113, 148, 253, 345, 539, 734, 1198, 1580, 2540, 3417, 5233, 7095, 11190, 14720, 22988, 31057, 47168, 63331, 98233, 129836, 200689, 269165, 406504, 546700, 838766, 1108583, 1700025, 2281517, 3437422, 4597833, 7023543, 9308824, 14198257, 18982014, 28556962

Offset: 1

Max Alekseyev, Nov 13 2022

nonn

Also, the number of distinct numerical semigroups that are generated by some subset of {1, 2, ..., n} and have a finite complement in the positive integers.

Max Alekseyev, Table of n, a(n) for n = 1..100
Marcel K. Goh et al., Counting numerical semigroups by largest element of minimal generating set, MathOverflow, 2022.

Inverse Moebius transform of A103580.

Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546, A326020, A326076, A326080, A326083, A326114.

a(n) = Sum_{k=1..n} moebius(k) * A103580(floor(n/k)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A365069 Number of subsets of {1..n} containing n and some element equal to the sum of two or more distinct other elements. A variation of non-binary sum-full subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A050295 Number of strongly triple-free subsets of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A326115 Number of maximal double-free subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A088810 Number of subsets of {1, ..., n} that are double-free but not sum-free.

Views

Author

Keywords

Links

Formula

Extensions

A088813 Number of subsets of {1, ..., n} that are double-free or sum-free.

Views

Author

Keywords

Links

Formula

Extensions

A050293 Number of 3-fold-free subsets of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A050294 Maximum cardinality of a 3-fold-free subset of {1, 2, ..., n}.