login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0). 22

%I #87 Mar 05 2023 11:30:13

%S 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,

%T 19,20,20,21,21,22,22,23,24,25,25,26,26,27,27,28,29,30,30,31,32,33,33,

%U 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

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

%C Note that the first equation implies a(0)=0, so there is no need to specify an initial value.

%C 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.

%C Least k such that a(k)=n is equal to A003159(n).

%C 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

%C 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

%C Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - _Vladimir Shevelev_, Apr 16 2010

%C 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

%C 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

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.

%D Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

%H Reinhard Zumkeller, <a href="/A050292/b050292.txt">Table of n, a(n) for n = 0..10000</a>

%H Steven R. Finch, <a href="/FinchTriple.html">Triple-Free Sets of Integers</a> [From Steven Finch, Apr 20 2019]

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Double-FreeSet.html">Double-Free Set</a>.

%F Partial sums of A035263. Close to (2/3)*n.

%F a(n) = A123087(2*n) = n - A123087(n). - _Max Alekseyev_, Mar 05 2023

%F From _Benoit Cloitre_, Nov 24 2002: (Start)

%F a(1)=1, a(n) = n - a(floor(n/2));

%F a(n) = (2/3)*n + (1/3)*A065359(n);

%F 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;

%F a(A039004(n)) = (2/3)*A039004(n);

%F a(2*A039004(n)) = 2*a(A039004(n));

%F a(A003159(n)) = n;

%F a(A003159(n)-1) = n-1;

%F a(n) mod 2 = A010060(n) the Thue-Morse sequence;

%F a(n+1) - a(n) = A035263(n+1);

%F a(n+2) - a(n) = abs(A029884(n)).

%F (End)

%F G.f.: Sum_{k=0..oo} a(n)*x^n = (1/(x-1)) * Sum_{i=0..oo} (-1)^i*x^(2^i)/(x^(2^i)-1) ). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003

%F a(n) = Sum_{k=>0} (-1)^k*floor(n/2^k), - _Benoit Cloitre_, Jun 03 2003

%F a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - _Philippe Deléham_, Mar 26 2004

%F a(2^n) = (2^(n+1) + (-1)^n)/3. - _Vladimir Shevelev_, Apr 15 2010

%F 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

%F 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

%F a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - _Philippe Deléham_, Oct 19 2011

%F From _Peter Bala_, Feb 02 2013: (Start)

%F 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.

%F (End)

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

%e 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

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

%t a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]

%t Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* _Harvey P. Dale_, Apr 29 2018 *)

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

%o (Haskell)

%o a050292 n = a050292_list !! (n-1)

%o a050292_list = scanl (+) 0 a035263_list

%o -- _Reinhard Zumkeller_, Jan 21 2013

%Y Bisection of A123087.

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

%K nonn,nice,easy

%O 0,4

%A _Eric W. Weisstein_

%E Extended with formula by _Christian G. Bower_, Sep 15 1999

%E Corrected and extended by _Reinhard Zumkeller_, Aug 16 2006

%E Extended with formula by _Philippe Deléham_, Oct 19 2011

%E Entry revised to give a simpler definition by _N. J. A. Sloane_, Jan 03 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)