I'm playing around with implementing the Lucas probable prime test (mainly so I can understand it better), and would love a version of the LinearRecurrence function that used addition modulo n (with n supplied by the user) instead of ordinary addition (which can easily result in overflows).

It wouldn't be all that crazy-hard to implement one, I think, and might even be quite interesting to do, but I thought I'd ask whether anyone already knows of such a thing.

  • 1
    $\begingroup$ A concrete example, with input and desired output, would be useful here. $\endgroup$ – Daniel Lichtblau Sep 7 '20 at 14:27
  • $\begingroup$ There isn't a built-in function, but you might be interested in the undocumented function Algebra`MatrixPowerMod[], which might help in your implementation. $\endgroup$ – J. M.'s torpor Sep 10 '20 at 11:17
  • $\begingroup$ Oh, wow--I think that's almost certainly going to do the trick. Thanks so much! $\endgroup$ – Phil Ramsden Sep 11 '20 at 12:29
  • $\begingroup$ p = NextPrime[10^100]; Mod[(Algebra`MatrixPowerMod[{{0, 1}, {1, 1}}, p -2 - JacobiSymbol[p, 5], p].{1, 1})[[2]], p] returns 0, very quickly; exactly what I was trying to do. That's Fibonacci; adapting to other recurrence relations will be a breeze. Thanks again. $\endgroup$ – Phil Ramsden Sep 11 '20 at 13:14

You can build your own "LinearRecurrence" and then use any function you like. Here is an example from MMA help:

LinearRecurrence[{a, b}, {1, 1}, 5]

this gives:

{1, 1, a + b, b + a (a + b), b (a + b) + a (b + a (a + b))}

We can do the same by:

Reap[Nest[(Sow[t = #.{b, a}]; {#[[2]], t}) &, {1, 1}, 3] ]

To introduce Mod, you would write:

Reap[Nest[(Sow[t =Mod[ #.{b, a},n]; {#[[2]], t}) &, {1, 1}, 3] ]
  • $\begingroup$ Your answer might be improved for the OP & future users if you can link to the “MMA help” page you pull this from. $\endgroup$ – CA Trevillian Sep 7 '20 at 21:06
  • $\begingroup$ Hi, thanks for this! I realise I need to clarify. The thing is, my guess is that LinearRecurrence uses some clever stuff to cope with large n, probably based on repeated doubling of the index. My n will be large, so my programming task would involve duplicating that clever stuff, rather than simply nesting (n-2) times. That's doable, but I wondered if anyone had already done it. $\endgroup$ – Phil Ramsden Sep 8 '20 at 15:09
  • $\begingroup$ So for example LinearRecurrenceMod[{1,1},{1,1},10^100+1,10^100] would return the googol-plus-oneth Fibonacci number, reduced mod googol. Kind of like a LinearRecurrence version of PowerMod, if you take my meaning. $\endgroup$ – Phil Ramsden Sep 8 '20 at 15:14
  • $\begingroup$ (At least, it's doable for second order recurrence relations, via Lucas U and V sequences; not sure if that generalises; number theory's not really my comfort zone.) $\endgroup$ – Phil Ramsden Sep 8 '20 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.