1 | initial version |

Well looking at `[a^n for n in range(10)]`

it's obviously a linear recurrence with the coefficients (5,2) the coefficients of `mp`

, 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 a linear recurrence (linrec) object,
- 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`

There may be an algebraic solution but, alas, I'm not an algebraist.

2 | No.2 Revision |

Well 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), 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 a linear recurrence (linrec) object,
- 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`

There may be an algebraic solution but, alas, I'm not an algebraist.

3 | No.3 Revision |

Well 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), 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
~~a~~an expression containing linear recurrence (linrec)~~object,~~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`

There may be an algebraic solution but, alas, I'm not an algebraist.

4 | No.4 Revision |

Well 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), 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,
- 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.**

5 | No.5 Revision |

`[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), 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,
- 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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.