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

## Project euler 27: Quadratic primes

Euler discovered the remarkable quadratic formula:

*n*² + *n* + 41

It turns out that the formula will produce 40 primes for the consecutive values *n* = 0 to 39. However, when *n* = 40, 40^{2} + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when *n* = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula *n*² − 79*n* + 1601 was discovered, which produces 80 primes for the consecutive values *n* = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² +an+b, where |a| < 1000 and |b| < 1000where |n| is the modulus/absolute value ofn

e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, *a* and *b*, for the quadratic expression that produces the maximum number of primes for consecutive values of *n*, starting with *n* = 0.

**Solution:**

It is self explanatory.

#include <iostream> #include <vector> #include <cmath> using namespace std; #define MAX 100000 vector <long> prime(0); bool * seive_helper(bool primes[], int range) { for (int i = 3; i <= range / 2 ; ++i, ++i) { for(int j = i * 3; j <= range ; j += (i << 1)) { primes[j] = true; } } } void seive(int range) { int count = 0; bool primes[MAX] = {false}; for(int i = 4; i <= range; ++i, ++i) { primes[i] = true; } seive_helper(primes, range); for(int i = 2; i <= range; ++i) { if (!primes[i]) { prime.push_back(i); } } } bool isPrime(long num, int range) { int i = 0; while (i <= range) { if (num == prime[i]) return true; else if (num < prime[i]) return false; i++; } return false; } int main() { long long sum = 0; int max_count = 0; int max_a; int max_b; seive(10000); for (int i = -1000; i <= 1000; i++) { for(int j = -1000; j <= 1000; j++) { int n = 0; int count = 0; while(isPrime(n * n + i * n + j, 10000)) { count++; n++; } if (count > max_count) { max_count = count; max_a = i; max_b = j; } } } cout<<"max_a: "<<max_a<<endl; cout<<"max_b: "<<max_b<<endl; cout<<"max_count: "<<max_count<<endl; cout<<"Answer: "<<(max_a * max_b)<<endl; return 0; }

max_a: -61

max_b: 971

max_count: 71

Answer: -59231

real 0m1.584s

user 0m1.528s

sys 0m0.062s

## Project euler 26: Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

**Solution:**

I solved this problem in a bruteforce manner. Divisor keeps incrementing from 2 to 1000.

We store the reminder instead of quotient in an array. When the same reminder repeats we know there is a recurring cycle. The maximum of that recurring cycle is the answer.

#include <iostream> #include <stdio.h> using namespace std; int max(int a, int b) { return (a > b) ? a: b; } int remArray[2000]; int divideByOne(long divisor) { int term = 0; long mul = 1; for(int i = 0; i < 2000; i++) remArray[i] = 0; while (mul != 0 && term < 2000) { term++; mul *= 10; mul %= divisor; if (remArray[mul] != 0) break; remArray[mul] = term; } return term; } int main() { int max_val = 0; for(int i = 2; i <= 1000; i++) max_val = max(max_val, divideByOne(i)); cout<<max_val; return 0; }

time ./a.exe

Answer: 983

real 0m0.087s

user 0m0.030s

sys 0m0.046s

## project euler: Problem 25 1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

F

_{n}= F_{n−1}+ F_{n−2}, where F_{1}= 1 and F_{2}= 1.

Hence the first 12 terms will be:

F

_{1}= 1

F_{2}= 1

F_{3}= 2

F_{4}= 3

F_{5}= 5

F_{6}= 8

F_{7}= 13

F_{8}= 21

F_{9}= 34

F_{10}= 55

F_{11}= 89

F_{12}= 144

The 12th term, F_{12}, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution:

This problem is straight forward. A very simple python code as follows

def func(): f1 = 1 f2 = 1 term = 2 while len(str(f2)) != 1000: term += 1 f1, f2 = f2, f1 + f2 print term func()

time python fibo.py

Answer: 4782

real 0m0.276s

user 0m0.125s

sys 0m0.109s