what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

Solution 1:

Just to compose table:

\begin{array}{|c|r|} \hline n! & \equiv \ldots (\bmod \:47) \\ \hline \\ 1! & 1 \\ 2! & 2\cdot 1 = 2 \\ 3! & 3 \cdot 2 = 6 \\ 4! & 4 \cdot 6 = 24 \\ 5! & 5 \cdot 24 = 120 \equiv 26 \\ 6! & 6 \cdot 26 = 156 \equiv 15 \\ 7! & 7 \cdot 15 = 105 \equiv 11 \\ \cdots \\ 44! & 44 \cdot 8 = 352 \equiv 23 \\ 45! & 45 \cdot 23 = 1035 \equiv 1 \\ \hline \end{array}

$45$ steps/rows in total.

Then to find sum: $S = 1+2+6+24+26+15+11+\ldots+23+1 = \color{#E0E0E0}{1052 \equiv 18 (\bmod \: 47)}$.

Here we use idea:
if $\qquad$ $k! \equiv s (\bmod \: p)$,
then $\;$ $(k+1)! \equiv (k+1)\cdot s (\bmod \: p)$,
and apply it step-by-step.

Solution 2:

If you write the sum backwards you get

$45! + 44! + 43! + ... + 1! = (((···(45+1)44+1)43+1)···+1)2+1$

This creates the sequence

$t_0 = 45, \quad t_{n+1} = (t_n+1)(t_0-n)$

where we wish to find the value of $t_{44}$

This will take $44$ multiplications and $88$ additions, which seems pretty efficient.

Doing the arithmetic modulo $47$, I got $t_{44} \equiv 18 \pmod{47}$.

 n  t[n]     n  t[n]     n  t[n]     n  t[n]     n  t[n]
 0    45     9    44    18    38    27    46    36    18
 1     3    10    24    19    27    28     0    37    11
 2    31    11     4    20    42    29    16    38    37
 3    28    12    24    21    45    30    20    39    40
 4    14    13     1    22    24    31    12    40    17
 5    36    14    15    23    33    32    28    41    25
 6    33    15    10    24     9    33    19    42    31
 7    23    16    37    25    12    34    32    43    17
 8    42    17    30    26    12    35     1    44    18