(prime - k) Factorial

Problem

Problem Link

Calculate $S(p)={\sum }_{k=1}^5(p-k)!\mathrm{mod}p$ for primes $p\ge 5$.

Solution

First, simplify the sum modulo $p$.

• $(p-1)!+(p-2)!=(p-2)!(p)\equiv 0(\mathrm{mod}p)$
• $(p-3)!+(p-4)!+(p-5)!=(p-5)!(p^2-6p+9)\equiv 9(p-5)!(\mathrm{mod}p)$

Thus, $S(p)\equiv 9(p-5)!(\mathrm{mod}p)$.

By Wilson’s Theorem, $(p-1)!\equiv -1(\mathrm{mod}p)$.

Expanding $(p-1)!$ gives:

$(p-1)(p-2)(p-3)(p-4)(p-5)!\equiv 24(p-5)!(\mathrm{mod}p)$

So, $24(p-5)!\equiv -1(\mathrm{mod}p)⟹(p-5)!\equiv -24^{-1}(\mathrm{mod}p)$.

Now, let’s combine this and solve for $S(p)$:

$S(p)\equiv 9(-24^{-1})\equiv -\frac{3}{8}\equiv -3\cdot 8^{-1}(\mathrm{mod}p)$

You can compute $8^{-1}(\mathrm{mod}p)$ in $O(1)$ time using Fermat’s Little Theorem ($8^{p-2}\mathrm{mod}p$) or precomputed values based on $p\mathrm{mod}8$.

CodeCPP fileDownload

#include <iostream>
#include <vector>
 
std::vector<int> generate_primes(int n) {
  std::vector<bool> is_prime(n + 1, true);
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  std::vector<int> primes;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      primes.push_back(i);
    }
  }
  return primes;
}
 
long long s(long long p) {
  long long rem = p % 8;
  if (rem == 1) return (-3 + 3 * p) / 8;
  if (rem == 3) return (-3 + p) / 8;
  if (rem == 5) return (-3 + 7 * p) / 8;
  return (-3 + 5 * p) / 8;
}
 
int main(void) {
  std::vector<int> primes = generate_primes(100000000);
 
  long long ans = 0;
  for (int p : primes) {
    if (p < 5) continue;
    ans += s(p);
  }
  std::cout << ans << std::endl;
 
  return 0;
}