10

Is there a simple way to implement !n mod p (number of derangements) where n ≤ 2∗10^8 and p is a prime and p < 1000

The program must execute fast so the naive approach doesn't work.

  • @SteveJessop is that the same as in the link? – Luchian Grigore Oct 16 '12 at 12:02
  • @Luchian: yes, the subfactorial is the number of derangements. – Steve Jessop Oct 16 '12 at 12:02
  • @LuchianGrigore - not apparently, that is what it means. I don't know why you reverted my edit... Obviously he doesn't want to calculate not n mod p. If you want just remove the c++ tag, it has nothing to do with that. – IVlad Oct 16 '12 at 12:02
  • Have you tried anything? You can read this one: http://stackoverflow.com/questions/9727962/fast-way-to-calculate-n-mod-m-where-m-is-prime – alestanis Oct 16 '12 at 12:04
  • Out of curiousity, which SPOJ question would this happen to be? – Nabb Oct 16 '12 at 12:11
  • @alestanis I'm looking for !n not for n! –  Oct 16 '12 at 12:12
  • 1
    Since `p < 1000`, it might be worth investigating if derangements are periodic mod `p`. For example, the first few `1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932` are periodic mod `2` with a period of 2: odd even odd even ...; I'm pretty sure this holds forever and for other numbers too – IVlad Oct 16 '12 at 12:12
  • 1
    `!n mod p` appears to be periodic with period `2p` (for odd p), so this gives a straightforward algorithm to compute the required value. You might want to try proving the periodicity though. – Nabb Oct 16 '12 at 12:13
  • @Nabb It's on polish spoj http://pl.spoj.pl/problems/LETTERS5/ –  Oct 16 '12 at 12:13
  • @BugMeNot I find there's this relation that works. `!n = floor(n!/e)`. Recursive factorial would take O(log N). – venkatKA Oct 16 '12 at 12:15
  • @zander: that formula is fine if you want a floating-point result but doesn't really help compute the value modulo `p` (you can't compute `floor(k/e) mod p` by knowing `k mod p`). – Steve Jessop Oct 16 '12 at 12:16
  • @zander it won't work since i have first divide within Real numbers, and therefore can't mod n! to reduce it. Mod is defined only for integers. –  Oct 16 '12 at 12:18
  • Yep, for p = 3 sequence is 1, 2 ,0, 2, 1, 0, 1, 2, 0; for p = 5 is 1, 0, 1, 2, 4, 4, 0, 4, 3, 1, 1, 0, 1, 2, 4 ... –  Oct 16 '12 at 12:47

2 Answers2

8

It turns out that !n mod p is periodic with a period of 2p. Thus we can compute !n mod p as !(n mod 2p) mod p, which we do with the recursive formula for derangements !n = (n-1) (!(n-1) + !(n-2)).

For a proof:

  • Observe that !(p+1) = 0 mod p, by the recursive relation for derangements.
  • Working modulo p, !(n+p) = !p * !n (this can be proved inductively using the previous observation).
  • Observe that !p = -1 mod p. Wikipedia provides a formula: !n = n! - Sum[(n choose i) * !(n-i), i=1..n] -- modulo p, the only nonzero term on the right hand side appears where i=n.
  • Conclude that !(n+2p) = !p !p !n = !n mod p.

From the proof, we see that we can in fact compute !n = ± !(n mod p) mod p where the sign is positive when n mod 2p is less than p.

Nabb
  • 3,434
  • 3
  • 22
  • 32
0

Having the recursive formula (!n = (n - 1) (!(n-1) + !(n-2))), why not implement the operations "multiplication modulo p" and "addition modulo p"?

Vlad
  • 35,022
  • 6
  • 77
  • 199
  • For `n` that large? Way too slow. – IVlad Oct 16 '12 at 12:03
  • @Vlad: too slow I'd think, since it might require approx 400M operations. – Steve Jessop Oct 16 '12 at 12:03
  • execute time is around 0,2s n multiplications would take way too long. I believe that there's some clever way to reduce problem, because p limit is p < 1000. –  Oct 16 '12 at 12:08
  • 1
    @BugMeNot - that's a pretty important restriction! Please add it to the OP, together with any other information. – IVlad Oct 16 '12 at 12:09
  • On consideration though this relation is probably a valid way forward. If you memoize the function `f(a,b,c) { return (a-1)(b + c) % p}`, then you need at worst a billion values given `p < 1000`. But Nabb observes above that `!n mod p` appears to be cyclic with shorter period than that, so actually you need rather fewer. Throw in some cycle-detection too, and you can probably get the value quite quickly. And that's without doing any maths -- *proving* some nice formula like `2*p` for the cycle length ahead of time would be preferable but probably not necessary given a 0.2s time constraint :-) – Steve Jessop Oct 16 '12 at 12:26
  • @Steve: Memoizing a function that does only 3 arithmetic operations? Really? ;) – Niklas B. Oct 28 '12 at 19:24