CVSROOT: /cvs/purrs
Module name: purrs
Changes by: zaccagnini(a)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=pur…
