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!)
A050295 Number of strongly triple-free subsets of {1, 2, ..., n}. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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.

Sequence in context: A192571 A215525 A192645 * A121649 A306622 A030034

Adjacent sequences:  A050292 A050293 A050294 * A050296 A050297 A050298

KEYWORD

nonn

AUTHOR

Eric W. Weisstein

EXTENSIONS

More terms from John W. Layman, Jun 22 2002

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

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 July 24 23:25 EDT 2021. Contains 346273 sequences. (Running on oeis4.)