\documentclass[12pt,notitlepage]{article}

\usepackage{hyperref}

\title{Project Euler: Problem 1
\\\small{\url{https://projecteuler.net/problem=1}}\\
\small{\url{https://github.com/oltdaniel/euler}}}

\begin{document}
  \maketitle

  \begin{center}
    \textit{"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000."}
  \end{center}

  The general idea would be to have an loop counting from 1 to below 1000. As this is still
  fast on most of the machines, as the range is pretty low, higher ranges will take way more
  computation time.\par

  As only the sum is required as an result and not each number on its own, this routine can
  be heavily optimized by some simple math. But let us start with the general algorithm idea.

  \subsection{Basic idea}
  The basic idea to solve this, is counting from $1$ to below $1000$ and check each number, if it is
  evenly divisble by 3 or 5. At this point it is important to take care of the numbers evenly
  divisble by 15, as this numbers will be both evenly divisble by $3$ and $5$ too.\par
  \textbf{Complexity: $O(n - 1)$}

  \subsection{Bigger steps}
  The algorithm described above will increment the number by $1$, which is actually very
  useless, as we know that numbers only numbers that are multiples of $3$ and $5$ will be significant
  to the result. So on, we can divide the code into to separate loops, counting one from $3$ below
  the limit $1000$  and increment it each time by $3$, and another one from $5$ below $1000$
  with incrementing the number each time by $5$.\par
  \textbf{Complexity: $O(\lceil n \div 3 \rceil + \lceil n \div 5 \rceil)$}

  \subsection{Reduce calculation}
  The general calculation done here is adding all numbers that are multiples of $3$ and $5$ that
  are below $1000$. This sequence of numbers can be combined into triangular numbers, that are described
  by the function $f(n) = n ( n + 1 ) \div 2$.\par

  However, as we want the sum of these numbers, we can mix
  up the formulat to inject a new parameter called $d$ to introduce the divisor. This will result
  in replacing $n$ with $n \div d$, the number of possible multiples, and multipling everything by $k$ in order to sum the amount of
  possible multiples by their actual value (the $y$-th multiple of the $x$-th number is $y * x$).\par

  The function $f$ will now be written as $f(n, d) = d * (n \div d) * (n \div d + 1) \div 2$. As this
  will not take care of the double counted multiples of $15$, we need to substract these of the sum.\par

  \textbf{Complexity: $O(1)$}

\end{document}
