## Project euler 31: Coin sums

https://projecteuler.net/problem=31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

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

Solution:

This a very nice Dynamic programming question:

def noOfCoins(coins, n): noOfWays= [x * 0 for x in range(n + 1)] noOfWays[0] = 1 for i in range(len(coins)): for j in range(coins[i], n + 1): noOfWays[j] = noOfWays[j] + noOfWays[j - coins[i]] return noOfWays[n] if __name__ == '__main__': coins = [1,2,5,10,20,50,100,200] n = 200 print(noOfCoins(coins, n))

Answer: 73682

Time Complexity: O(number of available coins * n) ~ o(N)

Space Complexity: O(N)

## Project euler 30: Digit fifth powers

https://projecteuler.net/problem=30

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 1^4 + 6^4 + 3^4 + 4^4

8208 = 8^4 + 2^4 + 0^4 + 8^4

9474 = 9^4 + 4^4 + 7^4 + 4^4

As 1 = 1^4 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

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

Solution:

It is straight forward answer.

def powrs(n, pw): prod = 1 for i in range(0, pw): prod *= n return int(prod) def sumdigitpows(n, pw): sum = 0 orig = n while (n > 0): sum +=powrs(int(n % 10), pw) n /= 10 if sum > orig: return 0 return int(sum) def fifthpowers(): pw = 5 sum = 0 for i in range(1000, 10000000): if i == sumdigitpows(i, pw): sum += i print (i) print ("Answr: %s" % str(sum)) if __name__ == '__main__': fifthpowers()

Answr: 443839

## Project euler 29: Distinct powers

Consider all integer combinations of *a*^{b} for 2 ≤ *a* ≤ 5 and 2 ≤ *b* ≤ 5:

2

^{2}=4, 2^{3}=8, 2^{4}=16, 2^{5}=32

3^{2}=9, 3^{3}=27, 3^{4}=81, 3^{5}=243

4^{2}=16, 4^{3}=64, 4^{4}=256, 4^{5}=1024

5^{2}=25, 5^{3}=125, 5^{4}=625, 5^{5}=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by *a*^{b} for 2 ≤ *a* ≤ 100 and 2 ≤ *b* ≤ 100?

def distpowers(n): a={2} # initialize the set d={} # map for total number of elements for each power s=[0 for x in range(n + 1)] for i in range(1, 8): for j in range(2, n + 1): a.add(i * j) d[i]=len(a) tot = 0 for i in range (2, n + 1): if s[i] == 0: prod = i power = 0 while prod <= n: s[prod] = 1 prod *= i power += 1 tot += d[power] print (tot) if __name__ == '__main__': distpowers(100)

Time complexity O(8 * n) ~ O(n)

Space complexity O(n)

Answer: 9183

## Project euler 28: Number spiral diagonals

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

**21** 22 23 24 **25**

20 **7** 8 **9** 10

19 6 **1** 2 11

18 **5** 4 **3** 12

**17** 16 15 14 **13**

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

def diag(n): sum = 0 for i in range(0, int(n / 2) + 1): sum += (2 * i + 1) * (2 * i + 1) sum += (4 * i * i + 1) sum += (2 * i + 1) * (2 * i + 1) - 2 * i sum += (2 * i + 1) * (2 * i + 1) - 6 * i return sum - 3 print (diag(1001))

Answer: 669171001

Time complexity: O(4 * n / 2) ~ O(n)

Space complexity: O(1)