2
$\begingroup$

We have a recurrence which produces a triangle's row and would like to find an efficient way to produce all rows up to that limit. In addition: Is there a way to do this using matrices? Where we would define a seed number and the same rules to get a triangle?

Clear[a, n];
a[0] := {1};
a[1] := {2*a[0], 3*a[0]};
a[n_] := Flatten[{{4*a[n - 2][[1]], 6*a[n - 2], 9*a[n - 2][[-1]]}}]

Edit corrected the row skipping.

a[-1] = {};
a[0] = {1};
a[n_] := a[n] = Flatten[{{2*a[n - 1][[1]], 6*a[n - 2], 3*a[n - 1][[-1]]}}]
$\endgroup$
  • 2
    $\begingroup$ You can use NestList[], of course: NestList[{#[[2]], Flatten[{4 #[[1, 1]], 6 #[[1]], 9 #[[1, -1]]}]} &, {{1}, {2, 3}}, 5]. $\endgroup$ – J. M.'s discontentment Mar 29 '17 at 12:47
  • 2
    $\begingroup$ Appears to be the same as b[n_, j_] := 2^(n - j)*3^j so could do e.g. Table[b[n, j], {n, 0, 10}, {j, 0, n}]. $\endgroup$ – Daniel Lichtblau Mar 29 '17 at 15:11
4
$\begingroup$

Don't use SetDelayed for the starting conditions, and use memoization for the general rule:

Clear[a, n];
a[0] = {1};
a[1] = {2*a[0], 3*a[0]};
a[n_] := a[n] = Flatten[{4*a[n - 2][[1]], 6*a[n - 2], 9*a[n - 2][[-1]]}]

If you now do a[10]; then all the even n < 10 will be stored inside a[2], a[4],....

Putting the result in a matrix would be something like:

Clear[mat];
mat[n_] := Block[{ans}, ans = ConstantArray[0, {n, n}];
  ans[[1, 1]] = 1;
  ans[[2, 1]] = 2*ans[[1, 1]];
  ans[[2, 2]] = 3*ans[[1, 1]];
  Do[ans[[row, 1]] = 4*ans[[row - 2, 1]];
   ans[[row, row]] = 9*ans[[row - 2, row - 2]];
   Do[ans[[row, col]] = 6*ans[[row - 2, col - 1]], {col, 2, 
     row - 1}], {row, 3, n}];
  ans]

If this is what you mean by "do[ing] this using matrices" ;)

| improve this answer | |
$\endgroup$
1
$\begingroup$

LinearRecurrence

A bit of experimentation shows this nice equivalence with LinearRecurrence which may touch on your matrix quest in some way.

a2[n_] := LinearRecurrence[{3/2}, {2^(n - 1)}, n]

Array[a2, 5]
{{1}, {2, 3}, {4, 6, 9}, {8, 12, 18, 27}, {16, 24, 36, 54, 81}}

NestList

As J. M. proposed you could use NestList, and I would use Join instead of Flatten as should your recursion allow packed arrays it will preserve packing.

f = {#[[2]], Join[2 #[[2, {1}]], 6 #[[1]], 3 #[[2, {-1}]]]} &;

NestList[f, {{}, {1}}, 4][[All, 2]]
{{1}, {2, 3}, {4, 6, 9}, {8, 12, 18, 27}, {16, 24, 36, 54, 81}}

Creating a case to illustrate the point about Join:

f2 = {#[[2]], Flatten[{4 #[[1, 1]], 6 #[[1]], 9 #[[1, -1]]}]} &;

test[fn_] :=
  NestList[fn, N @ {Range@1, Range[2, 3]}, 640][[All, 1]] // Length // RepeatedTiming

test /@ {f, f2}   // Column
{0.0041, 641}

{0.018, 641}
| improve this answer | |
$\endgroup$
  • $\begingroup$ LinearRecurrence is exactly what I had in mind. Thanks. $\endgroup$ – Fred Kline Mar 29 '17 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.