2
$\begingroup$

I have recurrence and I need to calculate first $N$ members of the sequence

ClearAll[aa];
l=3;
aa[n_, l_] := If[n <= l, 
   Quotient[n, l],
   (l + 2 (n - l) aa[n - l, l] + (n - l) (n - 1) aa[n - 1, l])/(n*(n + 1 - l))
]

Table[aa[i, l], {i, 0, 30}] // AbsoluteTiming

I guess it is stupid to use Table since its recalculate some of the members several times. How I can output all members in one pass? Can I use RecurrenceTable in this case and is it the quickest way to do it?

$\endgroup$

2 Answers 2

5
$\begingroup$

Use memoization:

ClearAll[aa, bb];
l = 3;
n = 30;
aa[n_, l_] := If[n <= l, Quotient[n, l], (l + 2 (n - l) aa[n - l, l] + (n - l) (n - 1) aa[n - 1, l])/(n*(n +  1 - l))]
bb[n_, l_] := bb[n, l] = If[n <= l, Quotient[n, l], (l + 2 (n - l) bb[n - l, l] + (n - l) (n - 1) bb[n - 1, l])/(n*(n + 1 - l))]

Table[aa[i, l], {i, 0, n}] // AbsoluteTiming // First
Table[bb[i, l], {i, 0, n}] // AbsoluteTiming // First

(*
2.8
0.
*)
$\endgroup$
1
$\begingroup$

As you suspect,RecurrenceTableis fast. I modified your functionaato eliminate the variablel, and renamed this variable tosto avoid confusion with the digit 1. This is not perfect code, since I have to assume the casesa[n=0]=0, anda[j]=1for allj>0whens=1.

s = 3;
RecurrenceTable[
  {
   aa[n]==(s+2(n-s) aa[n-s] + (n-s) (n-1) aa[n-1])/(n*(n+1-s)),
   Apply[Sequence,Join[Thread[Equal[Array[aa,s-1],ConstantArray[0,s-1]]],{aa[s]==1}]]
  },
   aa,
   {n,1,30}]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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