Displaying 1-10 of 12 results found.
A014486-index of the stunted binomial-mod-2 zigzag trees. See A080263.
+20
8
1, 6, 51, 6051, 76746, 12926010, 2372452685, 93393905915739, 1351877861804543, 286738012677424022, 62026524057807548707, 3041407633778252699836049, 686215566631222460001238168, 35912919120400408619708285058798
Breadth-first-wise A014486-like encoding of the stunted binomial-mod-2 zigzag trees ( A080263).
+20
4
2, 56, 968, 249728, 3996680, 1023152000, 261926931584, 17165643396644864, 274650294346579976, 70310475352724475776, 17999481690297465818240, 1179614032055334719872532480, 301981192206165688287372558464
Orbit size of each tree A080263(n) under Donaghey's "Map M" Catalan automorphism.
+20
3
1, 3, 3, 27, 54, 54, 18, 1134, 1134, 1134, 1134, 1782, 1782, 594, 594, 30618, 30618, 30618, 30618, 78246, 78246, 78246, 78246, 165726, 165726
Orbit size of each tree A080263(n) under Meeussen's bf<->df map on binary trees.
+20
3
1, 3, 16, 1441, 41888, 3376173
A063171-encoding of the stunted binomial-mod-2 zigzag trees. See A080263.
+20
2
10, 110010, 1110001010, 111100100010110010, 1111100010001011001010, 111111001000100010110010110010, 11111110001010001000101100101110001010, 111111110010001011001000100010110010111100100010110010
CROSSREFS
Breadth-first-wise encodings of the same trees: A080269.
0, 2, 28, 3995, 53032, 9218158, 1716408828, 68406706423034, 993609159645474, 211483814340246174, 45849905806140642231, 2254554272777258549734599, 509234594705250632023415288, 26692711238971831653512953923634
Total number of odd entries in first n rows of Pascal's triangle: a(0) = 0, a(1) = 1, a(2k) = 3*a(k), a(2k+1) = 2*a(k) + a(k+1). a(n) = Sum_{i=0..n-1} 2^wt(i).
(Formerly M2445)
+10
64
0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, 119, 135, 139, 147, 155, 171, 179, 195, 211, 243, 245, 249, 253, 261, 265, 273, 281, 297, 301, 309, 317, 333, 341, 357, 373, 405, 409, 417, 425, 441, 449, 465, 481, 513, 521
COMMENTS
The graph has a blancmange or Takagi appearance. For the asymptotics, see the references by Flajolet with "Mellin" in the title. - N. J. A. Sloane, Mar 11 2021 The following alternative construction of this sequence is due to Thomas Nordhaus, Oct 31 2000: For each n >= 0 let f_n be the piecewise linear function given by the points (k /(2^n), a(k) / 3^n), k = 0, 1, ..., 2^n. f_n is a monotonic map from the interval [0,1] into itself, f_n(0) = 0, f_n(1) = 1. This sequence of functions converges uniformly. But the limiting function is not differentiable on a dense subset of this interval. I submitted a problem to the Amer. Math. Monthly about an infinite family of non-convex sequences that solve a recurrence that involves minimization: a(1) = 1; a(n) = max { ua(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1; here u is any real-valued constant >= 1. The case u=2 gives the present sequence. Cf. A130665 - A130667. - Don Knuth, Jun 18 2007 Let M = an infinite lower triangular matrix with (1, 3, 2, 0, 0, 0, ...) in every column shifted down twice:
1;
3;
2; 1;
0, 3;
0, 2, 1;
0, 0, 3;
0, 0, 2, 1;
0, 0, 0, 3;
0, 0, 0, 2, 1;
...
This sequence starting with "1" = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. (End)
The production matrix of Dec 06 2009 is equivalent to the following: Let p(x) = (1 + 3x + 2x^2). The sequence = P(x) * p(x^2) * p(x^4) * p(x^8) * .... The sequence divided by its aerated variant = (1, 3, 2, 0, 0, 0, ...). - Gary W. Adamson, Aug 26 2016 Also the total number of ON cells, rows 1 through n, for cellular automaton Rule 90 (Cf. A001316, A038183, also Mathworld Link). - Bradley Klee, Dec 22 2018
REFERENCES
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.16.
Flajolet, Philippe, and Mordecai Golin. "Mellin transforms and asymptotics." Acta Informatica 31.7 (1994): 673-696.
Flajolet, Philippe, Mireille Régnier, and Robert Sedgewick. "Some uses of the Mellin integral transform in the analysis of algorithms." in Combinatorial algorithms on words. Springer, 1985. 241-254.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Eric Weisstein's World of Mathematics, Rule 90
FORMULA
a(n) = n^(log_2(3))*G(log_2(n)) where G(x) is a function of period 1 defined by its Fourier series. - Benoit Cloitre, Aug 16 2002; formula modified by S. R. Finch, Dec 31 2007 G.f.: (x/(1-x))*Product_{k>=0} (1 + 2*x^2^k). - Ralf Stephan, Jun 01 2003; corrected by Herbert S. Wilf, Jun 16 2005 a(1) = 1, a(n) = 2*a(floor(n/2)) + a(ceiling(n/2)).
MAPLE
f:=proc(n) option remember;
if n <= 1 then n elif n mod 2 = 0 then 3*f(n/2)
else 2*f((n-1)/2)+f((n+1)/2); fi; end;
MATHEMATICA
f[n_] := Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ]; Table[ Sum[ f[k], {k, 0, n} ], {n, 0, 100} ]
Join[{0}, Accumulate[Count[#, _?OddQ]&/@Table[Binomial[n, k], {n, 0, 60}, {k, 0, n}]]] (* Harvey P. Dale, Dec 10 2014 *) FoldList[Plus, 0, Total /@ CellularAutomaton[90, Join[Table[0, {#}], {1}, Table[0, {#}]], #]][[2 ;; -1]] &@50 (* Bradley Klee, Dec 23 2018 *) Join[{0}, Accumulate[2^DigitCount[Range[0, 127], 2, 1]]] (* Paolo Xausa, Oct 24 2024 *)
PROG
(PARI) a(n) = if(!n, 0, my(r=0, t=1); forstep(i=logint(n, 2), 0, -1, r*=3; if(bittest(n, i), r+=t; t*=2)); r); \\ Ruud H.G. van Tol, Jul 06 2024 (Haskell)
a006046 = sum . concat . (`take` a047999_tabl)
(Python) from functools import lru_cache
@lru_cache(maxsize=None)
(Magma) [0] cat [n le 1 select 1 else 2*Self(Floor(n/2)) + Self(Floor(Ceiling(n/2))): n in [1..60]]; // Vincenzo Librandi, Aug 30 2016
CROSSREFS
Sequences of form a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.
KEYWORD
nonn, nice, easy, look, changed
A014486-encoding of the branch-reduced binomial-mod-2 binary trees.
+10
12
2, 50, 14642, 3969842, 267572689202, 69427226972978, 4581045692538239282, 301220569271221714981682, 1295918094920364850246919050705202, 332029112115571675270693117549056818
COMMENTS
These are obtained from the stunted binomial-mod-2 zigzag trees ( A080263) either by extending each leaf to a branch of two leaves, or by branch-reducing every other such tree.
Triangle read by rows giving successive states of cellular automaton generated by "Rule 90".
+10
8
1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0
COMMENTS
If either neighbor is 1 then new state is 1, otherwise new state is 0.
Row n has length 2n+1.
Rules #18, #26, #82, #90, #146, #154, #210, #218 all give rise to this sequence. - Hans Havermann
REFERENCES
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 25.
LINKS
Eric Weisstein's World of Mathematics, Rule 90
EXAMPLE
1; 1,0,1; 1,0,0,0,1; 1,0,1,0,1,0,1; ...
MATHEMATICA
rows = 10; ca = CellularAutomaton[90, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, rows-k+1 ;; rows+k-1]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)
KEYWORD
nonn,tabf,nice,easy,changed
a(n) = Sum_{k=1..n} 2^b(k) where b(k) denotes the number of 1's in the binary representation of k.
+10
5
2, 4, 8, 10, 14, 18, 26, 28, 32, 36, 44, 48, 56, 64, 80, 82, 86, 90, 98, 102, 110, 118, 134, 138, 146, 154, 170, 178, 194, 210, 242, 244, 248, 252, 260, 264, 272, 280, 296, 300, 308, 316, 332, 340, 356, 372, 404, 408, 416, 424, 440, 448, 464, 480, 512, 520, 536
FORMULA
a(0)=0, a(2n) = 2a(n-1) + a(n) + 2, a(2n+1) = 3a(n) + 2.
G.f.: (1/(1-x)) * Product_{k>=0} (1 + 2x^2^k). (End)
MAPLE
f:= proc(n) option remember; if n::even then 2*procname(n/2-1)+procname(n/2)+2
else 3*procname((n-1)/2)+2
fi
end proc:
f(0):= 0:
MATHEMATICA
b[n_] := IntegerDigits[n, 2] // Total;
a[n_] := 2^(b /@ Range[n]) // Total;
PROG
(PARI) a(n)=sum(i=1, n, 2^sum(k=1, length(binary(i)), component(binary(i), k)))
Search completed in 0.009 seconds
|