Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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.
*)
share|improve this answer
add comment

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}]
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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