A050296 -id:A050296 - cp's OEIS frontend

A050291 Number of double-free subsets of {1, 2, ..., n}.

1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 288, 576, 960, 1920, 2880, 5760, 9360, 18720, 28080, 56160, 93600, 187200, 280800, 561600, 898560, 1797120, 2695680, 5391360, 8985600, 17971200, 26956800, 53913600, 87091200, 174182400, 261273600, 522547200, 870912000

Offset: 0

Eric W. Weisstein

A set is double-free if it does not contain both x and 2x.

So these are equally "half-free" subsets. - Gus Wiseman, Jul 08 2019

			From _Gus Wiseman_, Jul 08 2019: (Start)
The a(0) = 1 through a(5) = 20 double-free subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {1,3}  {4}      {4}
                {2,3}  {1,3}    {5}
                       {1,4}    {1,3}
                       {2,3}    {1,4}
                       {3,4}    {1,5}
                       {1,3,4}  {2,3}
                                {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {1,3,4}
                                {1,3,5}
                                {1,4,5}
                                {2,3,5}
                                {3,4,5}
                                {1,3,4,5}
(End)

Wang, E. T. H. ``On Double-Free Sets of Integers.'' Ars Combin. 28, 97-100, 1989.

Alois P. Heinz, Table of n, a(n) for n = 0..4030 (terms n = 1..400 from T. D. Noe)
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Eric Weisstein's World of Mathematics, Double-Free Set.

Cf. A000045, A007814, A050292-A050296.

Cf. A007865, A103580, A120641, A308546, A320340, A323092, A326083, A326115.

a:= proc(n) option remember; `if`(n=0, 1, (F-> (p-> a(n-1)*F(p+3)
      /F(p+2))(padic[ordp](n, 2)))(j-> (<<0|1>, <1|1>>^j)[1, 2]))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 16 2019

a[n_] := a[n] = (b = IntegerExponent[2n, 2]; a[n-1]*Fibonacci[b+2]/Fibonacci[b+1]); a[1]=2; Table[a[n], {n, 1, 34}] (* Jean-François Alcover, Oct 10 2012, from first formula *)
Table[Length[Select[Subsets[Range[n]],Intersection[#,#/2]=={}&]],{n,0,10}] (* Gus Wiseman, Jul 08 2019 *)

first(n)=my(v=vector(n)); v[1]=2; for(k=2,n, v[k]=v[k-1]*fibonacci(valuation(k,2)+3)/fibonacci(valuation(k,2)+2)); v \\ Charles R Greathouse IV, Feb 07 2017

a(n) = a(n-1)*Fibonacci(b(2n)+2)/Fibonacci(b(2n)+1), Fibonacci = A000045, b = A007814.

a(n) = 2^n - A088808(n). - Reinhard Zumkeller, Oct 19 2003

Extended with formula by Christian G. Bower, Sep 15 1999

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

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Original entry on oeis.org

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

Offset: 0

Eric W. Weisstein

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.
Least k such that a(k)=n is equal to A003159(n).
To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004
Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011
Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013

			Examples for n = 1 through 8: {1}, {1}, {1,3}, {1,3,4}, {1,3,4,5}, {1,3,4,5}, {1,3,4,5,7}, {1,3,4,5,7}.
Binary expansion of 5 is 101, so Sum{i>=0} b_i*(-1)^i = 2. Therefore a(5) = 10/3 + 2/3 = 4. - _Vladimir Shevelev_, Apr 15 2010

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Double-Free Set.

Bisection of A123087.

Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.

a050292 n = a050292_list !! (n-1)
a050292_list = scanl (+) 0 a035263_list
-- Reinhard Zumkeller, Jan 21 2013

A050292:=n->add((-1)^k*floor(n/2^k), k=0..n); seq(A050292(n), n=0..100); # Wesley Ivan Hurt, Feb 14 2014

a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* Harvey P. Dale, Apr 29 2018 *)

PARI
```
a(n)=if(n<2,1,n-a(floor(n/2)))
```

from sympy.ntheory import digits
def A050292(n): return ((n<<1)+sum((0,1,-1,0)[i] for i in digits(n,4)[1:]))//3 # Chai Wah Wu, Jan 30 2025

Partial sums of A035263. Close to (2/3)*n.
a(n) = A123087(2*n) = n - A123087(n). - Max Alekseyev, Mar 05 2023
From Benoit Cloitre, Nov 24 2002: (Start)
a(1)=1, a(n) = n - a(floor(n/2));
a(n) = (2/3)*n + (1/3)*A065359(n);
more generally, for m>=0, a(2^m*n) - 2^m*a(n) = A001045(m)*A065359(n) where A001045(m) = (2^m - (-1)^m)/3 is the Jacobsthal sequence;
a(A039004(n)) = (2/3)*A039004(n);
a(2*A039004(n)) = 2*a(A039004(n));
a(A003159(n)) = n;
a(A003159(n)-1) = n-1;
a(n) mod 2 = A010060(n) the Thue-Morse sequence;
a(n+1) - a(n) = A035263(n+1);
a(n+2) - a(n) = abs(A029884(n)).
(End)
G.f.: (1/(x-1)) * Sum_{i>=0} (-1)^i*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - Benoit Cloitre, Jun 03 2003
a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - Philippe Deléham, Mar 26 2004
a(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
If n = Sum_{i>=0} b_i*2^i is the binary expansion of n, then a(n) = 2n/3 + (1/3)Sum_{i>=0} b_i*(-1)^i. Thus a(n) = 2n/3 + O(log(n)). - Vladimir Shevelev, Apr 15 2010
Moreover, the equation a(3m)=2m has infinitely many solutions, e.g., a(3*2^k)=2*2^k; on the other hand, a((4^k-1)/3)=(2*(4^k-1))/9+k/3, i.e., limsup |a(n)-2n/3| = infinity. - Vladimir Shevelev, Feb 23 2011
a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - Philippe Deléham, Oct 19 2011
From Peter Bala, Feb 02 2013: (Start)
Product_{n >= 1} (1 + x^((2^n - (-1)^n)/3 )) = (1 + x)^2(1 + x^3)(1 + x^5)(1 + x^11)(1 + x^21)... = 1 + sum {n >= 1} x^a(n) = 1 + 2x + x^2 + x^3 + 2x^4 + 2x^5 + .... Hence this sequence lists the numbers representable as a sum of distinct Jacobsthal numbers A001045 = [1, 1', 3, 5, 11, 21, ...], where we distinguish between the two occurrences of 1 by writing them as 1 and 1'. For example, 9 occurs twice in the present sequence because 9 = 5 + 3 + 1 and 9 = 5 + 3 + 1'. Cf. A197911 and A080277. See also A120385.
(End)

Extended with formula by Christian G. Bower, Sep 15 1999
Corrected and extended by Reinhard Zumkeller, Aug 16 2006
Extended with formula by Philippe Deléham, Oct 19 2011
Entry revised to give a simpler definition by N. J. A. Sloane, Jan 03 2014

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

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

A086316 Decimal expansion of estimate of the strongly triple-free set constant.

Original entry on oeis.org

6, 1, 3, 4, 7, 5, 2, 6, 9, 2, 0, 2, 2, 3, 4, 4, 1, 6, 0, 1, 8, 0, 4, 1, 6, 6, 3, 8

Offset: 0

Eric W. Weisstein, Jul 15 2003

			0.613475269...
0.6134752692022344160180416638... - _Steven Finch_, Feb 25 2009

Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Julien Cassaigne and Paul Zimmermann, Numerical Evaluation of the Strongly Triple-Free Constant (1996). [From _Steven Finch_, Feb 25 2009]
Julien Cassaigne and Paul Zimmermann, Numerical Evaluation of the Strongly Triple-Free Constant (pdf file, 1996).
Eric Weisstein's World of Mathematics, Triple-Free Set

Cf. A050295, A050296.

f[k_,n_]:=1+Floor[FullSimplify[Log[n/3^k]/Log[2]]]; g[n_]:=Floor[FullSimplify[Log[n]/Log[3]]]; peven[n_]:=Sum[Quotient[f[k,n]+Mod[k+1,2],2],{k,0,g[n]}]; podd[n_]:=Sum[Quotient[f[k,n]+Mod[k,2],2],{k,0,g[n]}]; p[n_]:=Max[peven[n],podd[n]]; v[1]=1;j=1;k=1;n=4001; For[k=2,k=n,k++,If[2*v[k-j]<3^j,v[k]=2*v[k-j],{v[k]=3^j,j++}]]; Sum[p[v[n]]*(1/v[n]-1/v[n+1]),{n,1,4000}]/3 (* Steven Finch, Feb 25 2009 *)

More terms from Steven Finch, Feb 25 2009

A157282 Maximum cardinality of a weakly triple-free subset of {1, 2, ..., n}.

Original entry on oeis.org

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

Offset: 1

Steven Finch, Feb 26 2009

nonn

A050294 is different from this sequence. A050294 involves sets encompassing no {x,3x}; this sequence involves sets encompassing no {x,2x,3x}.
From Steven Finch, Feb 27 2009: (Start)
Define d(n)=A003586(n), b(0)=0 and b(k)=A057561(n) for d(n) <= k < d(n+1).
Then a(n) = Sum_{m=1..ceiling(n/3)} b(floor(n/e(m))) where e(m) = A007310(m). (End)

			a(9)=7 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 upper triangles are removed by marking 2, 3.

Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]

A050296 is the strongly triple-free analog of this sequence.

Cf. A003586, A007310, A057561.

More terms from Steven Finch, Feb 27 2009

cp's OEIS Frontend

A050291 Number of double-free subsets of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A086316 Decimal expansion of estimate of the strongly triple-free set constant.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A157282 Maximum cardinality of a weakly triple-free subset of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

Links