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

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,2

Comments

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.

From Vladimir Shevelev (2011) (Start):

we know a formula for this: a(n) = n-a(floor(n/3)). This gives that the sequence of first differences Db:=(a(n+1)-a(n)) of a satisfies Db(3m+1) = Db(3m+2) = 1, and Db(3m+3) = 1 - Db(m). This implies that Db = x, the fixed point of 0->111, 1->110.

(End)

From Michel Dekking, Feb 18 2019 (Start):

This equals the partial sums of A014578. To see this, it suffices to prove that the two sequences of first differences Da and Db of the partial sums and this are equal. Clearly the sequence Da of first differences of a is the sequence A014578. According to Philippe Deléham (2004), Da equals 0x = 0110110111110..., where x is the fixed point of the morphism 0->111, 1->110.

(End)

Links

Table of n, a(n) for n=1..73.

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.

Formula

a(3^n) = A015518(n+1) = -(-1)^n*A014983(n+1). - Philippe Deléham, Mar 31 2004

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

Example

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

Prog

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

Crossrefs

Cf. A050291-A050296.

Sequence in context: A175268 A241948 A051068 * A349775 A369870 A097950

Adjacent sequences: A050291 A050292 A050293 * A050295 A050296 A050297

Keyword

nonn,changed

Author

Eric W. Weisstein

Extensions

More terms from John W. Layman, Oct 25 2002

Corrected and edited by Steven Finch, Feb 25 2009

Status

approved