Project Euler - Problem 50

Horray! Number 50! I've advanced to "level 2" on project euler!

Additionally, it appears I spoke to soon about the easy nature of recent problems! This one was very interesting and took me several attempts to get right. Here's the problem:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

My initial approach was to create my prime sieve up to 1000000, then iterate through each prime between 1000 and 1000000, and check for the ability to sum up to that prime number from lower primes. I assumed that in order to maximize the sequence length, the initial prime would be less than 100. Unfortunately this resulted in looping essentially 100,000,000 times, doing a simple summation calculation. The result was that I got the right answer, but it took over a minute to do so! Under project euler rules, the problems are designed to be solved in less than a minute. So back to the drawing board!

The better way was to create an array of prime summations, and then search through the various combinations in that array to find the maximum prime. Since by the time you hit prime # 548, your consecutive sum at that point is breaking 1 million, so that narrows the summation search down to measly ~300,000 iterations - much better!

So first generate my sieve:

var primes = CustomMath.Primes(1000000);

Then I went about creating the prime sum array, which was easy enough:

// create array of prime sums

var prime_sums = new List<int&gt();

prime_sums.Add(0);

prime_sums.Add(2);

int sum = 2;

for (int prime = 2; true; prime++)

{

if (primes[prime])

{

sum += prime;

prime_sums.Add(sum);

}

if (sum > 1000000) break;

}

Next, I searched through the resulting array to find the longest combo resulting in a prime:

int consecCount = 0;

int maxPrime = 0;

// find longest consecutive sequence that is prime

for (int i = 0; i < prime_sums.Count; i++)

{

for (int j = i + consecCount; j < prime_sums.Count; j++)

{

int diff = prime_sums[j] - prime_sums[i];

if (diff < 1000000 && primes[diff])

{

if (j - i > consecCount)

{

consecCount = j - i;

maxPrime = diff;

}

}

}

}

And that does it! The new code gives the correct answer - 997663 - in less than 40ms! What a relief! :)

Project Euler - Problem 48

After posting about Problem 49 and realizing it wasn't really all that interesting, I decided to backtrack a bit and post my solution to Problem 48 as well, which is a more interesting problem.

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Unfortunately C# can't handle large numbers like those required to perform a calculation such as 1000^1000. For earlier project euler problems I had built a few quick hack methods (BigMultiply and BigAdd) to calculate the results of operations on large numbers. But those are slow and we actually don't need them here. The key to doing this problem efficiently is to realize that since we only want the last 10 digits, those are the only digits we ever care about, throughout all operations.

Thusly....

public static ValueType Go()

{

Int64 seriesSum = 0;

for (Int64 i = 1; i < 1001; i++)

{

Int64 currentPower = i;

for (Int64 power = i; power > 1; power--)

{

currentPower = currentPower * i;

// only need last 10 digits

string pow = currentPower.ToString();

if (pow.Length > 10)

currentPower = Int64.Parse(pow.Substring(pow.Length - 10));

}

seriesSum += currentPower;

// only need last 10 digits

string sum = seriesSum.ToString();

if (sum.Length > 10)

seriesSum = Int64.Parse(sum.Substring(sum.Length - 10));

}

return seriesSum;

}

...and voila! Takes a mere 340ms to get the answer: 9110846700.

In general the problems lately have been quite trivial, so I haven't been posting solutions. Here's hoping something more intriguing shows up!

Project Euler - Problem 49

Today we'll look at problem 49 in project euler:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Simple, but interesting!

My strategy was to use my primes sieve to generate primes up to 10000, then look for series which were prime and permutations - brute force essentially.

The only piece of code I didn't have was a method to compare two numbers and evaluate if they were permutations of one another. So I came up with the following:

public static bool IsPermutation(int n1, int n2)

{

char[] ac1 = n1.ToString().ToCharArray();

char[] ac2 = n2.ToString().ToCharArray();

if (ac1.Length != ac2.Length) return false;

Array.Sort(ac1);

Array.Sort(ac2);

for (int i = 0; i < ac1.Length; i++)

if (ac1[i] != ac2[i]) return false;

return true;

}

Works well enough!

All that remains is some ugly nested loops and ifs:

var primes = CustomMath.Primes(10000);

for (int prime = 1489; prime < 10000; prime += 2)

{

if (primes[prime])

{

for (int nextPrime = prime + 2; nextPrime < 10000; nextPrime += 2)

{

int thirdPrime = 2 * nextPrime - prime;

if (thirdPrime.ToString().Length > 4) break;

if (primes[nextPrime] && primes[thirdPrime])

{

if (IsPermutation(prime, nextPrime) && IsPermutation(prime, thirdPrime))

{

var sb = new StringBuilder();

sb.Append(prime);

sb.Append(nextPrime);

sb.Append(thirdPrime);

return sb.ToString();

}

}

}

}

}

You'll notice I'm starting at 1489, the first odd digit above the given sequence. Yes, I did check from 1001 first, but it stopped after finding the sequence at 1487, so then I checked above that number. Runs in about 100ms.

For the curious, the next (and only other sequence) is:

2969

6299

9629

Project Euler - Problem 41

Project euler again! This time, a fun little one that looks for pandigital primes:

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, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

My strategy here was to utilize my Primes function to generate a boolean array of primes, and then check possible numbers against it. I also needed to utilize a method that checked if a number was pandigital or not.

public static bool IsPandigital(Int64 num)

{

string strNum = num.ToString();

int size = strNum.Length;

if (strNum.Contains("0"))

return false;

char[] digits = new char[size];

for (int i = 1; i <= size; i++)

digits[i - 1] = char.Parse(i.ToString());

char[] chars = strNum.ToCharArray();

if (chars.Intersect(digits).Count() == size && chars.Distinct().Count() == size)

return true;

return false;

}

Pretty simple here. First does a quick check: if a number contains a 0, it's not pandigital. Then, based on the size of the number, figures out which digits it'll check for (ie a 4 digit number needs to have 1, 2, 3, and 4) and then checks that the number contains each of those digits, and each one only once.

Great! Now we're ready to go. The only remaining problem is that the largest pandigital number is 987,654,321 - almost 1 billion! That's a little bit too big for my boolean prime array to handle - it tops out around 300 million. Fortunately, we can eliminate 9 and 8 digit pandigital numbers as candidates for primality.

How do we do that? Well, one test for primality is to sum the digits of a number and find out if it's evenly divisible by 3. Since 9+8+7+6+5+4+3+2+1 = 45, which is divisible by 3, no 9 digit pandigital number is prime. Same for 8 digit pandigitals. Thus our ceiling is only 7,654,321 - just a little over 7 million!

Final code to get the answer:

public static ValueType Go()

{

// we can eliminate 9 and 8 digital pandigitals because their sum is divisble by three, and hence not prime.

var primes = CustomMath.Primes(7654321);

int nMax=0;

for (int i = 1; i < 7654321; i+= 2)

if (i < primes.Length)

if (primes[i] && CustomMath.IsPandigital(i))

nMax = i;

return nMax;

}

The answer is 7652413. This code runs a little bit more slowly than most - executing in 1422ms. I could probably optimize it futher, but it gets the job done well!

Project Euler - Problem 39

Today's project euler problem was quite interesting:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p <= 1000, is the number of solutions maximised

First off, for a right triangle with integer values, we know the following:

A = 2*x*n - x^2

B = 2*n^2 - 2*x*n

C = 2*n^2 - 2*x*n + x^2

Where x%2 = 1, and n>x

From this we can craft a simple formula for the perimeters of such triangles:

A+B+C = P = 4*n^2 - 2*x*n

What we need to do then, is for each potential value of x and n, figure out the perimeter and count. I create an integer array, where the index = P, and increment it everytime I get a P < 1000:

// calculate solutions

int[] solutions = new int[1001];

for (int x = 1; x < 1001; x += 2)

{

for (int n = x + 1; ; n++)

{

int p = 4 * n * n - 2 * x * n;

if (p > 1000) break;

for (int m = p; m < 1001; m += p)

{

if (m > 1000) break;

solutions[m]++;

}

}

}

Now it's simple: just find out which perimeter value occurred the most:

// find the maximum count

int ans = 0;

int maxCount = 0;

for (int i = 0; i < 1001; i++)

{

if (solutions[i] > maxCount)

{

maxCount = solutions[i];

ans = i;

}

}

And we're done! The answer turns out to be P = 840. The code executes in < 1ms! Awesomeness!

Project Euler - Problem 38

Lately I've been mildly obsessed with projecteuler.net. Fun math problems! And it's been a good exercise in both my mathematical skills as well as my programming skills. Today I'd like to present some code I used to solve problem #38:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Knee deep already in project euler by now, I've already had to develop code for primes. This following snippet populates a boolean array with true/false, if the index is prime or not. Makes for very fast and easy prime checking! It generates the prime list based on a sieve method.

public static bool[] Primes(Int64 num)

{

bool[] abPrimes = new bool[num];

for (int i = 0; i < num; i++)

abPrimes[i] = true;

for (int i = 2; i < num; i++)

{

if (abPrimes[i])

{

int x = i << 1;

while (x < num)

{

abPrimes[x] = false;

x += i;

}

}

}

abPrimes[0] = false;

abPrimes[1] = false;

return abPrimes;

}

Anyhow, that's all I needed to complete this problem. But I thought I'd have a little fun and so I wrote code to deliver numbers that would be logically truncatable as primes. That is to say, they could start with 2,3,5,7,9, end in only 3 or 7, and contain 1,3,7,or 9 for middle digits.

Wielding a little recursion and yield return powa:

public static IEnumerable GetTruncatablePrimes()

{

var sb = new StringBuilder("1");

while (true)

{

foreach (var item in SetDigit(sb, 0))

yield return item;

sb.Insert(0, "0");

}

}

private static IEnumerable SetDigit(StringBuilder sb, int index)

{

string position = "";

if (index == 0)

position = "first";

else if (index == sb.Length - 1)

position = "last";

foreach (Int64 digit in GetPrimeDigits(position))

{

sb[index] = char.Parse(digit.ToString());

if (index != sb.Length - 1)

foreach (var item in SetDigit(sb, index + 1))

yield return item;

else

yield return Int64.Parse(sb.ToString());

}

}

private static IEnumerable GetPrimeDigits(string position)

{

int[] digits;

switch (position)

{

case "first":

digits= new[] { 2, 3, 5, 7, 9 };

break;

case "last":

digits = new[] {3, 7 };

break;

default:

digits = new[] { 1, 3, 7, 9 };

break;

}

foreach (int d in digits)

yield return d;

}

Now that I had a list of potential digits, I just needed to see if they were prime, and if their truncated versions were prime:

//Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

public static Int64 Go()

{

bool[] abPrimes = CustomMath.Primes(1000000);

Int64 sum = 0;

int counter = 0;

foreach (var prime in GetTruncatablePrimes())

{

// exceptions - single digits don't count

if (prime.ToString().Length <2)

continue;

if (abPrimes[prime])

{

// check left truncation

Int64 left = prime;

while (left.ToString().Length > 1 && abPrimes[left])

left = TruncateLeft(left);

// check right truncation

Int64 right = prime;

while (right.ToString().Length > 1 && abPrimes[right])

right = TruncateRight(right);

// check if both left and right truncation was successful

if (left.ToString().Length == 1 && abPrimes[left] && right.ToString().Length == 1 && abPrimes[right])

{

sum += prime;

if (++counter == 11)

break;

}

}

}

return sum;

}

private static Int64 TruncateLeft(Int64 number)

{

return Int64.Parse(number.ToString().Remove(0, 1));

}

private static Int64 TruncateRight(Int64 number)

{

return Int64.Parse(number.ToString().Remove(number.ToString().Length-1, 1));

}

And that's it! The entire deal runs in about 50ms. Generally speaking, all project euler problems are designed to be computable in under 1 minute - but I'm always looking for the absolutely fastest possible methods. I initally had some code in there to continue checking primality if the potential primes were outside the bounds of the array, but that proved unnecessary.

The only 11 primes that fit the bill are:

23

37

53

73

313

317

373

797

3137

3797

739397

Why

Lately I've become compulsive about plowing through the problems located at projecteuler.net. But this blog isn't all about those problems. It's mostly going to be a place where I can post whatever is going on at any particular time. There will be code, recipes, thoughts and questions.

Mostly this blog is for my own personal enjoyment. But if you do get something out of it, that's great!