[PURRS-devel] purrs/tests heap

[Alessandro Zaccagnini]

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