Displaying 1-10 of 63 results found.
Triangle T(n,k), n>=0, 0<=k<=floor(log_2(n+1)), read by rows: T(n,k) = number of nonnegative integers <= n having binary weight k.
+0
15
1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 3, 2, 1, 3, 3, 1, 3, 3, 1, 1, 4, 3, 1, 1, 4, 4, 1, 1, 4, 5, 1, 1, 4, 5, 2, 1, 4, 6, 2, 1, 4, 6, 3, 1, 4, 6, 4, 1, 4, 6, 4, 1, 1, 5, 6, 4, 1, 1, 5, 7, 4, 1, 1, 5, 8, 4, 1, 1, 5, 8, 5, 1, 1, 5, 9, 5, 1, 1, 5, 9, 6, 1, 1, 5, 9, 7, 1
COMMENTS
T(n,k) is defined for all n >= 0 and k >= 0. Terms that are not in the triangle are zero.
FORMULA
T(n,k) = T(n-1,k) + [ A000120(n) = k] where [] is the Iverson bracket and T(n,k) = 0 for n<0. T(2^n-1,k) = A007318(n,k) = binomial(n,k). T(n,floor(log_2(n+1))) = A090996(n+1). Sum_{k>=0} T(n,k) = n+1.
Sum_{k>=0} k * T(n,k) = A000788(n). Sum_{k>=0} k^2 * T(n,k) = A231500(n). Sum_{k>=0} k^3 * T(n,k) = A231501(n). Sum_{k>=0} k^4 * T(n,k) = A231502(n). Sum_{k>=0} 2^k * T(n,k) = A006046(n+1). Sum_{k>=0} 3^k * T(n,k) = A130665(n). Sum_{k>=0} 4^k * T(n,k) = A116520(n+1). Sum_{k>=0} 5^k * T(n,k) = A130667(n+1). Sum_{k>=0} 6^k * T(n,k) = A116522(n+1). Sum_{k>=0} 7^k * T(n,k) = A161342(n+1). Sum_{k>=0} 8^k * T(n,k) = A116526(n+1). Sum_{k>=0} 10^k * T(n,k) = A116525(n+1). Sum_{k>=0} n^k * T(n,k) = A361257(n).
EXAMPLE
T(6,2) = 3: 3, 5, 6, or in binary: 11_2, 101_2, 110_2.
T(15,3) = 4: 7, 11, 13, 14, or in binary: 111_2, 1011_2, 1101_2, 1110_2.
Triangle T(n,k) begins:
1;
1, 1;
1, 2;
1, 2, 1;
1, 3, 1;
1, 3, 2;
1, 3, 3;
1, 3, 3, 1;
1, 4, 3, 1;
1, 4, 4, 1;
1, 4, 5, 1;
1, 4, 5, 2;
1, 4, 6, 2;
1, 4, 6, 3;
1, 4, 6, 4;
1, 4, 6, 4, 1;
...
MAPLE
b:= proc(n) option remember; `if`(n<0, 0,
b(n-1)+x^add(i, i=Bits[Split](n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..23);
PROG
(PARI) T(n, k) = my(v1); v1 = Vecrev(binary(n+1)); v1 = Vecrev(select(x->(x>0), v1, 1)); sum(j=0, min(k, #v1-1), binomial(v1[j+1]-1, k-j)) \\ Mikhail Kurkov, Nov 27 2024
CROSSREFS
Last elements of rows give A090996(n+1). Cf. A000027, A000120, A000225, A000788, A006046, A007318, A116520, A116522, A116525, A116526, A130665, A130667, A161342, A231500, A231501, A231502, A272020, A361257.
Expansion of Product_{k>=0} 1/(1 + 2*x^(2^k)).
+0
2
1, -2, 2, -4, 10, -20, 36, -72, 154, -308, 596, -1192, 2420, -4840, 9608, -19216, 38586, -77172, 154036, -308072, 616740, -1233480, 2465768, -4931536, 9865492, -19730984, 39457128, -78914256, 157838120, -315676240, 631333264, -1262666528, 2525371642, -5050743284
FORMULA
a(0) = 1; a(n) = -Sum_{k=1..n} 2^ A000120(k) * a(n-k).
MATHEMATICA
nmax = 33; CoefficientList[Series[Product[1/(1 + 2 x^(2^k)), {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x]
a[0] = 1; a[n_] := a[n] = -Sum[2^DigitCount[k, 2, 1] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 33}]
Expansion of Product_{k>=0} (1 + 2*x^(2^k))^2.
+0
1
1, 4, 8, 16, 24, 32, 48, 64, 88, 96, 128, 128, 176, 192, 256, 256, 344, 352, 448, 384, 512, 512, 640, 512, 688, 704, 896, 768, 1024, 1024, 1280, 1024, 1368, 1376, 1728, 1408, 1856, 1792, 2176, 1536, 2048, 2048, 2560, 2048, 2688, 2560, 3072, 2048, 2736, 2752, 3456
FORMULA
G.f. A(x) satisfies: A(x) = (1 + 2*x)^2 * A(x^2). - Ilya Gutkovskiy, Jul 09 2019
MATHEMATICA
nmax = 50; CoefficientList[Series[Product[(1 + 2 x^(2^k))^2, {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x]
a[n_] := a[n] = Sum[2^(DigitCount[k, 2, 1] + DigitCount[n - k, 2, 1]), {k, 0, n}]; Table[a[n], {n, 0, 50}]
1, 13, 25, 109, 121, 193, 325, 493, 529, 661, 829, 1129, 1189, 1405, 1657, 2101, 2149, 2281, 2533, 3133, 3337, 3709, 4309, 4909, 5065, 5449, 5917, 6757, 6877, 7381, 7873, 8845, 8893, 9025, 9277, 9877, 10165, 10849, 11737
COMMENTS
Also the number of ON cells after n generations in a knight's-move, one-neighbor, accumulative cellular automaton on the hexagonal lattice A_2. Define v(m)=2*sqrt(3)*[cos(m*Pi/3+Pi/6), sin(m*Pi/3+Pi/6)], vL(m)=2*v(m)+v(m+1), vR(m)=2*v(m)+v(m-1). The set of "knight's moves", M={vL(m):m=1,2,..6} U {vR(m):m=1,2,..6}, follows from an analogy between Z^2 and A_2. At each generation all ON cells remain ON while an OFF cell turns ON if and only if it has exactly one M-neighbor in the previous generation.
Fractal Structure Theorem (FST). A pair of lattice vectors M={v1,v2} generate a wedge, W = {x*v1 + y*v2 : x>=0, y>=0}. Define W-Subsets T_k such that T_{k+1}= T_k U { 2^n*v1 + v : v in T_k } U {2^n*v2 + v : v in T_k}, T_0 = { [0,0] }. The limit set T_{oo} is a fractal, and acquires the topology of a binary tree when points are connected by either v1 or v2. As a tree, T_k has height 2^k-1, with 2^k vertices at maximum depth, along a line in the direction v1-v2. Assume a one-M-neighbor, accumulative cellular automaton on W, where all vertices in T_k are ON. In the next generation, the front F_k={2^k*v1+m*(v2-v1) : 0<=m<=2^k} contains only two ON cells, {2^k*v1,2^k*v2}. The spacing, 2^k-1, is wide enough to turn ON two copies of T_k, one starting from each of the two ON cells in F_k. Thus T_{k+1} is also ON. Whenever only T_0 is ON as an initial condition, by induction, T_{oo} is ultimately ON.
The FST applies here to 12 distinct wedges: with {v1,v2}={vL(m), vR(m)} or with (v1,v2)={vL(m), vR(m+1)}, and m=1,2,..6. The triangle inequality ensures that paths including other vectors cannot reach the front F_k by generation 2^k. However, other vectors do generate retrogressive growth, which turns ON many additional cells.
The FST applies to a wide range of Cellular Automata. Wolfram's one-dimensional rule 90 gives the most elementary example where T_{oo} determines every ON cell. The tree structure T_{oo} also occurs with two-dimensional, accumulative, one-neighbor C.A. such as A151723, A319018, A147562. Also try: M={[0,1],[0,-1],[2,1],[-2,-1]}. According to S. Ulam (cf. Links), some version of the FST was already known to J. Holladay circa 1960.
The FST implies scale resonance between this cellular automaton and the arrowed half hexagon tiling (cf. Links).
MATHEMATICA
HexStar=2*Sqrt[3]*{Cos[#*Pi/3+Pi/6], Sin[#*Pi/3+Pi/6]}&/@Range[0, 5];
MoveSet=Join[2*HexStar+RotateRight[HexStar], 2*HexStar+RotateLeft[HexStar]];
Clear@Pts; Pts[0] = {{0, 0}};
Pts[n_]:=Pts[n]=With[{pts=Pts[n-1]}, Union[pts, Cases[Tally[Flatten[pts/.{x_, y_}:> Evaluate[{x, y}+#&/@MoveSet], 1]], {x_, 1}:>x]]]; Length[Pts[#]]&/@Range[0, 32]
Irregular triangle T(n, k), read by rows, n >= 0 and 0 <= k < A001316(n): T(n, k) is the (k+1)-th nonnegative number m such that n AND m = m (where AND denotes the bitwise AND operator).
+0
15
0, 0, 1, 0, 2, 0, 1, 2, 3, 0, 4, 0, 1, 4, 5, 0, 2, 4, 6, 0, 1, 2, 3, 4, 5, 6, 7, 0, 8, 0, 1, 8, 9, 0, 2, 8, 10, 0, 1, 2, 3, 8, 9, 10, 11, 0, 4, 8, 12, 0, 1, 4, 5, 8, 9, 12, 13, 0, 2, 4, 6, 8, 10, 12, 14, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0
COMMENTS
For any n >= 0 and k such that 0 <= k < A001316(n): - the six previous relations correspond respectively (when applicable) to the second term, the third term, the pair of central terms, the penultimate term and the last term of a row,
- T(n, k) AND T(n, A001316(n) - k - 1) = 0, - T(n, k) + T(n, A001316(n) - k - 1) = n, - T(n, k) = k for any k < A006519(n+1), If we plot (n, T(n,k)) then we obtain a skewed Sierpinski triangle (see Links section).
If interpreted as a flat sequence a(n) for n >= 0:
- a(n) = 0 iff n = A006046(k) for some k >= 0, - a(n) = 1 iff n = A006046(2*k + 1) + 1 for some k >= 0, - a( A006046(k) - 1) = k - 1 for any k > 0.
FORMULA
For any n >= 0 and k such that 0 <= k < A001316(n): - T(n, 0) = 0,
- T(2*n, k) = 2*T(n, k),
- T(2*n+1, 2*k) = 2*T(n, k),
- T(2*n+1, 2*k+1) = 2*T(n, k) + 1.
EXAMPLE
Triangle begins:
0: [0]
1: [0, 1]
2: [0, 2]
3: [0, 1, 2, 3]
4: [0, 4]
5: [0, 1, 4, 5]
6: [0, 2, 4, 6]
7: [0, 1, 2, 3, 4, 5, 6, 7]
8: [0, 8]
9: [0, 1, 8, 9]
10: [0, 2, 8, 10]
11: [0, 1, 2, 3, 8, 9, 10, 11]
12: [0, 4, 8, 12]
13: [0, 1, 4, 5, 8, 9, 12, 13]
14: [0, 2, 4, 6, 8, 10, 12, 14]
15: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
MATHEMATICA
A295989row[n_] := Select[Range[0, n], BitAnd[#, n-#] == 0 &];
Array[A295989row, 25, 0] (* Paolo Xausa, Feb 24 2024 *)
PROG
(PARI) T(n, k) = if (k==0, 0, n%2==0, 2*T(n\2, k), k%2==0, 2*T(n\2, k\2), 2*T(n\2, k\2)+1)
a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(4,1).
+0
8
1, 5, 21, 25, 89, 105, 121, 125, 381, 445, 509, 525, 589, 605, 621, 625, 1649, 1905, 2161, 2225, 2481, 2545, 2609, 2625, 2881, 2945, 3009, 3025, 3089, 3105, 3121, 3125, 7221, 8245, 9269, 9525, 10549, 10805, 11061, 11125, 12149, 12405, 12661, 12725, 12981, 13045, 13109, 13125, 14149, 14405
PROG
(PARI) a(n) = if (n==1, 1, 4*a(ceil(n/2))+a(floor(n/2))); \\ Michel Marcus, Aug 30 2016
CROSSREFS
Sequences of form a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (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.
a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(3,2).
+0
8
1, 5, 17, 25, 61, 85, 109, 125, 233, 305, 377, 425, 497, 545, 593, 625, 949, 1165, 1381, 1525, 1741, 1885, 2029, 2125, 2341, 2485, 2629, 2725, 2869, 2965, 3061, 3125, 4097, 4745, 5393, 5825, 6473, 6905, 7337, 7625, 8273, 8705, 9137, 9425, 9857, 10145, 10433, 10625, 11273, 11705, 12137, 12425
PROG
(PARI) a(n) = if (n==1, 1, 3*a(ceil(n/2))+2*a(floor(n/2))); \\ Michel Marcus, Aug 30 2016 (Magma) [n le 1 select 1 else 3*Self(Ceiling(n/2))+2*Self(Floor(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)) with a(1)=1 and (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.
a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(2,3).
+0
8
1, 5, 13, 25, 41, 65, 89, 125, 157, 205, 253, 325, 373, 445, 517, 625, 689, 785, 881, 1025, 1121, 1265, 1409, 1625, 1721, 1865, 2009, 2225, 2369, 2585, 2801, 3125, 3253, 3445, 3637, 3925, 4117, 4405, 4693, 5125, 5317, 5605, 5893, 6325, 6613, 7045, 7477, 8125, 8317, 8605, 8893, 9325, 9613, 10045
PROG
(PARI) a(n) = if (n==1, 1, 2*a(ceil(n/2))+3*a(floor(n/2))); \\ Michel Marcus, Aug 30 2016 (Magma) [n le 1 select 1 else 2*Self(Ceiling(n/2))+3*Self(Floor(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)) with a(1)=1 and (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.
a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (r,s)=(3,1).
+0
9
1, 4, 13, 16, 43, 52, 61, 64, 145, 172, 199, 208, 235, 244, 253, 256, 499, 580, 661, 688, 769, 796, 823, 832, 913, 940, 967, 976, 1003, 1012, 1021, 1024, 1753, 1996, 2239, 2320, 2563, 2644, 2725, 2752, 2995, 3076, 3157, 3184, 3265, 3292, 3319, 3328, 3571, 3652, 3733, 3760, 3841, 3868, 3895
COMMENTS
Number of triples 0 <= i, j, k < n such that bitwise AND of all pairs (i, j), (j, k), (k, i) is 0. - Peter Karpov, Mar 01 2016 Start with A = [[[1]]], iteratively replace every element Aijk with Aijk * [[[1, 1], [1, 0]], [[1, 0], [0, 0]]]. a(n) is the sum of the resulting array inside the cubic region i, j, k < n. - Peter Karpov, Mar 01 2016
PROG
(PARI) a(n) = if (n==1, 1, 3*a(ceil(n/2)) + a(floor(n/2))); \\ Michel Marcus, Mar 24 2016
CROSSREFS
Sequences of form a(n) = r*a(ceiling(n/2))+s*a(floor(n/2)) with a(1)=1 and (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.
Total number of OFF (white) cells after n iterations of the "Rule 182" elementary cellular automaton starting with a single ON (black) cell.
+0
22
0, 0, 2, 2, 4, 6, 12, 12, 14, 16, 22, 24, 30, 36, 50, 50, 52, 54, 60, 62, 68, 74, 88, 90, 96, 102, 116, 122, 136, 150, 180, 180, 182, 184, 190, 192, 198, 204, 218, 220, 226, 232, 246, 252, 266, 280, 310, 312, 318, 324, 338, 344, 358, 372, 402, 408, 422, 436
COMMENTS
It appears that a(n) is also the number of increasing binary-containment pairs of distinct positive integers up to n + 1. A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second. For example, the a(2) = 2 through a(8) = 14 pairs are:
{1,3} {1,3} {1,3} {1,3} {1,3} {1,3} {1,3}
{2,3} {2,3} {1,5} {1,5} {1,5} {1,5} {1,5}
{2,3} {2,3} {1,7} {1,7} {1,7}
{4,5} {2,6} {2,3} {2,3} {1,9}
{4,5} {2,6} {2,6} {2,3}
{4,6} {2,7} {2,7} {2,6}
{3,7} {3,7} {2,7}
{4,5} {4,5} {3,7}
{4,6} {4,6} {4,5}
{4,7} {4,7} {4,6}
{5,7} {5,7} {4,7}
{6,7} {6,7} {5,7}
{6,7}
{8,9}
(End)
REFERENCES
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.
MATHEMATICA
rule=182; rows=20; ca=CellularAutomaton[rule, {{1}, 0}, rows-1, {All, All}]; (* Start with single black cell *) catri=Table[Take[ca[[k]], {rows-k+1, rows+k-1}], {k, 1, rows}]; (* Truncated list of each row *) nbc=Table[Total[catri[[k]]], {k, 1, rows}]; (* Number of Black cells in stage n *) nwc=Table[Length[catri[[k]]]-nbc[[k]], {k, 1, rows}]; (* Number of White cells in stage n *) Table[Total[Take[nwc, k]], {k, 1, rows}] (* Number of White cells through stage n *)
Search completed in 0.036 seconds
|