4
\$\begingroup\$

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".

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ excellent :-) cheers for review \$\endgroup\$ May 30, 2013 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.