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
No comments:
Post a Comment