

A050292


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


20



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a doublefree 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. [From Vladimir Shevelev, Apr 15 2010]
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. [From Vladimir Shevelev, Apr 16 2010]
a(n) modulo 2 is the ProuhetThueMorse sequence A010060. Each number n appears A026465(n+1) times.  From 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 ThueMorse sequence A010060 by the run number that term is in.  N. J. A. Sloane, Dec 31 2013


REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. ``On DoubleFree Sets of Integers.'' Ars Combin. 28, 97100, 1989.


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
S. R. Finch, TripleFree Sets of Integers
R. Stephan, Some divideandconquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, DoubleFree Set.


FORMULA

Partial sums of A035263. Close to (2/3)*n.
a(1)=1, a(n)=na(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)=n1; a(n) mod 2 = A010060(n) the ThueMorse sequence; a(n+1)a(n)=A035263(n+1); a(n+2)a(n) = abs(A029884(n)).  Benoit Cloitre, Nov 24, 2002
G.f.: Sum_{k=0..oo} a(n)*x^n = (1/(x1)) * Sum_{i=0..oo} (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)) = 2n1 .  Philippe Deléham, Mar 26 2004
a(2^n)=(2^(n+1)+(1)^n)/3 [From 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)) [From 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^k1)/3)=(2*(4^k1))/9+k/3, i.e. limsupa(n)2n/3=infinity. [From Vladimir Shevelev, Feb 23 2011]
a(n)=Sum_k>=0 {A030308(n,k)*A001045(k+1)}.  From 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)


EXAMPLE

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}.
Since binary expansion of 5 is 101, then Sum{i>=0}b_i*(1)^i=2. Therefore a(5)=10/3+2/3=4 [From Vladimir Shevelev, Apr 15 2010]


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


PROG

(PARI) a(n)=if(n<2, 1, na(floor(n/2)))
(Haskell)
a050292 n = a050292_list !! (n1)
a050292_list = scanl (+) 0 a035263_list
 Reinhard Zumkeller, Jan 21 2013


CROSSREFS

Cf. A001045, A050291A050296, A050321, A035263.
Cf. A121701, A030308. A080277, A120385, A197911.
Sequence in context: A047784 A047742 A203967 * A181627 A071521 A204330
Adjacent sequences: A050289 A050290 A050291 * A050293 A050294 A050295


KEYWORD

nonn,nice,easy


AUTHOR

Eric W. Weisstein


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.  N. J. A. Sloane, Jan 03 2014


STATUS

approved



