#11802: Generation of Lucas sequences modulo an integer
--------------------------------+-------------------------------------------
Reporter: somindu | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: minor | Milestone: sage-4.7.2
Component: basic arithmetic | Keywords: Lucas sequence
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
--------------------------------+-------------------------------------------
Comment(by somindu):
Add the patches for function {{{lucas(k,p,q,n)}}} which generates Lucas
sequence V_k mod n (k >= 0) defined by {{{V_k = PV_{k-1} - QV_{k-2} with
V_0 = 2 and V_1 = P}}}.
Tests::
{{{
sage: from sage.rings.finite_rings.integer_mod import lucas
sage: p = randint(0,100000)
sage: q = randint(0,100000)
sage: n = randint(0,100)
sage: all([lucas(k,p,q,n)[0] == Mod(lucas_number2(k,p,q),n)
... for k in Integers(20)])
True
}}}
{{{
sage: from sage.rings.finite_rings.integer_mod import lucas
sage: p = randint(0,100000)
sage: q = randint(0,100000)
sage: n = randint(0,100)
sage: k = randint(0,100)
sage: lucas(k,p,q,n) ==
[Mod(lucas_number2(k,p,q),n),Mod(q^(int(k/2)),n)]
True
}}}
Examples::
{{{
sage: [lucas(k,4,5,11)[0] for k in range(30)]
[2, 4, 6, 4, 8, 1, 8, 5, 2, 5, 10, 4, 10, 9, 8, 9, 7, 5, 7, 3, 10,
3, 6, 9, 6, 1, 7, 1, 2, 3]
sage: lucas(20,4,5,11)
[10, 1]
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11802#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
