Archive | December, 2011

Problem Thirty Two

14 Dec

Here’s problem thirty two:

Question: Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

This is simply a case of looping and creating a function that tests if a given input is pandigital. Again, the upper bounds on the for loops were a bit tricky. I set the limit at 10,000 since the total number of digits cannot exceed 9, so the maximum situation that can occur is 9999 * 1 = 9999 (9 digits).

Here’s the code:

def isPandigital19(s):
	return '0' not in s and len(s) == 9 == len(set(s))

result = set()

for n in range(2, 10000):
	for m in range(2, 10000):
		if n * m > 10000: continue
		elif isPandigital19(str(n)+str(m)+str(n*m)):
			result.add(n*m)

print(sum(result))

So the result is stored in a set, since there could be duplicate multiplicand/multiplier/product pandigitals. We iterate through the possibilities using two for loops, and quickly check if the product is greater than 10,000 to skip to the next iteration. This is because if the product is over 10,000, the total digits of it and its factors are guaranteed to be over 9 digits. Only then do we check if the identity is pandigital using the function isPandigital19().

This function essentially checks the to see if the length of the string (of the identity) is 9 (9 digits), and if there are no duplicates by also testing the set of the string. However, 0 cannot be a digit in the identity since we’re only concerned with the digits 1-9, so that test is also included in the function. The function returns a true or false value, and the rest is self-explanatory.

Answer: 45228

Problem Thirty One

7 Dec

Here’s problem thirty one:

Question: How many different ways can £2 be made using any number of coins?

My solution to this wasn’t very pretty — just look at the monstrous for loop below.

result = 2

for b in range(2):
	for c in range(5):
		if 100*b + 50*c > 200: continue
		for d in range(11):
			if 100*b + 50*c + 20*d > 200: continue
			for e in range(21):
				if 100*b + 50*c + 20*d + 10*e > 200: continue
				for f in range(41):
					if 100*b + 50*c + 20*d + 10*e + 5*f > 200: continue
					for g in range(101):
						if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g > 200: continue
						for h in range(201):
							if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + h == 200:
								result += 1

print(result)

Yeah…zero points for style there. I know for a fact that there is a “clever” way of solving this problem, but its explanation was pretty over my head. Essentially this code works by trying (almost) every combination of coins possible and testing it to see if its value is 200. This is slightly streamlined by initially considering two possibilities, 200 and 100 + 100, so that there are less total calculations. This is the reason why result is initialized to 2 and there is no loop for the 200 coin. The number of calculations is also reduced by continuing (skipping to the next iteration) the for loop whenever the current value is greater than 200, which also skips all corresponding inner nested loops.

This slight detail allows us to skip most of the 1,922,707,710 calculations needed for a complete brute force solution, and returns an answer in a reasonable amount of time.

Answer: 73682

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 Nine

5 Dec

Here’s problem twenty nine:

How many distinct terms are in the sequence generated by a^b for 2<=a<=100 and 2<=b<=100?

This is remarkably simple in Python.

Here it is:

result = {a**b for a in range(2, 101) for b in range(2, 101)}
print(len(result))

A set is used to keep track of unique elements (note the curly braces), and a list comprehension with two for loops are used to generate the values. The length of the set is printed at the end.

Answer: 9183

Problem Twenty Eight

4 Dec

Here’s problem twenty eight:

Question: What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral?

My initial solution to this problem was quite different from my final one. I intended to make the spiral into a one-dimensional list, and since the diagonal digits occur at a regular rate, a couple of counters could keep track of which position was actually on a diagonal. This was slightly more complicated than I foresaw, but it did succeed in the end, albeit very messily. Looking through the answer forums, I discovered another way of approaching this problem. The spiral could be seen as concentric squares, and all that was needed was to find the corners of each square.

Take a look:

result = 1
for i in range(3, 1002, 2):
	result += (i*i) + (i*i-i+1) + (i*i-2*i+2) + (i*i-3*i+3) 
	
print(result)

I think you’ll agree that this is rather succinct (perhaps not the result += line, but I did not combine the expressions algebraically for sake of clarity). Viewing the spiral as a bunch of concentric squares, the dimensions are 1×1, 3×3, 5×5 … 1001×1001. It is unnecessary to calculate the value of the center of the square, which is why the for loop starts with (a square of length) 3 and result is initialized to 1. It is incremented by two, and you can see why by looking at the dimensions of the squares.

Now we have to find the values of the corners of a square with dimensions ixi. It’s important to note that the square is still technically constructed from a spiral; the numbers start from the center and spiral outward; they do not start on the border of the square. If the square is constructed in this manner, then we know somewhat intuitively that the top right corner is simply i2, or i*i. The top left corner’s equation was pretty much found by guess and check. The bottom two corners were slightly harder to find just by looking at the pattern of numbers, so I resorted to using the ever-handy regression function on my TI-84. These two equations were found to be i2-2i+2 and i2-3i+3, respectively. We add all of these corners into the result variable, and print at the end.

Answer: 669171001