Archive | November, 2011

Problem Twenty Seven

18 Nov

Here’s problem twenty seven:

Question: Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

I’m not exactly sure why, but this was a pretty fun problem to do. Basically I just had to brute force my way through this problem, and it actually ran much faster than I anticipated.

Take a look:

def isPrime(x): 
	divisor = 3 
	limit = int(x**0.5) + 1

	while divisor < limit:
		if x % divisor == 0:
			return False
		else:
			divisor += 2 

	return True

result = [0, 0, 0] # a, b, counter

for a in range(-999, 1000):
	for b in range(-999, 1000):
		n = 0
		while True:
			x = n*n + a*n + b
			if x > 0 and isPrime(x):
				n += 1	
			else:
				if n > result[2]:
					result = [a, b, n]
				break

print(result[0]*result[1])

As you can see, I reused the ever-so-popular isPrime() function for this problem. We use two for loops to test every combination of coefficients, and initialize n, the independent variable of the quadratic, to 0. We then continue to generate values of the quadratic until we reach one that isn’t prime. The length of the chain generated is tested to see if it’s greater then the previous longest chain, and if it is we overwrite the variable result.

Answer: -59231

Advertisements

Problem Twenty Six

17 Nov

Here’s problem twenty six:

Question: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

I had to find a clever solution to this problem, mainly because I didn’t know how to brute force it (maybe I should’ve read this). I learn something new everyday, and by solving this problem I discovered a neat application for Fermat’s Little Theorem.

Take a look:

def lengthDecimal(n): # finds length of recurring cycle of 1/n
	while n % 2 == 0:
		n //= 2
	while n % 5 == 0:
		n //= 5
	
	for x in range(1, n):
		if (10**x - 1) % n == 0:
			return x
			
	return 0

result = [0, 0] # number, length

for n in range(2, 1000):
	if lengthDecimal(n) > result[1]:
		result = [n, lengthDecimal(n)]
	
print(result)

Any multiple of 2 or 5 in the denominator will yield the same number of decimal places, so that is the first step of the lengthDecimal() function. If a prime number is in the denominator, we can use a trick based on Fermat’s Little Theorem to calculate the length of the recurring decimal cycle. The application is as follows: 1/n has a cycle of x digits if (10x – 1) % n = 0. Given n, it’s a simple matter of guess and check to find x.

This function is used to test numbers up to 1000.

Answer: 983

Problem Twenty Five

16 Nov

Here’s problem twenty five:

Question: What is the first term in the Fibonacci sequence to contain 1000 digits?

This was pretty simple, all we need to do is generate Fibonacci terms and check the length of each one. We also need a counter to keep track of what term we’re on.

a = b = n = 1
counter = 2

while len(str(n)) != 1000:
	counter += 1
	n = a + b
	a, b = b, n

print(counter)

a, b, and n are variables used to generate the Fibonacci sequence. Since Project Euler defines the first term of the Fibonacci sequence as 1 rather than 0, we initialize the counter to 2, since the first term we calculate (2) will be the 3rd term. The rest is self-explanatory.

Answer: 4782

Problem Twenty Four

15 Nov

Here’s problem twenty four:

Question: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

This was pretty simple using the itertools module. Just to clarify, a permutation is a combination of items where the order does matter, which applies in this case because we’re dealing with numbers.

import itertools

print([x for x in itertools.permutations('0123456789', 10)][999999])

This creates a list of each permutation, and we don’t need to sort it because itertools creates each permutation in order of increasing value, since ‘0123456789’ is in order of increasing value. The second argument for permutations(), 10, isn’t explicitly needed since it will default to the length of the iterable, but this makes it a bit clearer. The millionth lexicographic permutation will be 999,999th in the list, so that’s the position we print.

The printed statement is not pretty, but it works. I’m not exactly sure why itertools.permutations() returns a list of the (string) digits of each permutation, instead of just a string for each permutation.

Answer: 2783915460

Problem Twenty Three

14 Nov

Here’s problem twenty three:

Question: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

This problem was rather complicated…it took me a while to come up with an efficient way of solving it. Bits of this code are actually the result of reading other people’s solutions to improve my own.

Take a look:

def abundantNumberGen(limit): # returns list of abundant numbers up to limit
	numbers = []
	for x in range(1, limit):
		if sum(properFactors(x)) > x:
			numbers.append(x)
	return numbers

def properFactors(n): # returns list of proper factors of a number
	factors = [1] # 1 is automatically a factor
	for x in range(2, int(n**0.5)+1):
		if n % x == 0:
			factors.extend([x, n/x])
	if n**0.5 == int(n**0.5): # important! must remove the extra square root if n is a perfect square
		factors.remove(n**0.5)
	return factors

result = list(range(28123)) # list of numbers up to 28123; result[12] = 12, result[28122] = 28122
abundantNumbers = abundantNumberGen(28123)
for n in abundantNumbers:
	for m in abundantNumbers:
		if n + m < 28123: 
			result[n + m] = 0 # result[100] = 100 --> result[100] = 0

print(sum(result))

Instead of directly reading the run code first, let’s analyze the functions first for a change of pace.

def properFactors(n): # returns list of proper factors of a number
	factors = [1] # 1 is automatically a factor
	for x in range(2, int(n**0.5)+1):
		if n % x == 0:
			factors.extend([x, n/x])
	if n**0.5 == int(n**0.5): # important! must remove the extra square root if n is a perfect square
		factors.remove(n**0.5)
	return factors

This function is used repeatedly in calculating the solution, so any increase in efficiency here would significantly reduce the run time overall. This was done by automatically setting one as a factor, and only test-dividing up to the square root of the number. The factors found are stored in a list, and every time we find a factor, we add its corresponding factors (e.g. the number is 10, we find 2 and then find 5) to the list. It’s extremely important to remove the duplicate square root factor if the number is a perfect square; I initially overlooked this fact and ended up with a wrong answer. This is a more general version of the D(n) function used in problem 21.

def abundantNumberGen(limit): # returns list of abundant numbers up to limit
	numbers = []
	for x in range(1, limit):
		if sum(properFactors(x)) > x:
			numbers.append(x)
	return numbers

This function returns a list abundant numbers up to a specified limit, directly using the definition of an abundant number. We test if the sum of a number’s proper divisors is greater than the number itself, and if true, we append it to the list.

result = list(range(28123)) # list of numbers up to 28123; result[12] = 12, result[28122] = 28122
abundantNumbers = abundantNumberGen(28123)
for n in abundantNumbers:
	for m in abundantNumbers:
		if n + m < 28123: 
			result[n + m] = 0 # result[100] = 100 --> result[100] = 0

print(sum(result))

Now let’s look at the run code. The first line here was adapted from another solution I found, since I thought it was an extremely clever and efficient way of tackling this problem. Line 1 creates a list where the elements are equal to their indexes, i.e. list[10] = 10, list[124] = 124, simple but very useful. We generate abundant numbers up to the specified limit of 28123 (because we want a sum of abundant numbers that is less than 28123). We then test every combination of two abundant numbers, using two for loops, and if the result is less than 28123, i.e. a number that can be expressed as the sum of two abundant numbers, we set that element of the list to zero. When this finishes, all the numbers in the list that can be expressed as a sum of abundant numbers will be zero, and we can simply sum the remaining to find the solution.

Answer: 4179871

Problem Twenty Two

13 Nov

Here’s problem twenty two:

Question: What is the total of all the name scores in the file?

The two parts of the problem are as follows: we need to interpret the content from the file such that python can directly manipulate it, and then we need to interpret this data so that we can keep track of and sum each respective name score.

Here’s the code:

f = open(r'\Project Euler\euler_22_names.txt')
names = [n.replace('"','') for n in f.read().split(',')]
f.close()

names.sort()
result = 0 # sum of name scores
index = 0 # keeps track of what number the name is in the list (1-5000)

for name in names:
    index += 1 
    for letter in name:
        result += (ord(letter) - 64)*index # a=1...z=26 times the index number (name score)

print(result)

Getting the content from the file is rather simple:

f = open(r'\Project Euler\euler_22_names.txt')
names = [n.replace('"','') for n in f.read().split(',')]
f.close()

We create the file object f, and reading it as a string, we split each name by a comma, then delete the quotation marks around the name, and store each of these “processed” names in a list. The file is then closed.

names.sort()
result = 0 # sum of name scores
index = 0 # keeps track of what number the name is in the list (1-5000)

for name in names:
    index += 1 
    for letter in name:
        result += (ord(letter) - 64)*index # a=1...z=26 times the index number (name score)

print(result)

Listing in alphabetical order is rather simple in python, we just apply the sort() function to the list to do this. We initialize two variables, result, which will sum the name scores, and index, which is used in calculating the name score. We then iterate through the list of names, making sure to increment the index by one each time we retrieve a new name. Then we iterate through each of the characters in the name, adding to result the score of each letter (sum of the scores of the letters of a name = name score). The alphabetical number of a letter is found by getting the Unicode code of the letter, and subtracting 64. This is multiplied by the index, or the position of the name in the file, to get the score.

Answer: 871198282

Problem Twenty One

12 Nov

Here’s problem twenty one:

Evaluate the sum of all the amicable numbers under 10000.

A number is amicable if and only if the proper divisors of the sum of its proper divisors equal the number. A bit confusing, but the problem page has a better explanation of this. After doing problem 23, I actually went back and rewrote some of the code for this problem since I found a more efficient way to sum the proper factors of a number.

Let’s take a look:

def D(n): # sum of proper divisors
	sum = 1
	for x in range(2, int(n**0.5)+1):
		if n % x == 0:
			sum += x + n/x

	# important! must remove the extra square root if n is a perfect square
	if n**0.5 == int(n**0.5): 
		sum -= n**0.5

	return sum	

amicables = []
for a in range(2, 10000):
	b = D(a)
	if a != b and a == D(b): # definition of amicable numbers
		amicables.extend([a, b])

print(sum(set(amicables)))

This code is straightforward enough. Looking at line 13, we create an empty list to hold all amicable numbers that we find. We generate a values based on the criteria of the problem (<10000), and skip 1 because though it's not an amicable number, our D(n) function does some funky stuff and actually considers it amicable (trace through its path if you’re curious why — it creates the amicable pair 1, 0). We then use an if statement to test if we’ve found an amicable number and its pair (just directly converting the definition to Python), and if it is, we add both numbers to the amicables list.

def D(n): # sum of proper divisors
	sum = 1
	for x in range(2, int(n**0.5)+1):
		if n % x == 0:
			sum += x + n/x

	# important! must remove the extra square root if n is a perfect square
	if n**0.5 == int(n**0.5): 
		sum -= n**0.5

	return sum	

We test if a number is amicable by analyzing its proper factors, so we create a function called D(n) to do this. It takes in an argument, and finds the sum of its proper factors. We brute force the factors up to the square root of the number, at which point we can just very trivially find the remaining factors. Each factor that is found is added to a sum variable. An important thing to note is that if the argument is a perfect square, its square root will be added twice so we must subtract one square root from the sum.

Now before we can just sum up the numbers in the amicables list, remember that there are extra numbers in the list (double the sum to be exact). We must get rid of these duplicate numbers, so the set() function is used, which returns a set, which by definition is a collection of distinct items. Another way to do this would to just divide the sum by two.

Answer: 31626