Project Euler Problem 809
The following is a function defined for all positive rational values of x.
Solution
Answer: 75353432948733
Let
$$g_m(n)=f!\left(n+\frac1m\right).$$
From the definition of $f$, for $m>1$,
$$f!\left(n+\frac1m\right) = f!\left( \frac1{1-\frac1m}-1+f!\left(n-1+\frac1m\right) \right).$$
Since
$$\frac1{1-\frac1m}-1=\frac1{m-1},$$
we obtain the recurrence
$$g_m(n)=g_{m-1}(g_m(n-1)).$$
Also:
$$g_1(n)=f(n+1)=n+1.$$
Now build the first few functions:
- $g_2(n)=n+2$
- $g_3(n)=2n+3$
- $g_4(n)=2^{n+3}-3$
Define
$$T_0=16,\qquad T_{k+1}=2^{T_k}.$$
Then
$$g_5(n)=T_n-3.$$
The values explode extremely quickly. Modulo $10^{15}$, iterating
$$x \mapsto 2^x \pmod{10^{15}}$$
rapidly reaches the fixed point
$$L=75353432948736,$$
since
$$2^L \equiv L \pmod{10^{15}}.$$
Hence for any sufficiently large input,
$$g_5(n)\equiv L-3 \pmod{10^{15}}.$$
Now:
$$f!\left(\frac{22}{7}\right)=g_7(3),$$
and already the intermediate arguments are astronomically large, so every subsequent application stabilizes to the same residue:
$$g_7(3)\equiv L-3.$$
Therefore
$$f!\left(\frac{22}{7}\right)\equiv 75353432948733 \pmod{10^{15}}.$$
Answer: 75353432948733