Project Euler #6-10
Continuing on from the Project Euler Challenge, we look at the next 5 problems in the set.
Problem 6
High level idea: Find the absolute difference between the sum of the squares of the first \(N\) natural numbers and the square of the sum.
Input: \(T+1\) lines of integers. As always, the first line contains \(T\) that denotes the number of test cases. This is followed by \(T\) lines, each containing an integer, \(N\).
Constraints:
\[1 \leq T \leq 10^4\] \[1 \leq N \leq 10^4\]Solution
This problem requires us to find the difference between the square of a sum and the sum of squares. We break down the problem into two parts: 1) Finding the arithmetic progression up to \(N\) and squaring the result, and 2) finding the sum of squares.
Sub-problem 1 looks simple: we can easily obtain the arithmetic progression of a number (as done in the first Euler problem), using the formula \(S_{n}=\frac{n}{2}(2a+(n-1).d)\). As common difference \(d = 1\) and first term \(a = 1\), we can rewrite the formula to \(S_{n}=\frac{n}{2}(n+1)\). Code implementation below uses bit-shift operation to effectively divide by two without having to type-cast the float result back to int.
def ap(n):
return (n * (n+1))>>1
For sub-problem 2, it is more time-efficient to save the results of sum of squares in a dictionary, reminiscent of the \(5^{th}\) Euler problem). The calculation of the sum of squares is trivial, with no optimization tricks for this solution.
In the code implementation below, we save a list of sum of squares, sum_squares, that satisfies the problem for \(N =\) max_n. We iteratively build up the array up to the maximum value of n we have pre-computed, max_n.
def build_arr(n, max_n):
if max_n < n:
i = max_n
while i < n:
i += 1
sum_squares[i] = sum_squares[i-1] + i*i
max_n += 1
return max_n
For the main function, we simply build the array up to the value of \(N\) we need, and return the difference as required.
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
if max_n < n:
max_n = build_arr(n, max_n)
print(ap(n)*ap(n) - sum_squares[n])
This solution is rather straight-forward, employing only the AP formula to speed things up.
Futher improvements
After a cursory Google search, I found a formula for calculating the sum of squares \(S_{n}=\frac{n}{6}(n+1)(2n+1)\), which worked like a charm (and is trivial to implement in code):
def ap_sq(n):
return int((n * (n+1) * (2*n+1))/6)
Overall, this problem seeks to train one more so in mathematical thinking than algorithmic optimization.
Problem 7
High level idea: Find the \(N^{th}\) prime number.
Input: \(T+1\) lines of integers. As always, the first line contains \(T\) that denotes the number of test cases. This is followed by \(T\) lines, each containing an integer, \(N\).
Constraints:
\[1 \leq T \leq 10^3\] \[1 \leq N \leq 10^4\]Solution
This problem requires us to efficiently compute prime numbers. Generating a list of primes was covered in the third Euler problem, and primarily consists of a helper method is_prime that checks if a given number is a prime number (remember that we up to \(\sqrt{n}\), check out the previous post for more details), and another, get_primes, that builds up the list up to a required \(N\).
def is_prime(n, primes):
sqrt_n = int(math.sqrt(n))
for prime in primes:
if n % prime == 0:
return False
if prime >= sqrt_n:
return True
return True
# instantiating list of primes
primes = [2, 3]
# build list of primes
def get_primes(n, primes):
last = primes[-1]
while n > len(primes):
last += 2
if is_prime(last, primes):
primes.append(last)
The key thing to note is this method allows us to save a list of primes and continue off where we have last computed up to, saving us lots of time.
Problem 8
High level idea: Find the greatest product of \(K\) consecutive digits in the \(N\) digit number.
Input: \(T+1\) lines of integers. As always, the first line contains \(T\) that denotes the number of test cases. Each test case comprises containing integers \(K\) and \(N\), as well as the \(N\) digit long integer itself.
Constraints:
\[1 \leq T \leq 100\] \[1 \leq K \leq 7\] \[K \leq N \leq 1000\]Solution
To break down the problem statement: We are supposed to parse the input number of \(N\) digits and generate all combinations of \(K\) digit consecutive numbers (basically \(N - K + 1\) combinations). The solution is straight-forward in coding, noting that we have to handle the assignment of the first digit in each combination (lest everything becomes multiplied by the instantiated value of the placeholder variable).
def get_num(n,k,num):
ans = 0
for i in range(n-k+1):
val = 0
for j in range(k):
val = int(num[i+j]) if j == 0 else val * int(num[i+j])
if val > ans:
ans = val
return ans
This solution employs no math tricks, and instead is a string/array splicing coding practice. To better improve the robustness of this solution, one can employ checks to ensure each typecasting character in the input string is indeed a number (by filtering out for values \(> 10\)). We leave that for future work, as the problem statement states that the input will be a number.
Problem 9
High level idea: Find the greatest product of Pythagorean triples \(a,b,c\) that satisfies \(a + b + c = N\) for input integer \(N\).
Input: \(T+1\) lines of integers. The input contains \(T\) in the first line that denotes the number of test cases, followed by \(T\) lines of integer \(N\).
Constraints:
\[1 \leq T \leq 3000\] \[1 \leq N \leq 3000\]Solution
A Pythagorean triplet comprises integers \(a,b,c\) that forms a Pythagorus triangle by satisfying the equation \(a^2 + b^2 = c^2\). In this problem, we need to find the triplet that sums to \(N\) and produces the largest value when multiplied together, returning \(-1\) if a tripled does not exist.
First, we state all the equations given to us:
\[a + b + c = N\] \[a^2 + b^2 = c^2\] \[a < b < c\]To programmatically find the values \(a, b, c\), we need to somehow use these equations to reduce the search space. In this case, our goal is to iterate over values of \(a\) and use the equations above to calculate \(b\) and \(c\) given the value of \(N\) (which is a constant for a given problem).
Note that we can convert the first equation into \(c = N - b - a\) and substitute it into the second equation, which gives us the following:
\[b = \frac{(N-a)^2 - a^2}{2(N-a)}\] \[c = N - b - a\]With the above two equations, we can easily iterate values \(a\) to check if the values form a Pythagorus triangle (i.e. satisfies \(a^2 + b^2 = c^2\)).
Finally, one last optimization trick is to use the fact that \(a<b<c\) to search for values of \(a\) satisfying \(a<n/3\). Code implementation below:
def main(n):
ans = -1
for a in range(3, int(n/3)):
b = int((n**2 - 2*a*n)/(2*(n-a)))
c = n - b - a
if a**2 + b**2 == c**2:
val = a*b*c
if val > ans:
ans = val
return ans
This solution requires one to understand the problem and mathematically simplify the search space. A naive implementation requiring three loops would be too slow \(\mathcal{O}(n^3)\), whereas deriving formulae for \(b\) and \(c\) requires only one loop and reduces the time complexity to \(\mathcal{O}(n)\).
Problem 10
Find the greatest sum of all primes \(\leq N\).
Input: \(T+1\) lines of integers. The input contains \(T\) in the first line that denotes the number of test cases, followed by \(T\) lines of integer \(N\).
Constraints:
\[1 \leq T \leq 10^4\] \[1 \leq N \leq 10^6\]Solution
The first attempt I did was to re-use the prime number generator (naive method) done in problem #3. Unfortunately, this time round some test cases failed due to too slow an implementation. After some googling, I found a more effective method involving building the Sieve of Eratosthenes, followed by pre-computing the sum of primes.
The Sieve of Eratosthenes is a boolean array denoting if a number in its index position is prime. For example, sieve[2] should return True as \(2\) is a prime number, whereas sieve[0] and sieve[4] should both return False. The algorithm involves first instantiating a boolean array with True (except for the first two numbers \(0\) and \(1\)). Then, starting from \(2\), we mark out each \(2^{nd}\) number after \(2\) until the end of the length of sieve, which basically means we denote each multiple of \(2\) as not a prime number. We continue this marking of multiples for the next \(n^{th}\) which has not been marked out: \(3\) with multiples of \(3\), skipping \(4\) which had been marked False when sieving out multiples of \(2\), then sieving multiples of \(5\), and so on. Code implementation below:
# build sieve where index = prime number
def get_sieve(sieve):
sieve = [True] * 1000000
sieve[0] = False
sieve[1] = False
i = 2
while i < len(sieve):
if sieve[i]:
j = i
while i+j < len(sieve):
sieve[i+j] = False
j += i
i += 1
return sieve
With the sieve complete, we can finally compute the sum, saving the values in a list indexed by the value of \(N\) we want to query on.
def sum_prime(sum_primes, sieve):
sum_primes = [0] * 1000000
prev = 0
for i in range(len(sieve)):
sum_primes[i] = prev
if sieve[i]:
sum_primes[i] += i
prev += i
return sum_primes
This solution required me to learn something new about prime number generation, where counting can replace division check as s a form of prime number checking. Overall, a fun puzzle to indulge in!
Conclusion
While the practising my mathematical and algorithmic thinking had been fun, it seems like the Project Euler is geared towards learning interesting math tricks at the risk of being arcane. I’ll consider revisiting this problem set in the future, but for now it had been a good run!
Comments