cp's OEIS Frontend

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

%I A050292 #95 Feb 16 2025 08:32:40
%S A050292 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 A050292 19,20,20,21,21,22,22,23,24,25,25,26,26,27,27,28,29,30,30,31,32,33,33,
%U A050292 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 A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).
%C A050292 Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
%C A050292 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 A050292 Least k such that a(k)=n is equal to A003159(n).
%C A050292 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 A050292 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 A050292 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 A050292 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 A050292 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 A050292 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
%D A050292 Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.
%H A050292 Reinhard Zumkeller, <a href="/A050292/b050292.txt">Table of n, a(n) for n = 0..10000</a>
%H A050292 Steven R. Finch, <a href="/FinchTriple.html">Triple-Free Sets of Integers</a> [From Steven Finch, Apr 20 2019]
%H A050292 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A050292 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H A050292 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Double-FreeSet.html">Double-Free Set</a>.
%F A050292 Partial sums of A035263. Close to (2/3)*n.
%F A050292 a(n) = A123087(2*n) = n - A123087(n). - _Max Alekseyev_, Mar 05 2023
%F A050292 From _Benoit Cloitre_, Nov 24 2002: (Start)
%F A050292 a(1)=1, a(n) = n - a(floor(n/2));
%F A050292 a(n) = (2/3)*n + (1/3)*A065359(n);
%F A050292 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 A050292 a(A039004(n)) = (2/3)*A039004(n);
%F A050292 a(2*A039004(n)) = 2*a(A039004(n));
%F A050292 a(A003159(n)) = n;
%F A050292 a(A003159(n)-1) = n-1;
%F A050292 a(n) mod 2 = A010060(n) the Thue-Morse sequence;
%F A050292 a(n+1) - a(n) = A035263(n+1);
%F A050292 a(n+2) - a(n) = abs(A029884(n)).
%F A050292 (End)
%F A050292 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
%F A050292 a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - _Benoit Cloitre_, Jun 03 2003
%F A050292 a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - _Philippe Deléham_, Mar 26 2004
%F A050292 a(2^n) = (2^(n+1) + (-1)^n)/3. - _Vladimir Shevelev_, Apr 15 2010
%F A050292 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 A050292 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 A050292 a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - _Philippe Deléham_, Oct 19 2011
%F A050292 From _Peter Bala_, Feb 02 2013: (Start)
%F A050292 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 A050292 (End)
%e A050292 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 A050292 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 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 A050292 a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
%t A050292 Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* _Harvey P. Dale_, Apr 29 2018 *)
%o A050292 (PARI) a(n)=if(n<2,1,n-a(floor(n/2)))
%o A050292 (Haskell)
%o A050292 a050292 n = a050292_list !! (n-1)
%o A050292 a050292_list = scanl (+) 0 a035263_list
%o A050292 -- _Reinhard Zumkeller_, Jan 21 2013
%o A050292 (Python)
%o A050292 from sympy.ntheory import digits
%o A050292 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
%Y A050292 Bisection of A123087.
%Y A050292 Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.
%K A050292 nonn,nice,easy
%O A050292 0,4
%A A050292 _Eric W. Weisstein_
%E A050292 Extended with formula by _Christian G. Bower_, Sep 15 1999
%E A050292 Corrected and extended by _Reinhard Zumkeller_, Aug 16 2006
%E A050292 Extended with formula by _Philippe Deléham_, Oct 19 2011
%E A050292 Entry revised to give a simpler definition by _N. J. A. Sloane_, Jan 03 2014