Challenge: Digit Fifth Powers

Posted on: August 23, 2017 11:28:58 PM

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 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.

This is another relatively straight forward challenge where a modified brute force approach is fastest. I cached the 0-9 fifth powers so they wouldn't always need to be calculated and based on those results, it was clear that a good starting point was 35 since there was no possible way it could be anything between 25 and 35. The next step is finding an upper bound. I started by taking 5x95 and found that the result contained 6 digits. So I put the upper bound to 6x96 to support the 6 digits. The rest is just letting it loop and finding if the on going sum is larger than the initial number.
Program.cs
using System;
using System.Diagnostics;

namespace Project_Euler_30
{
    internal class Program
    {
        // 5x9^5 has 6 digits, so the upper bound should be 6x9^6
        private const int UpperBound = 59049 * 6;

        private static readonly int[] powersCache = new int[] { 0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049 };

        private static void Main(string[] args)
        {
            Stopwatch sw = Stopwatch.StartNew();
            int result = 0;

            // start the loop at 243 since that is the lower bound (3^5) of a possible sum
            for(int i = powersCache[3]; i <= UpperBound; i++)
            {
                int sum = 0;
                int workingNumber = i;

                while(workingNumber > 0)
                {
                    int digit = workingNumber % 10;
                    workingNumber /= 10;

                    sum += powersCache[digit];

                    if(sum > i)
                    {
                        // passed the number, stop checking
                        break;
                    }
                }

                if(sum == i)
                {
                    result += i;
                }
            }
            sw.Stop();

            Console.WriteLine($"Sum of results: {result}");
            Console.WriteLine($"Took {sw.ElapsedMilliseconds}ms");
        }
    }
}

Challenge: Distinct Powers

Posted on: August 23, 2017 10:17:27 PM

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?

This was very straight forward for me. The most simple way to do this is a simple brute force option. There are ways to calculate out most of the duplicates, but those calculations end up taking longer than 2 simple loops and feed the results into a hashset to guarantee uniqueness to get the answer.
Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Project_Euler_29
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            Stopwatch sw = Stopwatch.StartNew();
            HashSet<double> results = new HashSet<double>();

            for (int a = 2; a <= 100; a++)
            {
                for (int b = 2; b <= 100; b++)
                {
                    results.Add(Math.Pow(a, b));
                }
            }

            sw.Stop();

            Console.WriteLine($"Number of distinct powers: {results.Count}");
            Console.WriteLine($"Took {sw.ElapsedMilliseconds}ms");
        }
    }
}

Challenge: Number Spiral Diagnols

Posted on: June 14, 2017 12:17:51 AM
Another project euler challenge that states:

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?

I found this challenge to be very straight forward in how I would solve it. I know that there is an algebraic way to do it, but I didn't want to find/figure that equation out. I found that the top right corner is going to be the square of the size of the square, so 10012. From there, I can use simple subtraction to find the other corners. Then to get the next number to square will be the floor value of the root value of the bottom left corner. From there, it's a simple loop to go through all values.
Program.cs
using System;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_28
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            const int squareSize = 1001;

            Stopwatch sw = Stopwatch.StartNew();

            int half = (int)Math.Ceiling(squareSize / 2D) - 1;
            int[] topRight = new int[half];
            int[] topLeft = new int[half];
            int[] bottomLeft = new int[half];
            int[] bottomRight = new int[half];

            int idx = 0;
            for (int i = squareSize; i > 1;)
            {
                topRight[idx] = i * i;
                topLeft[idx] = topRight[idx] - i + 1;
                bottomLeft[idx] = topLeft[idx] - i + 1;
                bottomRight[idx] = bottomLeft[idx] - i + 1;

                i = (int)Math.Floor(Math.Sqrt(bottomRight[idx]));

                idx++;
            }

            sw.Stop();

            Console.WriteLine($"Sum of diagonols: {topRight.Sum() + topLeft.Sum() + bottomLeft.Sum() + bottomRight.Sum() + 1} in {sw.ElapsedTicks} ticks");
        }
    }
}

Challenge: Quadratic Primes

Posted on: June 13, 2017 1:13:31 AM
Here is another project euler challenge that states:

Euler discovered the remarkable quadratic formula:

n2 + n + 41

It turns out that the formula will produce 40 primes for the consecutive integer values 0 ≤ n ≤ 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 412 + 41 + 41 is clearly divisible by 41.

The incredible formula n2 - 79n + 1601 was discovered, which produces 80 primes for the consecutive values 0 ≤ n ≤ 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n2 + 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.

I tried to find a way to do this outside of brute force, but I couldn't find any fancy formulas or theorems. Knowing that n=0 has to equal a prime number, it was pretty easy to severely narrow down the number of values for b needing to be tested though. n=0, 02 + a(0) + b = b which means b absolutely must be prime. Once you know that b is a prime number, you can also narrow down the values for a by setting n=1. n=1, 12 + a(1) + b = 1 + a + b This result means that, in order to get a prime result, a must be an odd number except when b is 2. This is because all primes, aside from 2, are odd. Knowing this, we can now do a smarter brute force attempt to find the answer.
Program.cs
using Common.Math;
using System;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_27
{
    internal class Program
    {
        private static int[] primeCache = Eratosthenes.GetPrimes(1000).ToArray();

        private static bool IsPrime(int num)
        {
            if (num > primeCache.Last())
            {
                primeCache = Eratosthenes.GetPrimes(primeCache.Last() * 2);
            }

            // array.contains checks every value, these are in order from smallest to largest
            // so creating our own contains is more efficient.
            int i = 0;
            while (i < primeCache.Length && primeCache[i] < num)
            {
                i++;
            }

            return primeCache[i] == num;
        }

        private static void Main(string[] args)
        {
            Stopwatch sw = Stopwatch.StartNew();
            ResultHelper result = new ResultHelper();

            // 'b' must be prime because when n=0 we get 0^2 + a(0) + b which is just 'b'
            // since 0 is inclusive and all results must be prime, we can narrow down 'b' to just prime numbers
            int[] bPossibles = primeCache;

            // we can also narrow down 'a' possiblities because all primes except for 2 are odd
            // so if n=1 we get 1^2 + a(1) + b = 1 + a + b
            // since an odd added to an odd is always even, we know that for all cases except 2 'a' must be odd
            // in the case of 2 'a' must be even
            for (int a = -999; a < 1000; a += 2)
            {
                for (int bIdx = 0; bIdx < bPossibles.Length; bIdx++)
                {
                    // handle the case of b=2
                    int workingA = bPossibles[bIdx] == 2 ? a - 1 : a;

                    int n = 0;
                    while (IsPrime(Math.Abs(n * n + workingA * n + bPossibles[bIdx])))
                    {
                        n++;
                    }

                    if (result.Count < n)
                    {
                        result = new ResultHelper
                        {
                            A = a,
                            B = bPossibles[bIdx],
                            Count = n
                        };
                    }
                }
            }

            sw.Stop();

            Console.WriteLine($"{result.Count} primes found in {sw.ElapsedMilliseconds}ms when a={result.A} and b={result.B} with a product of {result.A * result.B}.");
        }

        private struct ResultHelper
        {
            public int A;
            public int B;
            public int Count;
        }
    }
}

Challenge: Largest Reciprocal Cycle

Posted on: June 9, 2017 2:05:16 AM
This is another project euler challenge that states:

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.

This problem required me to do quite a bit of research on decimals with recurring cycles. I came across a wikipedia article that led me to Fermat's Little Theorem to get the number of digits in the cycle, aka, the period. From there, the problem was easy to solve.
Program.cs
using Common.Math;
using System;

namespace ProjectEuler_26
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            Tuple result = new Tuple(0, 0);

            // start by getting primes up to 1000
            var primes = Eratosthenes.GetPrimes(1000);

            // loop backwards
            for (int i = primes.Length - 1; i >= 0; i--)
            {
                int count;

                // we know that the most a cyclical decimal will repeat is d-1
                if ((count = GetCyclicalCount(primes[i])) == primes[i] - 1)
                {
                    result = new Tuple(count, primes[i]);
                    break;
                }
            }

            Console.WriteLine($"The value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part is {result.Item2} with {result.Item1} numbers in the cycle.");
        }

        private static int GetCyclicalCount(int prime)
        {
            int period = 1;

            // using Fermat's Little Theorim you can get the count of numbers in the cycle referred to as a period
            // Fermat's Little Theorim is defined as a^p=a%p
            // where a is the number base and p is a prime of that number base
            // this means that the count of cyclical numbers is the first modular power where the period test is not 1

            while (ModularPow(10, period, prime) != 1)
            {
                period++;
            }

            return period;
        }

        private static int ModularPow(int @base, int exponent, int modulus)
        {
            if (modulus == 1) return 0;

            int result = 1;
            for (int i = 1; i <= exponent; i++)
            {
                result = (result * @base) % modulus;
            }

            return result;
        }
    }
}
The code is pretty well documented and explains what it's doing at just about every step. Enjoy!