|
|
A038573
|
|
a(n) = 2^A000120(n) - 1.
|
|
38
|
|
|
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
|
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
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,31;...)
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)
a(n) is also the number of cells turned ON at n-th generation of the cellular automaton of A267700 in a 90-degree sector on the square grid.
a(n) is also the number of Y-toothpicks added at n-th generation of the structure of A267700 in a 120-degree sector on the triangular grid. (End)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = number of positive integers k < n such that n XOR k = n-k (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
G.f.: -1/(1 - x) + Product_{k>=0} (1 + 2*x^(2^k)). - Ilya Gutkovskiy, Aug 20 2019
G.f. A(x) = x + x^2*A(x) + (1 + 2*x)*(1 - x^2)*A(x^2). - Michael Somos, Jul 24 2023
|
|
EXAMPLE
|
9 = 1001 -> 0011 -> 3, so a(9)=3.
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)
G.f. = x + x^2 + 3*x^3 + x^4 + 3*x^5 + 3*x^6 + 7*x^7 + x^8 + 3*x^9 + 3*x^10 + 7*x^11 + ... - Michael Somos, Jul 24 2023
|
|
MAPLE
|
seq(2^convert(convert(n, base, 2), `+`)-1, n=0..100); # Robert Israel, Jan 24 2016
|
|
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};
(PARI) a(n) = 2^hammingweight(n)-1; \\ Michel Marcus, Jan 24 2016
(Haskell)
a038573 0 = 0
a038573 n = (m + 1) * (a038573 n') + m where (n', m) = divMod n 2
(Python 3.10+)
|
|
CROSSREFS
|
This is Guy Steele's sequence GS(3, 6) (see A135416).
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|