[PURRS-devel] purrs/tests heap
Alessandro Zaccagnini
zaccagnini at cs.unipr.it
Sat Nov 20 18:11:04 CET 2004
CVSROOT: /cvs/purrs
Module name: purrs
Changes by: zaccagnini at 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=purrs&r1=1.199&r2=1.200
More information about the PURRS-devel
mailing list