Project Euler Problem #12 Solution

By the use of a theorem and a (relatively) efficient factorization algorithm, we can solve this problem fairly quickly. First, the theorem:

Theorem. If , then

.

This theorem tells us that if we can decompose into its prime factors, we can efficiently calculate the number of divisors of . It remains, therefore, for us to find a sufficiently efficient factorization algorithm. How about this:

def prime_factorization(n):
	divisor = 2
	while n > 1:
		factors = []
		while n % divisor == 0:
			factors.append(divisor)
			n /= divisor
		if factors:
			yield factors
		divisor += 1

This algorithm starts with a divisor of 2 and, if n is divisible by the divisor, it divides n by the divisor as long as n is still divisible by the divisor. When n no longer is, it increments the divisor and tries again until n is reduced to 1. Furthermore, each of the prime factors of n that equal each other are grouped into subsequences. That is, for n = 1701, we get [[3, 3, 3, 3, 3], [7]]. This makes it easier to use the theorem above.

We use a generator function to yield the triangle numbers, and a divisor-counting function that makes use of the theorem above, to get the desired number. All of the code, then, together, is:

def triangle_numbers():
	n = 1
	while True:
		yield n * (n + 1) / 2
		n += 1

def prime_factorization(n):
	candidate_factor = 2
	while n > 1:
		factors = []
		while n % candidate_factor == 0:
			factors.append(candidate_factor)
			n /= candidate_factor
		if factors:
			yield factors
		candidate_factor += 1

def count_divisors(n):
	count = 1
	for tuple in prime_factorization(n):
		count *= (len(tuple) + 1) 
	return count

for t in triangle_numbers():
	if count_divisors(t) > 500:
		print t
		break

Project Euler Problem #14 Solution

We calculate the length of each Collatz sequence with starting number and find the value of n for which the length is maximum.

Note that we actually calculate one less than the length of each sequence, but since that subtraction is applied to each length, it doesn’t matter.

def is_even(n):
	return n % 2 == 0

def collatz_length(n):
	length = 0
	while n > 1:
		length += 1
		if is_even(n):
			n /= 2
		else:
			n = 3 * n + 1
	return length

max_n = 0
max_len = 0
for n in range(1, 1000000):
	len = collatz_length(n)
	if len > max_len:
		max_len = len
		max_n = n

print max_n

Project Euler Problem #24 Solution

This code gets the millionth lexicographic permutation of (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):

from itertools import permutations

MILLIONTH = 10 ** 6 - 1

print reduce(lambda x, y: str(x) + str(y), list(permutations(range(10), 10))[MILLIONTH])

Project Euler Problem #29 Solution

Pretty self-explanatory:

import itertools

products = set()

for pair in itertools.product(range(2, 101), range(2, 101)):
	products.add(pair[0] ** pair[1])

print len(products)

This code takes advantage of the fact that the set object silently rejects duplicates when an attempt is made to add one.

Project Euler Problem #56 Solution

We effectively search a 100 × 100 grid and find the cell with the greatest digital sum. Using some functional magic, we can do this:

from itertools import *

pairs = product(range(1, 100), range(1, 100))
exponentials = imap(lambda pair: pair[0] ** pair[1], pairs)
strings = imap(lambda exponential: str(exponential), exponentials)
sums = imap(lambda string: sum(map(lambda digit: int(digit), string)), strings)

print max(sums)

Project Euler Problem #28 Solution

This algorithm calculates the sum of the diagonal numbers in a 1001 × 1001 spiral:

current = 0
step = 2

sum = 0
limit = 1001 ** 2

spiral = range(1, limit + 1)

while current < limit:
	for i in range(4):
		if current > limit:
			break
		sum += spiral[current]
		current += step
	step += 2

print sum

Project Euler Problem #40 Solution

Simple:

digits = ""

for n in range(1, 1000001):
	digits += str(n)

product = 1
for i in range(7):
	product *= int(digits[10 ** i - 1])

print product

Project Euler Problem #53 Solution

Simply iterate over each where and and count which ones are greater than 1,000,000. In Python:

import operator

def factorial(n):
	return 1 if n == 0 else reduce(operator.mul, range(1, n + 1))

def combo(n, r):
	return factorial(n) / (factorial(r) * factorial(n - r))

count = 0

for n in range(1, 101):
	for r in range(1, n):
		if combo(n, r) > 1000000:
			count += 1

print count

Project Euler Problem #42 Solution

Read the file of words, calculate their scores, and see which are triangular numbers. Note the use of an iterator function on line 4:

CAPITAL_LETTER_A = 'A'
COMMA = ","

def triangular_numbers():
	n = 1
	while True:
		yield n * (n + 1) / 2
		n += 1

def score_char(char):
	return ord(char) - ord(CAPITAL_LETTER_A) + 1

def score(word):
	return sum(map(score_char, word))

def is_triangular(num):
	for n in triangular_numbers():
		if n > num:
			return False;
		else:
			if n == num:
				return True
	return False

with open("words.txt") as f:
	text = f.read()
	words = map(lambda word: word[1:-1], text.strip().split(COMMA))
	scores = map(lambda word: score(word), words)
	
	print len(filter(lambda score: is_triangular(score), scores))

Project Euler Problem #45 Solution

This program starts at n = 286 and calculates triangle numbers from that point, checking whether the triangle number is also pentagonal and hexagonal:

public static void Main(string[] args)
{
    for (var n = 286L; ; n++)
    {
        var triangleNumber = TriangleNumber(n);
        if (IsPentagonal(triangleNumber) && IsHexagonal(triangleNumber))
        {
            Console.WriteLine(triangleNumber);
            break;
        }
    }
    Console.ReadKey();
}

public static bool IsPentagonal(long triangleNumber)
{
    var pentagonal = 0L;
    for (var n = 1L; pentagonal <= triangleNumber; n++)
    {
        pentagonal = n * (3 * n - 1) / 2;
        if (pentagonal == triangleNumber)
            return true;
    }
    return false;
}

public static bool IsHexagonal(long triangleNumber)
{
    var hexagonal = 0L;
    for (var n = 1L; hexagonal <= triangleNumber; n++)
    {
        hexagonal = n * (2 * n - 1);
        if (hexagonal == triangleNumber)
            return true;
    }
    return false;
}

private static long TriangleNumber(long n)
{
    return n * (n + 1) / 2;
}