project-euler.md

description
Try something new...and solve all the challenges...

Project Euler

Problem 4

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Since the limit is 10^6 which mean we only need to check 1998 numbers (http://oeis.org/A050250)

So we can easily bruteforce, checking every product generated by production of three-digits number is palindrome number or not

def is_palindrome(num):
	str_num = str(num)
	for i in range(0, len(str_num)):
		if str_num[i] != str_num[len(str_num) - i - 1]:
			return False
	return True

max = 0
max_i = 0
max_j = 0
for i in range(100, 1000):
	for j in range(100, 1000):
		product = i * j
		if is_palindrome(product) == True and product > max:
			max = product
			max_i = i
			max_j = j
print max, max_i, max_j

{% code title="output" %}

906609 913 993

{% endcode %}

But this is practice, so i will do it in more proper way

First, i need to wrote an algorithm to generate palindrome numbers

{% embed url="http://rhyscitlema.com/algorithms/generating-palindromic-numbers/" %}

But it turns out that generate palindrome numbers in mathematical way is no faster than string one

Problem 5

Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

import math
def check_prime(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def generate_prime_array(limit):
	arr = []
	for i in range(2, limit):
		if check_prime(i) == True:
			arr.append(i)
	return arr

primes = generate_prime_array(20)

k = 20
sum = 1
for p in primes:
	exp = math.floor(math.log(k)/math.log(p))
	sum *= p**exp
print sum

232792560

Problem 6

Sum square difference

Problem 6

The sum of the squares of the first ten natural numbers is,12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

#!/bin/python

import sys

def calc(num):
    formula = (num * (num**2 - 1) * (3*num + 2))/12
    return formula
t = int(raw_input().strip())
for a0 in xrange(t):
    n = int(raw_input().strip())
    print calc(n)

{% code title="input" %}

1
100

{% endcode %}

{% code title="output" %}

25164150

{% endcode %}

Problem 9

Special Pythagorean triplet

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

It's easy, brute a and then calculate b, c with each a, it will help reduce to O(n)

#!/bin/python

import sys

def find(m):
    maximum = -1
    for a in range(3, m/2):
        c = ((a**2) + ((m - a) ** 2))/(2*(m-a))
        b = m - a - c
        if b == int(b) or c == int(c):
            if a + b + c == m and (a**2 + b**2 == c**2):
                if a*b*c > maximum:
                    maximum = a*b*c
    return maximum

t = int(raw_input().strip())
for a0 in xrange(t):
    n = int(raw_input().strip())
    print find(n)