### Archive

Posts Tagged ‘project euler’

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

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:

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

```

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

Categories: Programming Tags:

## 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, 402 + 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² − 79n + 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.

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
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;

return 0;
}

```

max_a: -61
max_b: 971
max_count: 71

real 0m1.584s
user 0m1.528s
sys 0m0.062s

Categories: Programming

## 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
real 0m0.087s
user 0m0.030s
sys 0m0.046s

Categories: Programming

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

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, 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