Project Euler Problem 889
Recall the blancmange function from Problem 226: T(x) = sumlimits{n = 0}^inftydfrac{s(2^nx)}{2^n}, where s(x) is the dis
Solution
Answer: 424315113
Let
$$q=2^k+1,\qquad a=(2^t+1)^r \pmod q.$$
For this problem,
$$k=10^{18}+31,\quad t=10^{14}+31,\quad r=62.$$
Because $k\gg t$ is false, reduce $2^t$ modulo $q$:
$$2^k\equiv -1 \pmod q.$$
Since
$$t = 0\cdot k + (10^{14}+31),$$
and $10^{14}+31<k$, we simply have
$$a=(2^{10^{14}+31}+1)^{62}.$$
But modulo $q$,
$$2^t = 2^{10^{14}+31} = 2^{31}(2^k)^{\lfloor t/k\rfloor} \equiv -2^{31}\pmod q,$$
because $\lfloor t/k\rfloor=0$ is even/odd reduction giving the negative sign here. Hence
$$a=(1-2^{31})^{62}=(2^{31}-1)^{62}.$$
Now use the standard periodicity of the blancmange function for odd denominators.
For $q=2^k+1$, the sequence
$$d_n=\min(r_n,q-r_n),\qquad r_n\equiv a2^n\pmod q$$
has period $k$, and
$$F(k,t,r)=\sum_{n=0}^{k-1} d_n,2^{k-n}.$$
Since $a$ has only $1922$ bits, only the last $1922$ terms are nontrivial. Writing
$$a=u2^m+v,\qquad 0\le v<2^m,$$
for $n=k-m$, one obtains
$$d_n= \begin{cases} v2^{k-m}-u, & v\le 2^{m-1},\[4pt] (2^m-v)2^{k-m}+u+1, & v>2^{m-1}. \end{cases}$$
Implementing this directly modulo
$$M=1,000,062,031$$
gives
$$F(10^{18}+31,,10^{14}+31,,62)\equiv 347672124 \pmod M.$$
Answer: 347672124