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

Problem Twenty

11 Nov

Here’s problem twenty:

Find the sum of the digits in the number 100!.

This was more or less brute force, but it runs fairly quickly so any extra “cleverness” would be superfluous.

Here it is:

def Factorial(n):
	product = 1
	for m in range(n, 1, -1):
		product *= m
	
	return product

print(sum([int(x) for x in str(Factorial(100))]))

We define Factorial() as taking an argument, and then multiplying it to its previous integer, repeating this until we reach one. We turn this resulting number (Factorial(100)) into a string so it is iterable, and place each of its digits (making sure to int() each digit) into a list, and then sum it up.

Answer: 648

Problem Nineteen

24 Oct

Here’s problem nineteen:

Question: How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

This could’ve been solved trivially by using the Python date module, but where’s the fun in that? I decided to create my own date-incrementer by simply the date in a list, as [month, day, year, weekday], and incrementing by day using a handful of functions.

The code is long, but we’ll look at it in chunks:

def leapyear(date): # checks if year is leap year
	global leapyr 
	if str(date[2])[-2:] != '00' and date[2] % 4 == 0:
		leapyr = True
	elif str(date[2])[-2:] == '00' and date[2] % 400 == 0:
		leapyr = True
	else:
		leapyr = False

def weekday(date): # increments weekday (m, t, w..)
	if date[3] == 7:
		date[3] = 1
	else:
		date[3] += 1
	
	return date

def day(date): # increments day (1, 2, 3, 4..31)
	if any(date[0] == i for i in [4, 6, 9, 11]): # 30 days
		if date[1] == 30:
			date[1] = 1
		else:
			date[1] += 1

	elif date[0] == 2: # february
		if leapyr:
			if date[1] == 29:
				date[1] = 1
			else:
				date[1] += 1
		else:
			if date[1] == 28:
				date[1] = 1
			else:
				date[1] += 1

	else: # 31 days
		if date[1] == 31:
			date[1] = 1
		else:
			date[1] += 1

	return date 

def month(date): # increments month
	if date[1] == 1: # since we increment the day first, if the day is 1, meaning the first day of a new month
		if date[0] != 12: # increment month
			date[0] += 1
		else:
			date[0] = 1

	return date

def year(date): # increments year
	if date[1] == 1 and date[0] == 1: # we increment day and month first, so if it is jan. 1st
		date[2] += 1 # increment year

	return date

date = [1, 1, 1901, 2] # start date, is tuesday
result = 0 # holds number of sundays on first of month

while date[0:3] != [12, 31, 2000]: # up to this date
	leapyear(date)
	date = weekday(date)
	date = day(date)
	date = month(date)	
	date = year(date)

	if date[1] == 1 and date[3] == 7:
		result += 1
	
print(result)

So let’s look at the run code first, at the very bottom.

date = [1, 1, 1901, 2] # start date, is tuesday
result = 0 # holds number of sundays on first of month

while date[0:3] != [12, 31, 2000]: # up to this date
	leapyear(date)
	date = weekday(date)
	date = day(date)
	date = month(date)	
	date = year(date)

	if date[1] == 1 and date[3] == 7:
		result += 1
	
print(result)

The starting date is stored as a list in date, and is a Tuesday (found by WolframAlpha), hence the 2. While the date is not the ending date (Dec 31, 2000), we run this chunk of code. leapyear(date) checks to see if the year is a leap year, and the next four functions each increment the date according to its name. Then we check if the current date is a Sunday on the first of a month, and if it is, we add one to result.

def leapyear(date): # checks if year is leap year
	global leapyr 
	if str(date[2])[-2:] != '00' and date[2] % 4 == 0:
		leapyr = True
	elif str(date[2])[-2:] == '00' and date[2] % 400 == 0:
		leapyr = True
	else:
		leapyr = False

Now let’s look at leapyear(). It calculate leap years based on what the question told us: “A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400”. We check if the last two digits of the year are “00” to determine if a year is a century. This is pretty simple.

def weekday(date): # increments weekday (m, t, w..)
	if date[3] == 7:
		date[3] = 1
	else:
		date[3] += 1
	
	return date

Incrementing the weekday is also pretty simple, and we use Monday as 1 up to Sunday as 7. If it’s Sunday, the next day is Monday, so we make sure to reset the weekday to 1.

def day(date): # increments day (1, 2, 3, 4..31)
	if any(date[0] == i for i in [4, 6, 9, 11]): # 30 days
		if date[1] == 30:
			date[1] = 1
		else:
			date[1] += 1

	elif date[0] == 2: # february
		if leapyr:
			if date[1] == 29:
				date[1] = 1
			else:
				date[1] += 1
		else:
			if date[1] == 28:
				date[1] = 1
			else:
				date[1] += 1

	else: # 31 days
		if date[1] == 31:
			date[1] = 1
		else:
			date[1] += 1

	return date 

Here it gets a bit complicated. We have to know what month it is to calculate the number of days in that month, and also if it’s a leap year. The code is divided into three chunks, with the first and last dedicated to months with 30 and 31 days, respectively. This is more or less straightforward, using the same logic for incrementing as in weekday(). For February, we have to consider if it’s a leap year or not. This is found by the global variable leapyr, which we calculate at every date by the function leapyear(). If it is a leap year, we increment the day until it hits 29, and if it isn’t, we increment until 28.

def month(date): # increments month
	if date[1] == 1: # since we increment the day first, if the day is 1, meaning the first day of a new month
		if date[0] != 12: # increment month
			date[0] += 1
		else:
			date[0] = 1

	return date

Moving on to the month. Remember that in the run code that we increment the day before we increment the month. So, that means if the day is 1, it must be the first day of a new month, and so we increment the month by one. Same logic as before, incrementing up to 12.

def year(date): # increments year
	if date[1] == 1 and date[0] == 1: # we increment day and month first, so if it is jan 1st
		date[2] += 1 # increment year

	return date

The last part is incrementing the year. We increment the day and month before incrementing the year, so if the day and month are 1/1 (Jan 1st), that means it must be a new year, so we increment year by 1. There is no limit on how high the year can go.

When the date reaches Dec 31, 2000, the loop ends and we print the result.

Answer: 171