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.