ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 29 Jul 2014 01:14:05 -0500Symbolic integer arithmetichttp://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/It's not that hard to find a closed expression for the remainder of the polynomial $x^n$ modulo $x^2-5x-2$. But I don't seem to manage it in SAGE.
n=var('n')
R=PolynomialRing(RationalField(),'x');R
x=R.gen();x
mp=x^2-5*x-2
S=R.quotient(mp,'a')
a=S.gen();a^2
a^5
works as expected, but replacing the last line with a^n gives an error (non-integral exponents not supported). I understand a general variable is not a SAGE integer, but how DO I make clear n is supposed to be an integer?
In the same way, it's not that hard to calculate the symbolic n-the power of a small, say 2x2, matrix, but the straightforward aproach of simplifying A^n gives the same error (non-integral exponents not supported).
I checked wolfram alpha for the symbolic power of a matrix, and immediately got the expected answer for [[1,2],[3,4]]^n .
![Wolfram alpha answer](http://www4b.wolframalpha.com/Calculate/MSP/MSP16951af85fib66538dhg0000648f487198eeg2e8?MSPStoreType=image/gif&s=54&w=1188.&h=58.)
Mon, 28 Jul 2014 08:41:10 -0500http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/Answer by rws for <p>It's not that hard to find a closed expression for the remainder of the polynomial $x^n$ modulo $x^2-5x-2$. But I don't seem to manage it in SAGE.</p>
<pre><code>n=var('n')
R=PolynomialRing(RationalField(),'x');R
x=R.gen();x
mp=x^2-5*x-2
S=R.quotient(mp,'a')
a=S.gen();a^2
a^5
</code></pre>
<p>works as expected, but replacing the last line with a^n gives an error (non-integral exponents not supported). I understand a general variable is not a SAGE integer, but how DO I make clear n is supposed to be an integer?</p>
<p>In the same way, it's not that hard to calculate the symbolic n-the power of a small, say 2x2, matrix, but the straightforward aproach of simplifying A^n gives the same error (non-integral exponents not supported).</p>
<p>I checked wolfram alpha for the symbolic power of a matrix, and immediately got the expected answer for [[1,2],[3,4]]^n .</p>
<p><img alt="Wolfram alpha answer" src="http://www4b.wolframalpha.com/Calculate/MSP/MSP16951af85fib66538dhg0000648f487198eeg2e8?MSPStoreType=image/gif&s=54&w=1188.&h=58."/></p>
http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/?answer=23613#post-id-23613Well looking at `[a^n for n in range(10)]` it's obviously a linear recurrence with the coefficients (5,2) the coefficients of `mp`,
a^n mod mp = p(n)*a+q(n), where p(n)=[A015535(n)](https://oeis.org/A015535), q(n)=2p(n-1)
and this generalizes to any polynomial. So, your question concerns two things:
- have Sage understand your problem. I don't think that simply giving the expression a^n mod mp should output
a closed form of that result. Rather, Sage would need a hint, like a command that takes that expression a^n and
the ring and returns an expression containing linear recurrence (linrec) objects,
- Sage would need a linear recurrence object, this is http://trac.sagemath.org/ticket/15714, see also https://sites.google.com/site/cfinitesequenceforsage/
- to compute the values of degree-2 linrecs you can already use `lucas_number1` but this is no general solution, and it's not a symbolic function in Sage, so it cannot be part of a returned expression
**There may be an algebraic solution but, alas, I'm not an algebraist.**
Short of an immediate solution, you can use the general Binet formula with 2-degree polynomials and 2x2 matrices to get the closed form in terms of elementary functions:
def GBinet(c,d,a0,a1,n):
r1=2*d/(-c+sqrt(c^2+4*d))
r2=2*d/(-c-sqrt(c^2+4*d))
return ((a1-c*a0+a0*r1)*r1^n-(a1-c*a0+a0*r2)*r2^n)/sqrt(c^2+4*d)
sage: n=var('n')
sage: p(n)=GBinet(5,2,0,1,n)
sage: p(n)
-1/33*sqrt(33)*((-4/(sqrt(33) + 5))^n - (4/(sqrt(33) - 5))^n)
sage: p(5).n()
779.000000000000
- https://en.wikipedia.org/wiki/Binet_formula#Closed-form_expression
- https://gist.github.com/rwst/8525436
Mon, 28 Jul 2014 10:39:38 -0500http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/?answer=23613#post-id-23613Comment by rws for <p>Well looking at <code>[a^n for n in range(10)]</code> it's obviously a linear recurrence with the coefficients (5,2) the coefficients of <code>mp</code>, </p>
<p>a^n mod mp = p(n)*a+q(n), where p(n)=<a href="https://oeis.org/A015535">A015535(n)</a>, q(n)=2p(n-1)</p>
<p>and this generalizes to any polynomial. So, your question concerns two things:</p>
<ul>
<li>have Sage understand your problem. I don't think that simply giving the expression a^n mod mp should output
a closed form of that result. Rather, Sage would need a hint, like a command that takes that expression a^n and
the ring and returns an expression containing linear recurrence (linrec) objects,</li>
<li>Sage would need a linear recurrence object, this is <a href="http://trac.sagemath.org/ticket/15714">http://trac.sagemath.org/ticket/15714</a>, see also <a href="https://sites.google.com/site/cfinitesequenceforsage/">https://sites.google.com/site/cfinite...</a></li>
<li>to compute the values of degree-2 linrecs you can already use <code>lucas_number1</code> but this is no general solution, and it's not a symbolic function in Sage, so it cannot be part of a returned expression</li>
</ul>
<p><strong>There may be an algebraic solution but, alas, I'm not an algebraist.</strong></p>
<p>Short of an immediate solution, you can use the general Binet formula with 2-degree polynomials and 2x2 matrices to get the closed form in terms of elementary functions:</p>
<pre><code>def GBinet(c,d,a0,a1,n):
r1=2*d/(-c+sqrt(c^2+4*d))
r2=2*d/(-c-sqrt(c^2+4*d))
return ((a1-c*a0+a0*r1)*r1^n-(a1-c*a0+a0*r2)*r2^n)/sqrt(c^2+4*d)
sage: n=var('n')
sage: p(n)=GBinet(5,2,0,1,n)
sage: p(n)
-1/33*sqrt(33)*((-4/(sqrt(33) + 5))^n - (4/(sqrt(33) - 5))^n)
sage: p(5).n()
779.000000000000
</code></pre>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Binet_formula#Closed-form_expression">https://en.wikipedia.org/wiki/Binet_f...</a></li>
<li><a href="https://gist.github.com/rwst/8525436">https://gist.github.com/rwst/8525436</a></li>
</ul>
http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/?comment=23619#post-id-23619I have added the Binet formula (that's what Wolfram prints) to my answer.Tue, 29 Jul 2014 01:14:05 -0500http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/?comment=23619#post-id-23619Comment by Dirk Danckaert for <p>Well looking at <code>[a^n for n in range(10)]</code> it's obviously a linear recurrence with the coefficients (5,2) the coefficients of <code>mp</code>, </p>
<p>a^n mod mp = p(n)*a+q(n), where p(n)=<a href="https://oeis.org/A015535">A015535(n)</a>, q(n)=2p(n-1)</p>
<p>and this generalizes to any polynomial. So, your question concerns two things:</p>
<ul>
<li>have Sage understand your problem. I don't think that simply giving the expression a^n mod mp should output
a closed form of that result. Rather, Sage would need a hint, like a command that takes that expression a^n and
the ring and returns an expression containing linear recurrence (linrec) objects,</li>
<li>Sage would need a linear recurrence object, this is <a href="http://trac.sagemath.org/ticket/15714">http://trac.sagemath.org/ticket/15714</a>, see also <a href="https://sites.google.com/site/cfinitesequenceforsage/">https://sites.google.com/site/cfinite...</a></li>
<li>to compute the values of degree-2 linrecs you can already use <code>lucas_number1</code> but this is no general solution, and it's not a symbolic function in Sage, so it cannot be part of a returned expression</li>
</ul>
<p><strong>There may be an algebraic solution but, alas, I'm not an algebraist.</strong></p>
<p>Short of an immediate solution, you can use the general Binet formula with 2-degree polynomials and 2x2 matrices to get the closed form in terms of elementary functions:</p>
<pre><code>def GBinet(c,d,a0,a1,n):
r1=2*d/(-c+sqrt(c^2+4*d))
r2=2*d/(-c-sqrt(c^2+4*d))
return ((a1-c*a0+a0*r1)*r1^n-(a1-c*a0+a0*r2)*r2^n)/sqrt(c^2+4*d)
sage: n=var('n')
sage: p(n)=GBinet(5,2,0,1,n)
sage: p(n)
-1/33*sqrt(33)*((-4/(sqrt(33) + 5))^n - (4/(sqrt(33) - 5))^n)
sage: p(5).n()
779.000000000000
</code></pre>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Binet_formula#Closed-form_expression">https://en.wikipedia.org/wiki/Binet_f...</a></li>
<li><a href="https://gist.github.com/rwst/8525436">https://gist.github.com/rwst/8525436</a></li>
</ul>
http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/?comment=23616#post-id-23616Well, as a matter of fact, I think it should output a closed form. I'm approaching the question from a didactical point of view. It may well be that treating these questions as linear recurrences is a more fundamental point of view, but students and even many teachers are not aware of that.
I checked Wolfram Alpha, and that gives the closed form answer straight away. I just want to know how I can prod SAGE to do something along the same lines.Mon, 28 Jul 2014 13:32:52 -0500http://ask.sagemath.org/question/23610/symbolic-integer-arithmetic/?comment=23616#post-id-23616