

A038573


a(n) = 2^A000120(n)  1.


18



0, 1, 1, 3, 1, 3, 3, 7, 1, 3, 3, 7, 3, 7, 7, 15, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 3, 7, 7, 15, 7, 15, 15, 31, 7, 15, 15, 31, 15, 31, 31, 63, 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31, 3, 7, 7, 15, 7, 15, 15, 31
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Essentially the same sequence as A001316, which has much more information.  N. J. A. Sloane, Jun 05 2009
Smallest number with same number of 1's in its binary expansion as n.
Fixed point of the morphism 0 > 01, 1 > 13, 3 > 37, ... = k > k, 2k+1, ... starting from a(0) = 0; 1 > 01 > 0113 > 01131337 > 011313371337377(15) > ..., .  Robert G. Wilson v, Jan 24 2006
From Gary W. Adamson, Jun 04 2009: (Start)
As an infinite string, 2^n terms per row starting with "1":
(1; 1,3; 1,3,3,7; 1,3,3,7,3,7,7,15; 1,3,3,7,3,7,7,15,3,7,7,15,7,15,15,3l;...)
Row sums of that triangle = A027649: (1, 4, 14, 46, 454,...); where the
next row sum = current term of A027649 + next term in finite difference
row of A027649, i.e., (1, 3, 10, 32, 100, 308,...) = A053581. (End)


LINKS

T. D. Noe, Table of n, a(n) for n=0..1023
Michael Gilleland, Some SelfSimilar Integer Sequences


FORMULA

a(2n) = a(n), a(2n+1) = 2*a(n)+1, a(0) = 0. a(n) = A001316(n)1 = 2^A000120(n)  1.  Daniele Parisse (daniele.parisse(AT)m.dasa.de)
a(n) = number of positive integers k < n such that n XOR k = nk (cf. A115378).  Paul D. Hanna, Jan 21 2006
a(n) = f(n, 1) with f(x, y) = if x = 0 then y  1 else f(floor(x/2), y*(1 + x mod 2)).  Reinhard Zumkeller, Nov 21 2009
a(n) = (n mod 2 + 1) * a(floor(n/2)) + n mod 2.  Reinhard Zumkeller, Oct 10 2012


EXAMPLE

9 = 1001 > 0011 > 3, so a(9)=3.
From Gary W. Adamson, Jun 04 2009: (Start)
Triangle read by rows:
. 1;
. 1, 3;
. 1, 3, 3, 7;
. 1, 3, 3, 7, 3, 7, 7, 15;
. 1, 3, 3, 7, 3, 7, 7, 15, 3, 7, 7, 15, 7, 15, 15, 31;
. ...
Row sums: (1, 4, 14, 46,...) = A026749 = last row terms + new set of terms such that row 3 = (1, 3, 3, 7,) + (3, 7, 7, 15) = 14 + 32 = A027649(3) + A053581(3). (End)
The rows of this triangle converge to A159913.  N. J. A. Sloane, Jun 05 2009


MATHEMATICA

Array[ 2^Count[ IntegerDigits[ #, 2 ], 1 ]1&, 100 ]
Nest[ Flatten[ # /. a_Integer > {a, 2a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 24 2006 *)


PROG

(PARI) a(n)=2^subst(Pol(binary(n)), x, 1)1
(Haskell)
a038573 0 = 0
a038573 n = (m + 1) * (a038573 n') + m where (n', m) = divMod n 2
 Reinhard Zumkeller, Oct 10 2012, Feb 07 2011


CROSSREFS

Cf. A007313, A115378.
This is Guy Steele's sequence GS(3, 6) (see A135416).
A027649, A053581.  Gary W. Adamson, Jun 04 2009
Cf. A000079.  Omar E. Pol, Jun 07 2009
Sequence in context: A005885 A205145 A061892 * A246591 A173465 A151837
Adjacent sequences: A038570 A038571 A038572 * A038574 A038575 A038576


KEYWORD

nonn,easy,nice


AUTHOR

Marc LeBrun


EXTENSIONS

More terms from Erich Friedman
New definition from N. J. A. Sloane, Mar 01 2008


STATUS

approved



