\documentclass{article}
\usepackage{fancyhdr}
\usepackage{amsmath ,amsthm ,amssymb}
\usepackage{graphicx}
\usepackage{listings}

\begin{document}

This is slightly cheating because I picked this problem, and I really liked my
approach. I know that this can be solved by brute force, but it's incredibly ugly.

First let's define a function $d_k(x)$, that returns the $k$ least significant digits of $x$.

\begin{align}
	\nonumber
	d_1(0)& =0\\
	\nonumber
	d_1(14)& =4\\
	\nonumber
	d_2(14)& =14
\end{align}

This is really just the $mod$ function is a different form. Just a bit more terse.

\[ d_k(x) = x \bmod 10^k \]

This function has some identities that are useful for this problem. I won't
prove them.

\begin{align}
	\label{eq:multid}
	d_k(Cx) &= d_k(d_k(C) \cdot d_k(x))\\
	\label{eq:addid}
	d_k(C + x) &= d_k(d_k(C) + d_k(x))
\end{align}

Problem 97 asks us to produce the following:

\[
	d_{10}(28433 \cdot 2^{7830457} + 1)
\]

The identities \eqref{eq:multid} and \eqref{eq:addid} can help us break this
down into something slightly more manageable.

\begin{align}
	\nonumber
	A &= d_{10}(28433 \cdot 2^{7830457} + 1)\\
	\nonumber
	  &= d_{10}(d_{10}(28433) \cdot d_{10}(2^{7830457}) + d_{10}(1))\\
	  \label{eq:euler97}
      &= d_{10}(28433 \cdot d_{10}(2^{7830457}) + 1)
\end{align}

$d_{10}(2^{7830457})$ is a waste to compute. Though the identity \eqref{eq:multid} can be used to do some interesting modulus optimizations,
I'd rather find a more elegant solution.

Let's look at powers of two in more depth. Consider the powers of 2:

\[ 2^x = 1, 2, 4, 8, 16, 32, 64, 128, 256, \ldots \]

There is a pattern here when considering just the least signficant digit.

\[ d_1(2^x) = 1, 2, 4, 8, 6, 2, 4, 8, 6, \ldots \]

This sequence is eventually periodic, with period $4$.

\[ P(d_1(2^x)) = 4 \]

Using a short Haskell function, I found the periods for the first four digits of $2^x$:

\begin{align}
	\nonumber
	P(d_{1}(2^x)) &= 4\\
	\nonumber
	P(d_{2}(2^x)) &= 20\\
	\nonumber
	P(d_{3}(2^x)) &= 100\\
	\nonumber
	P(d_{4}(2^x)) &= 500
\end{align}

The periodicity looked like it could be generalized.

\begin{align}
	\label{eq:periodicity}
	P(d_k(2^x)) &= 4 \cdot 5^{k - 1}\\
	\label{eq:specificperiod}
	P(d_{10}(2^x)) &= 7812500
\end{align}

This number looks promising. Because $d_k(2^x)$ is not strictly periodic, but only eventually periodic, we aren't guaranteed that $d_k(2^x) = d_k(2^{x - P(d_k(2^x))})$. All we can do it just guess and check.



\begin{align}
	\nonumber
	A &= d_{10}(28433 \cdot d_{10}(2^{7830457}) + 1)\\
	\nonumber
	  &= d_{10}(28433 \cdot d_{10}(2^{7830457 - 7812500}) + 1)\\
	\nonumber
	  &= d_{10}(28433 \cdot d_{10}(2^{17957}) + 1)\\
	\label{eq:solution}
	  &= (28433 \cdot (2^{17957} \bmod 10^{10}) + 1) \bmod 10^{10}
\end{align}

This final formula \eqref{eq:solution} is much easier to compute.

\end{document}