problem with PURRS ? - with regards to OEIS's A136429
Hi,
Here is the OEIS sequence description: A136429 a(n) = sum( F(k+1)^2 F(n-k+1)^2, k = 0..n ) where F(n) = Fibonacci number (A000045). 1, 2, 9, 26, 84, 250, 747, 2182, 6323, 18132, 51624, 146004, 410677, 1149578, 3204477, 8899502, 24634620, 67990414, 187154271, 513939214, 1408246247, 3851081256, 10512259920, 28647203880, 77946605545, 211782868754 OFFSET
0,2 FORMULA
G.f.: (1-x)^2/((1+x)^2(1-3x+x^2)^2).
Recurrence: a(n+6) = 4 a(n+5) - 10 a(n+3) + 4 a(n+1) - a(n).
AUTHOR
Emanuele Munarini (emanuele.munarini(AT)polimi.it), Apr 01 2008
So I tried PURRS http://www.cs.unipr.it/purrs/ PURRS Demo Results Exact solution for x(n) = -x(6+n)+4*x(5+n)-10*x(3+n)+4*x(1+n) for the initial conditions x(0) = 1 x(1) = 2 x(2) = 9 x(3) = 26 x(4) = 84 x(5) = 250 x(n) = -(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5 *(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n for each n >= 0 Then I have defined sequence in PARI using close formula generated by PURRS (21:16) gp > a(n)=-(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5 *(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n
But it doesn't even give initial conditions ... ? (21:16) gp > a(0) %5 = 1.000000000000000000000000000 (21:16) gp > a(1) %6 = 2.000000000000000000000000000 (21:17) gp > a(3) %7 = 26.00000000000000000000000000 (21:17) gp > a(4) %8 = 63.00000000000000000000000000 (21:17) gp > a(5) %9 = 174.0000000000000000000000000 (21:19) gp > a(6) %10 = 443.0000000000000000000000000
Did I make a mistake in above or ... ?
Ciao, Regards, Alex
x(n)=x(n-x(n-1))+x(n-x(n-2))
PURRS output "this recurrence is malformed"
On Sat, Apr 5, 2008 at 10:27 PM, Alexander Povolotsky apovolot@gmail.com wrote:
Hi,
Here is the OEIS sequence description: A136429 a(n) = sum( F(k+1)^2 F(n-k+1)^2, k = 0..n ) where F(n) = Fibonacci number (A000045).
1, 2, 9, 26, 84, 250, 747, 2182, 6323, 18132, 51624, 146004, 410677,1149578, 3204477, 8899502, 24634620, 67990414, 187154271, 513939214, 1408246247, 3851081256, 10512259920, 28647203880, 77946605545, 211782868754
OFFSET
0,2
FORMULA
G.f.: (1-x)^2/((1+x)^2(1-3x+x^2)^2).
Recurrence: a(n+6) = 4 a(n+5) - 10 a(n+3) + 4 a(n+1) - a(n).
AUTHOR
Emanuele Munarini (emanuele.munarini(AT)polimi.it), Apr 01 2008
So I tried PURRS http://www.cs.unipr.it/purrs/ PURRS Demo Results Exact solution for x(n) = -x(6+n)+4*x(5+n)-10*x(3+n)+4*x(1+n) for the initial conditions x(0) = 1 x(1) = 2 x(2) = 9 x(3) = 26 x(4) = 84 x(5) = 250 x(n) = -(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5 *(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n for each n >= 0 Then I have defined sequence in PARI using close formula generated by PURRS (21:16) gp > a(n)=-(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5 *(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n
But it doesn't even give initial conditions ... ? (21:16) gp > a(0) %5 = 1.000000000000000000000000000 (21:16) gp > a(1) %6 = 2.000000000000000000000000000 (21:17) gp > a(3) %7 = 26.00000000000000000000000000 (21:17) gp > a(4) %8 = 63.00000000000000000000000000 (21:17) gp > a(5) %9 = 174.0000000000000000000000000 (21:19) gp > a(6) %10 = 443.0000000000000000000000000
Did I make a mistake in above or ... ?
Ciao, Regards, Alex
x(n-1) + x(n-2) + x(n-3) x(0) = 1; x(1) = 1; x(2) = 1
PURRS output "memory limit exceeded"
On Sun, Apr 6, 2008 at 8:50 PM, Alexander Povolotsky apovolot@gmail.com wrote:
x(n)=x(n-x(n-1))+x(n-x(n-2))
PURRS output "this recurrence is malformed"
On Sat, Apr 5, 2008 at 10:27 PM, Alexander Povolotsky apovolot@gmail.com wrote:
Hi,
Here is the OEIS sequence description: A136429 a(n) = sum( F(k+1)^2 F(n-k+1)^2, k = 0..n ) where F(n) = Fibonacci number (A000045).
1, 2, 9, 26, 84, 250, 747, 2182, 6323, 18132, 51624, 146004, 410677,1149578, 3204477, 8899502, 24634620, 67990414, 187154271, 513939214, 1408246247, 3851081256, 10512259920, 28647203880, 77946605545, 211782868754
OFFSET
0,2
FORMULA
G.f.: (1-x)^2/((1+x)^2(1-3x+x^2)^2).
Recurrence: a(n+6) = 4 a(n+5) - 10 a(n+3) + 4 a(n+1) - a(n).
AUTHOR
Emanuele Munarini (emanuele.munarini(AT)polimi.it), Apr 01 2008
So I tried PURRS http://www.cs.unipr.it/purrs/ PURRS Demo Results Exact solution for x(n) = -x(6+n)+4*x(5+n)-10*x(3+n)+4*x(1+n) for the initial conditions x(0) = 1 x(1) = 2 x(2) = 9 x(3) = 26 x(4) = 84 x(5) = 250 x(n) = -(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5 *(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n for each n >= 0 Then I have defined sequence in PARI using close formula generated by PURRS (21:16) gp > a(n)=-(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5 *(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n
But it doesn't even give initial conditions ... ? (21:16) gp > a(0) %5 = 1.000000000000000000000000000 (21:16) gp > a(1) %6 = 2.000000000000000000000000000 (21:17) gp > a(3) %7 = 26.00000000000000000000000000 (21:17) gp > a(4) %8 = 63.00000000000000000000000000 (21:17) gp > a(5) %9 = 174.0000000000000000000000000 (21:19) gp > a(6) %10 = 443.0000000000000000000000000
Did I make a mistake in above or ... ?
Ciao, Regards, Alex
Alexander Povolotsky wrote:
x(n-1) + x(n-2) + x(n-3) x(0) = 1; x(1) = 1; x(2) = 1
PURRS output "memory limit exceeded"
I guess that you obtained this via the web interface demo. The bare point is that the solver in the web interface has been tailored to only use a limited amount of both CPU time and system memory, so as to avoid our web server to become unresponsive: since the computation above requires more memory, a deliberate error condition is raised. You can still solve the same recurrence using the web interface, provided you remove the initial conditions (and you do not ask for the verification of the solution).
Cheers, Enea Zaffanella.
Alexander Povolotsky wrote:
x(n-1) + x(n-2) + x(n-3) x(0) = 1; x(1) = 1; x(2) = 1
PURRS output "memory limit exceeded"
Dear Alexander,
apparently you have stumbled upon what appears to be a bug in PURRS. Unfortunately, we are not currently actively developing PURRS as we are busy developing one of its intended client applications: an analyzer for C programs. Work on PURRS will be resumed when this is ready and we will be back to complexity analysis. Meanwhile, you are welcome to investigate this and other problem more deeply and to submit candidate solutions: we will be happy to integrate them into the CVS repository and even to give you read/write access to it, in case you plan to engage into serious PURRS development work. All the best,
Roberto
P.S. Please do not mail addresses other than purrs-devel@cs.unipr.it: all the PURRS people subscribe to that list.
Alexander Povolotsky wrote:
x(n)=x(n-x(n-1))+x(n-x(n-2))
PURRS output "this recurrence is malformed"
The output message has to be interpreted wrt the current capabilities of the system. PURRS cannot handle this kind of recurrence, so it says it is malformed. See http://www.cs.unipr.it/purrs/details for info on the kind of recurrences that PURRS can handle.
Cheers, Enea.
participants (3)
-
Alexander Povolotsky -
Enea Zaffanella -
Roberto Bagnara