Hi,
maybe some of you guys know Project Euler already, if not, please follow the link and read a bit about it.
It is a collection of interesting mathematical problems.
This is my take on the first problem:
Find the sum of all the multiples of 3 or 5 below 1000
While this is a one line problem in python:
print ( sum ([ 0 if i % 3 and i % 5 else i in range ( 1000 )]))
solving this analytically is challenging.
This is how far I got:
\begin{align}
W &- \textrm{maximal value, here } 1000 \\\
m_j &= \lfloor \log_j W \rfloor \\\
i, j &- \textrm{exponents, here }3, 5 \\\
k_i, k_j &\in N; \textrm{exponents for }i, j; k_x <= m_x
\end{align}
wherefore
i^{k_i} \cdot j^{k_j} < W
is always valid.
As
\log
is a strict monotonic function, we can change this to
\begin{align}
i^{k_i} \cdot j^{k_j} &< W \\\
k_i \cdot \log_i \left(i\right) + k_j \cdot \log_i \left(j\right) &< log_i \left(W\right)\\\
k_i &< log_i \left(W\right) - k_j \cdot \log_i \left(j\right) \\\
m_{i} \left( j \right) &= \lfloor log_i \left(W\right) - k_j \cdot \log_i \left(j\right) \rfloor
\end{align}
So the needed value can be defined as:
\begin{align}
L &= \sum_{a=0}^{m_j} \sum_{b=0}^{m_i\left(a\right)} j^a \cdot i^b \\\
&= \sum_{a=0}^{m_j} j^a \cdot \sum_{b=0}^{m_i\left(a\right)} i^b
\end{align}
Now, apply this summation formula:
\sum_{i=0}^n k^i = \frac{k^{n+1}-1}{k-1}
which results in
\begin{align}
L &= \sum_{a=0}^{m_j} j^a \cdot \frac{i^{m_i \left(a\right)+1}-1}{i-1} \\\
&= \frac{-1}{i-1} \cdot \sum_{a=0}^{m_j} j^a + \frac{i}{i-1} \cdot \sum_{a=0}^{m_j} j^a \cdot i^{m_i \left(a\right)} \\\
&= \frac{-1}{i-1} \cdot \left(\frac{j^{m_j + 1}-1}{j-1} \right) + \frac{i}{i-1} \cdot \sum_{a=0}^{m_j} i^{a \cdot \log_i \left( j \right) + m_i \left(a\right)} \\
\end{align}
well… and this is how far I got. I could reformulate it to:
L = \frac{-1}{i-1} \cdot \left(\frac{j^{m_j + 1}-1}{j-1} \right) + \frac{i \cdot W}{i-1} \cdot \sum_{a=0}^{m_j} i^{- \{log_i \left(W\right) - a \cdot \log_i \left(j\right)\}}
with
\{ \}
as the frac function . I have no idea how to proceed from here. :(
So if you see an error or have an idea, please write me!
I also found a different solution here: Muvik.de but I really like to know how to solve my problem!