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

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

Author

Eric W. Weisstein

Keywords

• nonn

Comments

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

Links

• 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.

Crossrefs

Cf. A050291-A050296, A068060.

Extensions

More terms from John W. Layman, Jun 22 2002

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