Category Archives: Euler

Ruby: Project Euler Problem # 58

http://projecteuler.net/problem=58

Spiral primes

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Ruby: Solution to Project Euler Problem # 28

http://projecteuler.net/problem=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?

Ruby: Solution to Project Euler Problem # 25

Recently, I’ve been typing more Ruby then usual. In Ruby you can have a fairly big number.
http://projecteuler.net/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.

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?

C#: Project Euler Solution to Problem 27

http://projecteuler.net/problem=27

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.

static void Main(string[] args)
{
    //n² + an + b
    int maxprimes = 0;
    int maxproduct = 0;
    for (int a = 0; a < 1000; a++)
    {
        for (int b = 0; b < 1000; b++)
        {
            int prime = countPrime(a, b);
            if (maxprimes < prime)
            {
                maxprimes = prime;
                maxproduct= (-a*b );
            }
        }
    }
    Console.WriteLine(maxproduct);
}
 
public static int countPrime(int a, int b)
{
    int count = 0;
    int n = 0;
    while (true)
    {
        double result = Math.Pow(n, 2.00) - (a * n) + b;
        if (isPrime((int)result) && result >= 0)
            count++;
        else
            return count;
        n++;
    }
}
 
public static bool isPrime(int n)
{
    if (n == 1)
        return false;
    if (n == 2)
        return true;
    for (int i = 2; i < n; ++i)
    {
        if ((n % i) == 0)
            return false;
    }
    return true;
}

C#: Project Euler Solution to Problem 32

http://projecteuler.net/problem=32

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 x 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

public static LinkedList<string> onetonine = new LinkedList<string>();
static void Main(string[] args)
{
    LinkedList<int> distinct_product = new LinkedList<int>();
    int product = 0;
    for (int a = 1; a < 2000; a++)
    {
        for (int b = 1; b < 2000; b++)
        {
            product = a * b;
 
            if (isDigits(a + "" + b + "" + product))
            {
                if (!distinct_product.Contains(product) )
                    distinct_product.AddLast(product);
            }
        }
    }
    int sum = 0;
    foreach (int prod in distinct_product)
        sum += prod;
    Console.WriteLine("sum : "+sum);
}
 
public static bool isDigits(string s)
{
    onetonine.Clear();
    onetonine.AddLast("1");
    onetonine.AddLast("2");
    onetonine.AddLast("3");
    onetonine.AddLast("4");
    onetonine.AddLast("5");
    onetonine.AddLast("6");
    onetonine.AddLast("7");
    onetonine.AddLast("8");
    onetonine.AddLast("9");
    if (s.Length != 9)
        return false;
    for (int i = 0; i < s.Length; i++)
    {
        if (onetonine.Contains("" + s[i]))
            onetonine.Remove("" + s[i]);
        else
            return false;
    }
    return true;
}