Archive

Archive for July, 2015

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

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

Categories: Programming Tags: ,

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 &gt; 0):
sum +=powrs(int(n % 10), pw)
n /= 10
if sum &gt; 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

Categories: Programming Tags: ,

Project euler 29: Distinct powers

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=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 ab 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):
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)

Categories: Programming Tags: ,

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