Archive | October, 2011

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

Advertisements

Problem Eighteen

23 Oct

Here’s problem eighteen:

Question: Find the maximum total from top to bottom of the triangle below.

In the blurb, Project Euler states that brute forcing every possible path is possible, but that there is a much harder version of this problem later on that requires a “clever method”. So from the beginning I decided to throw a brute force solution out the window, and focused on constructing an inventive solution.

Here’s a quick overview of the code; it’s not very long:

triangle = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 4, 82, 47, 65],
[19, 1, 23, 75, 3, 34],
[88, 2, 77, 73, 7, 63, 67],
[99, 65, 4, 28, 6, 16, 70, 92],
[41, 41, 26, 56, 83, 40, 80, 70, 33],
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]

triangle.reverse()

for row in range(0, len(triangle)):
    for a in range(0, len(triangle[row])-1):
        m = max(triangle[row][a], triangle[row][a+1])
        n = m + triangle[row+1][a]

        triangle[row+1][a] = n

print(triangle[len(triangle)-1])

We store the triangle as a list of lists, which makes it possible to iterate through each term of each row. Then this list is reversed, essentially flipping the triangle upside down so that the bottom row is now the first row and vice versa. This isn’t absolutely necessary, but I like to work from the top to the bottom.

The two for statements simply allow us to iterate through each row of the triangle (for statement #1), and then iterate through every number in that row (for statement #2). The current row is stored in row and the current number is stored in a. (I have to admit that the variable names are somewhat inscrutable here, but I wasn’t feeling very creative when writing this code)

Now let’s take a look at the bigger picture. How do we solve this problem without trying every possible path? Simply by working from the bottom to the top, or since we reversed the triangle, from the top to the bottom (but let’s stick with bottom to top for now so you can look at the triangle). We only need to consider two rows at a time, starting from the bottom row and the row above it. Let’s look at the upper row (line 15). The first element is 63. If you think about it, there’s only two ways that you can “move”, or find a number to add, from 63. Going down, it can only go through 4 or 62 to follow a path. Now that we know this, we can see that there’s only one correct path (moving up) to 63, and that’s the path that will create the largest sum. In this case that would be 62 + 63. Extending this discovery, we can know that for every number in a row, there are two ways to get there from the row below, and in those two ways/paths, one of them will create the largest sum. So we simply take the max of two adjacent numbers in a row, and add that to the corresponding number in the row above.

for row in range(0, len(triangle)):
    for a in range(0, len(triangle[row])-1):
        m = max(triangle[row][a], triangle[row][a+1])
        n = m + triangle[row+1][a]

        triangle[row+1][a] = n

Now the code should make some intuitive sense. The first line after the for statements simply stores the max of two adjacent numbers in a row in m. n is the sum of m (the max), and the corresponding number in the row above it. Then we actually replace that term (the corresponding number in the row above) with n, the sum. So, when we’re done with one row, each term of the row above will hold the largest possible sum to get to that position. This repeats until we reach the very top of the triangle (but remember we’re actually going down the list), where there will be two terms in the second to last row, and one term in the row above. Each of the two terms in the bottom row will represent the largest possible path to that term. This should make sense now, but if it doesn’t try running the code yourself with a print(triangle) statement after each iteration to visually see what is going on.

Then we print the top row of the triangle (bottom of the list), which will indicate the largest possible path.

Answer: 1074

Problem Seventeen

19 Oct

Here’s problem seventeen:

Question: If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

This problem was pretty involved. Converting digits to numbers was significantly more complicated than I have initially expected, and I was surprised that my solution worked almost immediately after I finished writing it. I expected there to be some small detail that I overlooked, but it worked unexpectedly well.

Here’s the code:

def numberWordLength(n):
	total = 0

	digits = [int(x) for x in str(n)]
	digits.reverse()

	ones = digits[0]
	tens = hundreds = thousands = 0
	if len(digits) >= 2:
		tens = digits[1]
	if len(digits) >= 3:
		hundreds = digits[2]
	if len(digits) == 4:
		thousands = digits[3]

	# testing ones place
	if any(ones == i for i in [1,2,6]): # one, two, six
		total += 3
	elif any(ones == i for i in [4,5,9]): # four, five, nine
		total += 4
	elif any(ones == i for i in [3,7,8]): # three, seven, eight
		total += 5

	# testing tens place
	if tens == 0:
		pass
	elif any(tens == i for i in [4,5,6]): # forty, fifty, sixty
		total += 5
	elif any(tens == i for i in [2,3,8,9]): # twenty, thirty, eighty, ninety
		total += 6
	elif tens == 7: # seventy
		total += 7
	elif tens == 1 and any(ones == i for i in [4,6,7,9]): # fourTEEN, sixTEEN, sevenTEEN, nineTEEN
		total += 4 # adding the letters in 'teen'
	elif tens == 1 and any(ones == i for i in [3,5,8]): # thirtEEN, fiftEEN, eightEEN
		total += 3 # adding the 'een'
	elif tens == 1 and any(ones == i for i in [1,2]): # eleVEN, tweLVE
		total += 3
	elif tens == 1 and ones == 0: # ten
		total += 3

	# testing hundreds place
	if hundreds == 0:
		pass
	elif any(hundreds == i for i in [1,2,6]): # onehundred, two, six
		total += 10
		if tens != 0 or ones != 0:
			total += 3 # adding the 'and'
	elif any(hundreds == i for i in [4,5,9]): # fourhundred, five, nine
		total += 11
		if tens != 0 or ones != 0:
			total += 3 # adding the 'and'
	elif any(hundreds == i for i in [3,7,8]): # threehundred, seven, eight
		total += 12
		if tens != 0 or ones != 0:
			total += 3 # adding the 'and'

	# testing thousands place
	if thousands == 1: # onethousand
		total += 11

	return total

sum = 0

for n in range(1,1001):
	sum += numberWordLength(n)

print(sum)

The bulk of the code is made up of the function numberWordLength(). Just to get a big picture view of how this all works, let’s take a look at the bottom first.

sum = 0

for n in range(1,1001):
	sum += numberWordLength(n)

print(sum)

So sum is initialized to zero. We put every number up to 1000 into a function that magically returns the number of letters it would be if it were written out as an English word. We add that to sum, and when we’re finished we print it.

Now let’s look at how the magical numberWordLength() function works, in chunks.

def numberWordLength(n):
	total = 0

	digits = [int(x) for x in str(n)]
	digits.reverse()

	ones = digits[0]
	tens = hundreds = thousands = 0
	if len(digits) >= 2:
		tens = digits[1]
	if len(digits) >= 3:
		hundreds = digits[2]
	if len(digits) == 4:
		thousands = digits[3]

Here we initialize the variable total to zero. It will hold the number of letters a number has, and it’s the variable we will return later on. We convert the inputted number, n, into a list of digits, and reverse it. This is so the tens place is first (digits[0]), hundreds place is second, and so on. ones holds the ones place digit of the inputted number, and the other variables are initialized to zero since there not need be any digit after the ones place. If there are, we set the variables to their respective values in digits.

Moving on,

# testing ones place
if any(ones == i for i in [1,2,6]): # one, two, six
	total += 3
elif any(ones == i for i in [4,5,9]): # four, five, nine
	total += 4
elif any(ones == i for i in [3,7,8]): # three, seven, eight
	total += 5

We test the ones place first. The any() function returns true if any of the elements in the iterable are true. So if the ones digits equals 1, 2, or 6, each of which has 3 characters in its English name, we add 3 to total. This varies depending on the value of ones, and if ones is zero, we add nothing to total.

Continuing,

# testing tens place
if tens == 0:
	pass
elif any(tens == i for i in [4,5,6]): # forty, fifty, sixty
	total += 5
elif any(tens == i for i in [2,3,8,9]): # twenty, thirty, eighty, ninety
	total += 6
elif tens == 7: # seventy
	total += 7

elif tens == 1 and any(ones == i for i in [4,6,7,9]): # fourTEEN, sixTEEN, sevenTEEN, nineTEEN
	total += 4 # adding the letters in 'teen'
elif tens == 1 and any(ones == i for i in [3,5,8]): # thirtEEN, fiftEEN, eightEEN
	total += 3 # adding the 'een'
elif tens == 1 and any(ones == i for i in [1,2]): # eleVEN, tweLVE
	total += 3

elif tens == 1 and ones == 0: # ten
	total += 3

First we check it tens is zero, meaning that there’s no tens digit (remember how we initialized the variables) or the tens digit is actually zero. If it is zero, we skip over the entire loop for efficiency’s sake. pass is the statement used in Python to indicate that nothing should be done, since a blank is not allowed.

Now things get slightly complicated. There’s three cases we have to consider here.

1. (Lines 4-9) The tens digit is between 2 and 9, which means that there is no interaction between the tens and ones digit. In other words, if 2 is in the tens place, no matter what the ones place is, it will always be twenty-something. Therefore, we can simply add the length of ‘twenty’, 6, to total. This varies depending on the tens place.

2. (Lines 11-16) The tens digit is 1, and the ones digit is not 0. This means that we have to deal with the strange English teen-number system. The tens and ones digit interact with each other to form the full word. For example, if the number was 11, it would not be ten-one, but rather eleven. In this case, we already added the length of ‘one’ to total, we only need to add 3 more to total instead of the full length of ‘eleven’, which is 6. Does that make sense? If not, read at the comments in the code and try it with a different number.

3. (Lines 18-19) The tens digit is 1, and the ones digit is 0. Then it’s simple. That means it’s just ‘ten’, and we add 3 to total.

We’re almost at the end now,

# testing hundreds place
if hundreds == 0:
	pass
elif any(hundreds == i for i in [1,2,6]): # onehundred, two, six
	total += 10
	if tens != 0 or ones != 0:
		total += 3 # adding the 'and'
elif any(hundreds == i for i in [4,5,9]): # fourhundred, five, nine
	total += 11
	if tens != 0 or ones != 0:
		total += 3 # adding the 'and'
elif any(hundreds == i for i in [3,7,8]): # threehundred, seven, eight
	total += 12
	if tens != 0 or ones != 0:
		total += 3 # adding the 'and'

Here it gets just a bit more complicated. Again, if hundreds is zero, that means that there is no hundreds place or that the hundreds place value actually is zero (same reasoning as before). Just looking at the outermost if/elif statements, we add the varying length of the word-form hundreds place to total. For example, if the hundreds place was 4, we would add 11 because it’s ‘fourhundred’. This is fairly straightforward.

However, there’s another factor we must consider. Because in English we sometimes add the word ‘and’ when we’re naming numbers above 100, the length of ‘and’ must be accounted for. If we think about it this way, you don’t use an ‘and’ when naming a number that’s purely in the hundreds place, e.g. 200, which would simply be ‘twohundred’. However, if there’s a nonzero digit in either the ones or tens place, there is an ‘and’. For example, 402 is ‘fourhundredandtwo’, 710 is ‘sevenhundredandten’, and 214 is ‘twohundredandfourteen’. So if either the ones or tens digit is not zero, then we add 3 to total to account for the added ‘and’.

Finally,

# testing thousands place
if thousands == 1: # onethousand
	total += 11

return total

Since the only number we’re dealing with in the thousands place is 1000, that’s the only number we need to take into consideration. So if thousands is equal to 1, i.e. the number is 1000, we add 11 (‘onethousand’) to total regardless of anything else. There is no need to account for ‘and’ or anything else because if the thousands place is one, then the other places will necessarily be zero, so we’re essentially finding the length of the word-form 1000. When this is done, we return the total.

Answer: 21124

Problem Sixteen

18 Oct

Here’s problem sixteen:

Question: What is the sum of the digits of the number 2^1000?

This was a pretty straightforward problem. The only tricky part may have been adding the digits, but it really can be tackled in one line of code.

Here it is:

print(sum(map(int, str(2**1000))))

print(sum([int(x) for x in str(2**1000)]))

I actually have two ways of getting to the solution here, just to practice writing different Python. The first uses the map() function, which takes a function as the first argument and an iterable as the second. It applies the function to all elements of that iterable, and returns the values in an iterable. Then we sum.

The second works directly inside a list, applying the int() function to every character of the string 2**1000, stores that in a list, and sums.

Answer: 1366

Problem Fifteen

17 Oct

Onto problem fifteen:

Question: How many routes are there through a 20×20 grid?

I was actually stuck on this problem for a couple of days, and it took ┬áthe help of a friend to finally figure it out. I kept thinking about it in terms of a grid and┬ávertices, but it’s a lot more helpful to think of it as combinations of routes.

In the full problem, Project Euler specifies that you cannot “backtrack” from a point, so essentially you can only move down and right from any given point. In a 2×2 grid, no matter what path you take, you have to move two across and two down to reach the end. This logic also applies to a 20×20 grid, where every path will contain 20 (let’s say vectors just for fun) right-vectors and 20 down-vectors. So how many ways are there of rearranging these 40 vectors? It’s 40 factorial, or 40!.

In other words, imagine there’s 40 empty spaces (visualize as empty boxes). You also have 40 different vectors (visualize as arrows) that you can put into these 40 spaces. For the first space, you have 40 vectors to choose from, so there’s 40 possibilities. For the second space, you now only have 39 vectors to choose from. So on and so forth. The find the total number of possible arrangements of vectors in the spaces, you multiply the possibilities in each space, so 40*39*38…*1. This is written as 40!.

However, 40! won’t give us the total number of paths from the start to the end of the grid. It’ll actually give quite a good amount extra. How can there be extra paths? Well, 40! actually finds all the arrangements if each of the down-vectors and right-vectors were different…say they were a different color. But since in this case they’re all the same, we’re getting the same path multiple times. For example, if we had the path down-down-right, it doesn’t matter which out of the 20 down-vectors we put into the first two positions. Using the 20 down-vectors, there are multiple ways you can get the path down-down-right, but for all practical purposes we only need one of them.

So how do we get rid of the extra “paths”? Well, since there are 20 of each type of vector, there are 20! ways to arrange down-vectors, and 20! ways to arrange right-vectors. So to get rid of these extra arrangements, we divide 40! by 20!20!, or 40!/(20!*20!). This is actually also a combination, or 40 choose 20. After some quick calculator punching, we arrive at the answer.

That’s how I solved the problem mathematically, but how would you do it with Python? Reading the solutions forum, I realized that the grid could actually represent Pascal’s Triangle. If you lay the grid diagonally and mark each vertex with the number of possible ways to get there, you get Pascal’s Triangle. I’m sure if you Google this problem you’ll find plenty of pictures of what it looks like, but we’ll focus on the code here.

Here’s it is:

import math

def pascalTriangle(n): # note that the first row of pascal's triangle is row 0

	row = [] # stores list of integers in the row

	for m in range(n+1): # for row n, there are n+1 elements of that row
		# for element number m in the row n
		# the value of m can be found with the formula:
		element = math.factorial(n) / (math.factorial(m)*math.factorial(n - m)) 
		row.append(element)

	return row

print(pascalTriangle(40)[20]) 

To find the nth row of Pascal’s Triangle, it simply uses a formula to arrive at each term of the row, and returns it as a list. For a 20×20 grid, the last vertex (the end) when overlayed onto Pascal’s Triangle will be the middle term of the 40th row, which is the 21st term, or the 20th element of the list.

Answer: 137846528820

Problem Fourteen

16 Oct

Here’s problem fourteen:

Question: Which starting number, under one million, produces the longest [hailstone] chain?

This sequence is called the hailstone sequence. Essentially, if the current value is even we do something, and if it’s odd we do something else, repeating this chain until the value equals one.

def hailstoneLength(n):
	counter = 0
	while True:
		if n % 2 == 0:
			n = n / 2
			counter += 1
		elif n == 1:
			return counter
		else:
			n = 3*n + 1
			counter += 1

length = 0
number = 0

for n in range(1, 1000000):

	if hailstoneLength(n) > length:
		length = hailstoneLength(n)
		number = n

print(number, length)

This is relatively simple. Given an n that is a number under one million, we find the length of the hailstone sequence starting at n. If it’s longer than the previous length we store n in a variable and repeat.

The function hailstoneLength() works by taking in an argument as the starting term, and generating the hailstone sequence of that initial value. It keeps track of every time the even or odd operation is applied to the current term (when the term does not equal one) in the variable counter. When the term equals one, by definition the hailstone sequence ends so we return the counter, or the length of the sequence.

Answer: 837799 (length of 524)

Problem Thirteen

16 Oct

Here’s problem thirteen:

Question: Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

I’m not sure if there’s actually a clever solution to this problem. I basically just copied and pasted the block of digits, and had python sum it all and print the result, and took the first ten digits.

print(sum([37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
91942213363574161572522430563301811072406154908250,
23067588207539346171171980310421047513778063246676,
89261670696623633820136378418383684178734361726757,
28112879812849979408065481931592621691275889832738,
44274228917432520321923589422876796487670272189318,
47451445736001306439091167216856844588711603153276,
70386486105843025439939619828917593665686757934951,
62176457141856560629502157223196586755079324193331,
64906352462741904929101432445813822663347944758178,
92575867718337217661963751590579239728245598838407,
58203565325359399008402633568948830189458628227828,
80181199384826282014278194139940567587151170094390,
35398664372827112653829987240784473053190104293586,
86515506006295864861532075273371959191420517255829,
71693888707715466499115593487603532921714970056938,
54370070576826684624621495650076471787294438377604,
53282654108756828443191190634694037855217779295145,
36123272525000296071075082563815656710885258350721,
45876576172410976447339110607218265236877223636045,
17423706905851860660448207621209813287860733969412,
81142660418086830619328460811191061556940512689692,
51934325451728388641918047049293215058642563049483,
62467221648435076201727918039944693004732956340691,
15732444386908125794514089057706229429197107928209,
55037687525678773091862540744969844508330393682126,
18336384825330154686196124348767681297534375946515,
80386287592878490201521685554828717201219257766954,
78182833757993103614740356856449095527097864797581,
16726320100436897842553539920931837441497806860984,
48403098129077791799088218795327364475675590848030,
87086987551392711854517078544161852424320693150332,
59959406895756536782107074926966537676326235447210,
69793950679652694742597709739166693763042633987085,
41052684708299085211399427365734116182760315001271,
65378607361501080857009149939512557028198746004375,
35829035317434717326932123578154982629742552737307,
94953759765105305946966067683156574377167401875275,
88902802571733229619176668713819931811048770190271,
25267680276078003013678680992525463401061632866526,
36270218540497705585629946580636237993140746255962,
24074486908231174977792365466257246923322810917141,
91430288197103288597806669760892938638285025333403,
34413065578016127815921815005561868836468420090470,
23053081172816430487623791969842487255036638784583,
11487696932154902810424020138335124462181441773470,
63783299490636259666498587618221225225512486764533,
67720186971698544312419572409913959008952310058822,
95548255300263520781532296796249481641953868218774,
76085327132285723110424803456124867697064507995236,
37774242535411291684276865538926205024910326572967,
23701913275725675285653248258265463092207058596522,
29798860272258331913126375147341994889534765745501,
18495701454879288984856827726077713721403798879715,
38298203783031473527721580348144513491373226651381,
34829543829199918180278916522431027392251122869539,
40957953066405232632538044100059654939159879593635,
29746152185502371307642255121183693803580388584903,
41698116222072977186158236678424689157993532961922,
62467957194401269043877107275048102390895523597457,
23189706772547915061505504953922979530901129967519,
86188088225875314529584099251203829009407770775672,
11306739708304724483816533873502340845647058077308,
82959174767140363198008187129011875491310547126581,
97623331044818386269515456334926366572897563400500,
42846280183517070527831839425882145521227251250327,
55121603546981200581762165212827652751691296897789,
32238195734329339946437501907836945765883352399886,
75506164965184775180738168837861091527357929701337,
62177842752192623401942399639168044983993173312731,
32924185707147349566916674687634660915035914677504,
99518671430235219628894890102423325116913619626622,
73267460800591547471830798392868535206946944540724,
76841822524674417161514036427982273348055556214818,
97142617910342598647204516893989422179826088076852,
87783646182799346313767754307809363333018982642090,
10848802521674670883215120185883543223812876952786,
71329612474782464538636993009049310363619763878039,
62184073572399794223406235393808339651327408011116,
66627891981488087797941876876144230030984490851411,
60661826293682836764744779239180335110989069790714,
85786944089552990653640447425576083659976645795096,
66024396409905389607120198219976047599490197230297,
64913982680032973156037120041377903785566085089252,
16730939319872750275468906903707539413042652315011,
94809377245048795150954100921645863754710598436791,
78639167021187492431995700641917969777599028300699,
15368713711936614952811305876380278410754449733078,
40789923115535562561142322423255033685442488917353,
44889911501440648020369068063960672322193204149535,
41503128880339536053299340368006977710650566631954,
81234880673210146739058568557934581403627822703280,
82616570773948327592232845941706525094512325230608,
22918802058777319719839450180888072429661980811197,
77158542502016545090413245809786882778948721859617,
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690]))

Answer: 5537376230