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

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

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

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

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

Answer: 669171001
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.

Considering quadratics of the form:

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;
    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:

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
Answer: 4782

real 0m0.276s
user 0m0.125s
sys 0m0.109s