CVSROOT: /cvs/purrs Module name: purrs Changes by: zaccagnini@cs.unipr.it 2004-11-20 18:11:03

Modified files: tests : heap

Log message: Added a new linear recurrence of order 2 arising from a number-theoretical problem. Notice that the order-reduction method backfires, in that it finds an expression for the solution which is more complex than it should be. When the initial conditions are "x(0) = 0" and "x(1) = 9", the solution found without the reduction is, indeed, "x(n) = (4 / 5 * n + 1) * 5^n". The more general, and more interesting, relation x(n) = p^2 * x(n-2) + 2 * (p - 1) / p * p^n is marked as "too complex". This phenomenon should be investigated, since PURRS ought to be able to solve the general case as well as special ones. The relevant initial conditions are "x(0)=1" and "x(1) = 2 * p - 1", and the solution is "x(n) = ((p - 1) / p * n + 1) * p^n"

Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/purrs/tests/heap.diff?cvsroot=purr...