Message Boards Message Boards

0
|
3315 Views
|
2 Replies
|
4 Total Likes
View groups...
Share
Share this post:

list of intermediate values of this function

Posted 11 years ago

Hello I am working with this function defined recursively, here is my function:

p[1] := 5;
p[2] := 1;
p[3] := 2;
p[n_] := p[n - 1] + p[n - 3] /; n > 3;

When testing p [14] returns 241 that is well

what I need is the list of values such as the following:

{7,8,10,17,25,35,52,77,112,164,241}

any day is welcome, thanks in advance.

POSTED BY: Luis Ledesma
2 Replies

You can always just make a Table of values:

Table[p[n], {n, 4, 14}]

But I'm guessing this isn't what you want... You can of course always define it to be a recurse function on lists:

p[1] := {5};
p[2] := {1};
p[3] := {2};
p[n_] := {p[n - 1], Last@p[n - 1] + Last@p[n - 3]} /; n > 3;

p[14]

{{{{{{{{{{{{2}, 7}, 8}, 10}, 17}, 25}, 35}, 52}, 77}, 112}, 164}, 241}
POSTED BY: Sean Clarke

There are a number of ways to get that list. Here are a few.

(1) Standard memoization.

p[1] := 5;
p[2] := 1;
p[3] := 2;
p[n_] := p[n] = p[n - 1] + p[n - 3]

In[386]:= Table[p[j], {j, 4, 15}]

Out[386]= {7, 8, 10, 17, 25, 35, 52, 77, 112, 164, 241, 353}

(2) This next is something of a disappointment. One gets horrendous powers of algebraic Root objects.

p2func[n_] = 
  p2[n] /. First[
    RSolve[{p2[n] == p2[n - 1] + p2[n - 3], p2[1] == 5, p2[2] == 1, 
      p2[3] == 2}, p2[n], n]];

In[426]:= Table[p2func[j], {j, 4, 15}] // N // Chop

Out[426]= {7., 8., 10., 17., 25., 35., 52., 77., 112., 164., 241., 353.}

Alternatively, use RootReduce.

In[427]:= Table[RootReduce[p2func[j]], {j, 4, 15}]

Out[427]= {7, 8, 10, 17, 25, 35, 52, 77, 112, 164, 241, 353}

(3) We can set this up as matrix powering. I show the basics but one can do this more efficiently if creating a table by saving previous powers at each step. See method (4) for more on this.

pmat = {{1, 0, 1}, {1, 0, 0}, {0, 1, 0}};
p3[n_] := First[MatrixPower[pmat, n - 3].{2, 1, 5}]
Table[p3[n], {n, 4, 15}]

Out[418]= {7, 8, 10, 17, 25, 35, 52, 77, 112, 164, 241, 353}

(4) NestList is good for this type of thing.

Rest[NestList[{#[[2]], #[[3]], #[[1]] + #[[3]]} &, {5, 1, 2}, 
   12]][[All, -1]]

Out[424]= {7, 8, 10, 17, 25, 35, 52, 77, 112, 164, 241, 353}

We can combine this with the matrix powering:

In[434]:= NestList[pmat.# &, {2, 1, 5}, 12][[2 ;; -1, 1]]

Out[434]= {7, 8, 10, 17, 25, 35, 52, 77, 112, 164, 241, 353}

(5) And there is of course RecurrenceTable.

In[437]:= RecurrenceTable[{p2[n] == p2[n - 1] + p2[n - 3], p2[1] == 5,
   p2[2] == 1, p2[3] == 2}, p2[n], {n, 4, 15}]

Out[437]= {7, 8, 10, 17, 25, 35, 52, 77, 112, 164, 241, 353}
POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract