Project Euler #1

Project Euler #1

---

• 문제
  • 풀이 1
  • 풀이 2
  • 풀이 3
  • 풀이 4
• 후기

문제

---

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.

10미만의 자연수 중 모든 3의 배수와 5의 배수의 합은 23.(3, 5, 6, 9)

1000미만의 자연수 중 모든 3의 배수와 5의 배수의 합은 얼마인가?

풀이 1

---

• func라는 함수를 구현해서 결과를 출력하도록 했다.

import time
def func(num):
    rs = 0
    for i in range(1,num):
        if i % 3 == 0 or i % 5 == 0: #3의 배수, 5의 배수에 해당 되는 수만 걸러낸다.(15의 배수를 포함)
            rs += i
    return rs

stime = time.time()
print(func(1000))
print(time.time() - stime)

풀이 2

---

• 풀이 1이 너무 길어 sum()을 이용하여 한줄로 작성했다.

import time
stime = time.time()

sum(x for x in range(1,1000) if x %3 ==0 or x % 5 == 0)
print(time.time() - stime)

풀이 3

---

• 문제는 $n$ 미만의 $x$ 의 배수 집합( $A$ )과 $y$ 의 배수의 집합( $B$ )의 합집합( $A \cup B$ )의 원소들의 합을 구하는 것이다.

• 집합에서 집합 $A$ 와 집합 $B$ 의 합집합은 $A \cup B = A + B - A \cap B$ 이다.

• 따라서, ( $x$ 의 배수의 합) $+$ ( $y$ 의 배수의 합) $-$ ( $x, y$ 의 최소공배수의 합) 이다.
  $\displaystyle \sum_{k_{1} = 1}^{q_{1}}{xk_{1}} + \sum_{k_{2} = 1}^{q_{2}}{yk_{2}} - \sum_{k_{3} = 1}^{q_{3}}{\operatorname{lcm}(x, y)k_{3}}$

• 최소공배수는 주어진 수를 소인수 분해한 결과 중 소수의 지수가 큰 수들을 곱한 값이다.
  $x=n_{1}^{2} \times {\color{Red}n_{2}^{4}} \times {\color{Red}n_{3}} \\ y={\color{Red}n_{1}^{5}} \times n_{2}^{2} \times {\color{Red}n_{4}^{2}} \\ \operatorname{lcm}(x, y) = {\color{Red}n_{1}^{5}} \times {\color{Red}n_{2}^{4}} \times {\color{Red}n_{3}} \times {\color{Red}n_{4}^{2}}$

• 이 문제에 적용시키면 아래와 같다.
  $x=3^{1}, \; y=5^{1}\\ \operatorname{lcm}(x, y) = 3^{1} \times 5^{1} = 15\\$

import time
stime = time.time()
sum3 = sum(range(3, 1000, 3))
sum5 = sum(range(5, 1000, 5))
sum15 = sum(range(15, 1000, 15))

sum3 + sum5 - sum15
print(time.time() - stime)

풀이 4

---

• 풀이 3을 좀 더 진행시키면 다음과 같다.

• $1, 2, \dots , n$ 의 합은 다음과 같은 식으로 유도된다.
  $\begin{matrix} & \displaystyle \sum_{k=1}^{n}k & = & 1 + 2 + 3 + \cdots + (n - 2) + (n -1) + n \\ + & \displaystyle \sum_{k=1}^{n}k & = & n + (n -1) + (n - 2) + \cdots + 3 + 2 + 1 \\ \end{matrix} \\ \overline{\begin{matrix} 2 \displaystyle \sum_{k=1}^{n}k & = &(n + 1) + (n - 1 + 2) + (n - 2 + 3) + \cdots + (n - 2 + 3) + (n -1 + 2) + (n + 1) \\ & = & (n + 1) + (n + 1) + (n + 1) + \cdots + (n + 1) + (n + 1) + (n + 1) \\ & = & n(n + 1) \end{matrix}} \\ \therefore \quad \displaystyle \sum_{k=1}^{n}k = \frac{n(n + 1)}{2}$

• 이 문제에 적용시키면 아래와 같다.
  $\begin{matrix} & \displaystyle \sum_{k_{1} = 1}^{q_{1}}{xk_{1}} + \sum_{k_{2} = 1}^{q_{2}}{yk_{2}} - \sum_{k_{3} = 1}^{q_{3}}{\operatorname{lcm}(x, y)k_{3}} \\ = & \displaystyle x\sum_{k_{1} = 1}^{q_{1}}{k_{1}} + y\sum_{k_{2} = 1}^{q_{2}}{k_{2}} - \operatorname{lcm}(x, y)\sum_{k_{3} = 1}^{q_{3}}{k_{3}} \\ = & \displaystyle x\frac{q_{1}(q_{1} + 1)}{2} + y\frac{q_{2}(q_{2} + 1)}{2} - \operatorname{lcm}(x, y)\frac{q_{3}(q_{3} + 1)}{2} \end{matrix}\\ x=3^{1}, \; y=5^{1}\\ \operatorname{lcm}(x, y) = 3^{1} \times 5^{1} = 15\\ \begin{matrix} n = 3 & \to & 999 = nq_{1} + r = & 3q_{1} + r & \therefore & q_{1} = 333,& r = 0 \\ n = 5 & \to & 999 = nq_{2} + r = & 5q_{2} + r & \therefore & q_{2} = 199,& r = 4 \\ n = 15 & \to & 999 = nq_{3} + r = & 15q_{3} + r & \therefore & q_{3} = 66,& r = 9 \\ \end{matrix} \\ \displaystyle \implies x\frac{q_{1}(q_{1} + 1)}{2} + y\frac{q_{2}(q_{2} + 1)}{2} - \operatorname{lcm}(x, y)\frac{q_{3}(q_{3} + 1)}{2}\\ = \displaystyle 3\frac{333(333 + 1)}{2} + 5\frac{199(199 + 1)}{2} - 15\frac{66(66 + 1)}{2}$

import time
nsum = lambda n: n*(n+1)/2
stime = time.time()

q1 = 999 // 3
q2 = 999 // 5
q3 = 999 // 15

3*nsum(q1) + 5*nsum(q2) - 15*nsum(q3)
print(time.time() - stime)

후기

1번 문제라 난도가 낮다.
하지만, 풀이법이 다양하여 Project Euler가 추구하는 방향성을 확실히 보여주는 문제라고 생각한다.
1번 문제일 만하다.