Truncating an integer from left to right and right to left

Question

Project Euler problem 37 says:

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.

Going right to left is trivial enough as you just keep dividing by 10:

IEnumerable<long> RTL (long x)
{
 while(x > 10) {
 x /= 10;
 yield return x;
 }
}

Going left to right was a little trickier. Just wondering if there's a more optimal way to do this.

IEnumerable<long> LTR (long x)
{
 while(x > 10) 
 {
 long y = x; //take a copy of current value of x;
 int powerten = 0; //variable to count what the 10^n value is
 while(y > 10){ //calculate powerten by repeated dividing y / 10
 y /= 10; // for 3797 this would be '3' i.e. 3.797 * 10^3
 powerten++;
 }
 long p = (long)Math.Pow(10, powerten); // 10 ^ 3 = 1000
 long z = (x/p)*p; // 3797/1000*1000 = 3000
 x = (x - z); // subtract from x
 yield return x;
 }
}

It runs pretty fast but I'm just wondering is there a more optimal way to remove the leftmost significant digit of a number on each iteration without all the "gymnastics".

Answer 1

I would suggest returning the truncations in order of increasing lengths for truncation from the left (checking the shorter tails for primality is faster, so if the number is not a left-truncatable prime, that should be detected faster on average when the tails are yielded in that order),

IEnumerable<long> LTR (long x)
{
 long powerOfTen = 10;
 while(powerOfTen <= x)
 {
 long tail = x % powerOfTen;
 powerOfTen *= 10;
 yield return tail;
 }
}

is nice and short if you know that the argument x is never so large that the next larger power of 10 exceeds long range. I f x may be that large, you need to guard against overflow, slightly longer:

IEnumerable<long> LTR(long x)
{
 // if (x < 10) return ??;
 long bound = x/10, lastPowerOfTen = 1;
 while(lastPowerOfTen <= bound)
 lastPowerOfTen *= 10; // doesn't overflow
 }
 long powerOfTen = 1;
 do
 {
 powerOfTen *= 10;
 yield return x % powerOfTen;
 }while(powerOfTen < lastPowerOfTen);
}

If you want to return the truncations in order of decreasing lengths, you can easily modify the last:

IEnumerable<long> LTR(long x)
{
 // if (x < 10) return ??;
 long bound = x/10, powerOfTen = 1;
 while(powerOfTen <= bound)
 powerOfTen *= 10; // doesn't overflow
 }
 while(powerOfTen > 1)
 {
 x %= powerOfTen;
 powerOfTen /= 10;
 yield return x;
 }
}

Note: If the decimal representation of x contains at least one zero other than the last digit, these would all return the same value more than once. Since no (right or left) truncatable prime can have a zero digit in its decimal expansion, I did not care about that. If you do, in the last (decreasing length) version, you could easily avoid that by replacing

powerOfTen /= 10;

with a loop

do {
 powerOfTen /= 10;
}while(powerOfTen > 1 && powerOfTen > x);

In the increasing-length versions, that would not be as simple.

Further note:

long p = (long)Math.Pow(10, powerten);

Don't use floating point functions for integer arithmetic. In this case, if the called Math.Pow function operates on doubles [I'm not sure how that is in C#], it will not lead to wrong results, but it could produce wrong results if it operates on floats, and also in general (for other bases) even if double is used.

• Eoin Campbell: excellent :-) cheers for review