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

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

Author

Eric W. Weisstein

Keywords

• nonn
• nice
• easy

Comments

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

			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
		

References

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

Links

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

Crossrefs

Bisection of A123087.

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

Programs

Haskell

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

Maple

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

Mathematica

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)))

Python

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

Formula

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)

Extensions

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