Problem #416

Fifty-Fifty
Public 07/26/17 8xp Math 88.9%

Let $p_{4,3}(n)$ be the smallest prime $p$ such that $p > n$ and $p \equiv 3 \pmod{4}$ and let $$ p_{4,3}^k(n) := \begin{cases} p_{4,3}^{k-1}(p_{4,3}(n)) & \text{if } k > 1\\ p_{4,3}(n) & \text{if } k = 1 \end{cases}. $$

Let $F(n) := \frac{n - 1}{2}! \pmod{n}$ (i.e. the remainder of $\frac{n-1}{2}!$ divided by $n$).

For example, $F(3) = 1$ and $F(47) = 46$.

Let $S(n, m) := \sum_{k=1}^{m} F(p_{4,3}^{k}(n))$.

You are given $S(1, 32) = 1856$, $S(10^7, 32) = 150008239$ and $S(10^{12}, 32) = 18000000012930$.

Find $S(10^{18}, 32)$.

[My timing: 1.8 seconds (PyPy)]

Note: It would be hard without parigp.




You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]