CTF
Search…
Project Euler
Try something new...and solve all the challenges...

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
1
def is_palindrome(num):
2
str_num = str(num)
3
for i in range(0, len(str_num)):
4
if str_num[i] != str_num[len(str_num) - i - 1]:
5
return False
6
return True
7
8
max = 0
9
max_i = 0
10
max_j = 0
11
for i in range(100, 1000):
12
for j in range(100, 1000):
13
product = i * j
14
if is_palindrome(product) == True and product > max:
15
max = product
16
max_i = i
17
max_j = j
18
print max, max_i, max_j
Copied!
output
1
906609 913 993
Copied!
But this is practice, so i will do it in more proper way
First, i need to wrote an algorithm to generate palindrome numbers
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?
1
import math
2
def check_prime(n):
3
for i in range(2, int(math.sqrt(n)) + 1):
4
if n % i == 0:
5
return False
6
return True
7
8
def generate_prime_array(limit):
9
arr = []
10
for i in range(2, limit):
11
if check_prime(i) == True:
12
arr.append(i)
13
return arr
14
15
primes = generate_prime_array(20)
16
17
k = 20
18
sum = 1
19
for p in primes:
20
exp = math.floor(math.log(k)/math.log(p))
21
sum *= p**exp
22
print sum
Copied!
1
232792560
Copied!

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.
1
#!/bin/python
2
3
import sys
4
5
def calc(num):
6
formula = (num * (num**2 - 1) * (3*num + 2))/12
7
return formula
8
t = int(raw_input().strip())
9
for a0 in xrange(t):
10
n = int(raw_input().strip())
11
print calc(n)
Copied!
input
1
1
2
100
Copied!
output
1
25164150
Copied!

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)
1
#!/bin/python
2
3
import sys
4
5
def find(m):
6
maximum = -1
7
for a in range(3, m/2):
8
c = ((a**2) + ((m - a) ** 2))/(2*(m-a))
9
b = m - a - c
10
if b == int(b) or c == int(c):
11
if a + b + c == m and (a**2 + b**2 == c**2):
12
if a*b*c > maximum:
13
maximum = a*b*c
14
return maximum
15
16
t = int(raw_input().strip())
17
for a0 in xrange(t):
18
n = int(raw_input().strip())
19
print find(n)
Copied!
Last modified 2yr ago