Tag Archives: sum

Problem Thirty

6 Dec

Here’s problem thirty:

Question: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

The trickiest part of this problem was determining a limit past which it is certain that no numbers can satisfy the conditions. The rest is more or less simple brute forcing and equality checking.

The limit can be found this way. It is impossible for a 9 digit number to be written as the sum of the fifth powers of its digits simply because the sum doesn’t reach that high. The lowest 9 digit number is 100,000,000, but the highest possible sum is 9*95 = 531441. Following this logic, 8 and 7 digit numbers are also impossible. However, a 6 digit number could potentially be written as the sum of the fifth powers of its digits: 100,000 < 6*95 = 354,294. Therefore, the largest number we need to test is 354,294 since any number after that will be impossible to reach with these sums.

Here’s the code:

result = 0

for x in range(2, 354295): # 6*9^5 + 1
	digits = [int(n)**5 for n in str(x)]
	if sum(digits) == x:
		result += x

print(result)

The variable result is initialized to 0. We generate x‘s up until the limit, and find the fifth power of each of its digits using list comprehension. If the sum of these values is equal to the number itself, we add the number to the result. Once the loop finished the result is printed.

Answer: 443839

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 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 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 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

Problem Eleven

6 Oct

On to problem eleven.

Question: What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

Ah, this question was actually pretty difficult. It took me a while to figure out a way to be able to find vertically and diagonally adjacent numbers in the grid, and my eventual solution was to use a list of lists. Essentially, each row in the grid is represented as a list of numbers, and 20 of these lists are put into another list in the order of the grid. After this was done, the rest entailed manipulating individual elements in the lists.

It might be clearer to see the code, so here it is:

nums = [
[ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8], 
[49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0], 
[81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65], 
[52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91], 
[22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80], 
[24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50], 
[32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70], 
[67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21], 
[24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72], 
[21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95], 
[78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92], 
[16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57], 
[86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58], 
[19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40], 
[ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66], 
[88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69], 
[ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36], 
[20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16], 
[20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54], 
[ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48]]

result = 0
factors = []

# finds highest in rows
for row in nums:
	for i in range(0, 17):
		product = row[i]*row[i+1]*row[i+2]*row[i+3] 

		if product > result:
			result = product
			factors = [row[i],row[i+1],row[i+2],row[i+3]] 
		i += 1
	
# finds highest in columns
for i in range(0, 17):
	for j in range(0, 20):
		product = nums[i][j]*nums[i+1][j]*nums[i+2][j]*nums[i+3][j]	

		if product > result:
			result = product
			factors = [nums[i][j],nums[i+1][j],nums[i+2][j],nums[i+3][j]]

# finds diagonal to the right
for i in range(0, 17):
	for j in range(0, 17):
		product = nums[i][j]*nums[i+1][j+1]*nums[i+2][j+2]*nums[i+3][j+3]

		if product > result:
			result = product
			factors = [nums[i][j],nums[i+1][j+1],nums[i+2][j+2],nums[i+3][j+3]]


# finds diagonal to the left
for i in range(16, -1, -1):
	for j in range(19, 2, -1):
		product = nums[i][j]*nums[i+1][j-1]*nums[i+2][j-2]*nums[i+3][j-3]

		if product > result:
			result = product
			factors = [nums[i][j],nums[i+1][j-1],nums[i+2][j-2],nums[i+3][j-3]]


print(result, factors)

The factors list is not necessary to solve the problem, but I prefer to keep it in there if only to see what exactly the computer is calculating. This code has four parts, which check the products of the adjacent horizontal, vertical, left-diagonal, and right-diagonal digits respectively.

# finds highest in rows
for row in nums:
	for i in range(0, 17):
		product = row[i]*row[i+1]*row[i+2]*row[i+3] 

		if product > result:
			result = product
			factors = [row[i],row[i+1],row[i+2],row[i+3]] 
		i += 1

Let’s look at line 26’s block first. The for loop finds each row in the grid, and puts it (as a list) into the variable row. For each row, i is the variable used to retrieve the ith element in the row (list). Since we’re looking for groups of four digits, the last four digits we need to test in each row are in positions 16, 17, 18, and 19 (remember, list positions start at 0). So i only has to go up to 16, since we find next three elements after i to multiply them. Every time four digits are multiplied, we check it against the previous largest product, and if it’s larger, the variable is overwritten with the that number. The four digits that are factors of the product are also stored.

# finds highest in columns
for i in range(0, 17):
	for j in range(0, 20):
		product = nums[i][j]*nums[i+1][j]*nums[i+2][j]*nums[i+3][j]	

		if product > result:
			result = product
			factors = [nums[i][j],nums[i+1][j],nums[i+2][j],nums[i+3][j]]

Next we tested vertically adjacent digits. In this case, i is the variable used to retrieve the ith element from nums, or in other words it retrieves the ith row in the grid. j is the variable used to find the jth element of that row. From a similar logic as before, the last group of rows we need to test are rows 16, 17, 18, and 19. Therefore, i only needs to go up to 16. However, j needs to go up to 19 because we need to go all the way to the end of each row and multiply the vertical column of digits below it. Four vertical digits are found by retrieving four adjacent rows (numbered i to i+3), then finding the same (jth) element of each. These four digits are then multiplied, and tested against product.

# finds diagonal to the right
for i in range(0, 17):
	for j in range(0, 17):
		product = nums[i][j]*nums[i+1][j+1]*nums[i+2][j+2]*nums[i+3][j+3]

		if product > result:
			result = product
			factors = [nums[i][j],nums[i+1][j+1],nums[i+2][j+2],nums[i+3][j+3]]

Diagonal to the right means that starting from any digit and going down diagonally, the last digit in that diagonal will be to the right of the initial digit. Again, i is used to find the ith row, and j is the jth element in that row. The ranges for i and j will become more obvious after explaining how the diagonal is found. So the first digit we find is in the ith row, at position j. The second digit is a row below that, at the i+1th row, and one position to the right, at j+1. This is repeated until the i+3rd row, where we will have a four digits that are diagonal to each other. Since the last digit is 3 down and 3 to the right of the initial digit, i (the row) and j (the element position) only have to go up to 16. Each product is checked against product.

# finds diagonal to the left
for i in range(16, -1, -1):
	for j in range(19, 2, -1):
		product = nums[i][j]*nums[i+1][j-1]*nums[i+2][j-2]*nums[i+3][j-3]

		if product > result:
			result = product
			factors = [nums[i][j],nums[i+1][j-1],nums[i+2][j-2],nums[i+3][j-3]]

Finding the diagonal to the left is a bit strange. We start from the 4th row from the bottom (nums[16]), and work our way up to the top row (nums[0]). Therefore, i, or the ith row, starts at 16 and goes to 0. Following a similar logic as before, since the final digit in the left-diagonal is 3 down and 3 to the left from the initial digit, j, or the jth element must start from 19 (the end of the row), up to 3 (4 from the left of the row). We test the left-diagonals starting from the right, and moving to the left, or incrementing j by -1. Each product is checked against product.

So after we test the horizontal, vertical, and diagonal products, we will have exhausted all possibilities and the variable product will be storing the largest product it found, and so we print.

Answer: 70600674 [89, 94, 97, 87]