

A050295


Number of strongly triplefree 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 triplefree 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 triplefree subsets of {1,2,...,6k+1} which do not contain 6k+1 and c(6k+1) = Number of strongly triplefree 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 triplefree 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 triplefree. Hence c(6k+1)<=a(6k).
2) c(6k+1)>=a(6k) : Take any strongly triplefree 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 triplefree. 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+r1) 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 triplefree 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 triplefree 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, TripleFree Sets of Integers [From Steven Finch, Apr 20 2019]
Eric Weisstein's World of Mathematics, TripleFree Set.


CROSSREFS

Cf. A050291A050296, 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



