f(Λ)

ProjectEuler - Problem 001

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:

W−maximal value, here 1000 mj=⌊log⁡jW⌋ i,j−exponents, here 3,5 ki,kj∈N;exponents for i,j;kx<=mx \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 iki⋅jkj<Wi^{k_i} \cdot j^{k_j} < W is always valid.

As log⁡\log is a strict monotonic function, we can change this to

iki⋅jkj<W ki⋅log⁡i(i)+kj⋅log⁡i(j)<logi(W) ki<logi(W)−kj⋅log⁡i(j) mi(j)=⌊logi(W)−kj⋅log⁡i(j)⌋ \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:

L=∑a=0mj∑b=0mi(a)ja⋅ib =∑a=0mjja⋅∑b=0mi(a)ib \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:

∑i=0nki=kn+1−1k−1 \sum_{i=0}^n k^i = \frac{k^{n+1}-1}{k-1}

which results in

L=∑a=0mjja⋅imi(a)+1−1i−1 =−1i−1⋅∑a=0mjja+ii−1⋅∑a=0mjja⋅imi(a) =−1i−1⋅(jmj+1−1j−1)+ii−1⋅∑a=0mjia⋅log⁡i(j)+mi(a) \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=−1i−1⋅(jmj+1−1j−1)+i⋅Wi−1⋅∑a=0mji−{logi(W)−a⋅log⁡i(j)} 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!

Published

Category

projecteuler