Project Euler, Problems 33 and 37

Another two problems solved; I wish I could say that I simply sat down and thought of an efficient algorithm first go, but that's really not the case. With the first of those I've mentioned today I basically got two of them just by thinking. The final one came about basically because I finally put enough restrictions on things to force out a small number of choices to manually inspect.

It's a victory... Maybe not a noble win, but still. Onwards and upwards! Eleven more to go...

The second of the two that I've written a bit about here was a bit easier, it was basically just coding something and then sitting back to let it run.

Problem 33
The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s. We shall consider fractions like, 30/50 = 3/5, to be trivial examples. There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

So, for this puzzle it was effectively a case of searching through a series of pairs of numbers for certain conditions. First of all run through numbers a from 11 to 98, and for each of these go through numbers b from a+1 to 99. We consider fractions a divided by b (as this guarantees that the fraction will be less than 1). Eliminate any where a or b is divisible by 10. Sort out the pairs such that we have numbers which are coprime (that is, they share no common factors) and so that they have at least one digit the same.

I created two subroutines for this: the first checked if two numbers were coprime, and the second figured out the biggest common factor of two non-coprime numbers. This made simplifying things easier, and helped to exclude lots of cases. It would have been a little tricky (due to the depth of my knowledge of C++) to just create a routine which found the four things that we wanted, and so I just basically kept adding conditions and narrowing the number of pairs of numbers down and down until there were sufficiently few that I could look over them.

Problem 37
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.

This was quite straightforward really, it just took a bit of programming to sort through the possibilities; as the number of digits grows the number of things that have to be considered increases too. It just took a little time, and I gradually increased the number of digits. The largest had six digits, and it took a while to search through (of course, I wasn't searching through every six digit number, only the odd ones, and excluded any which a 0 digit in the middle, or started with 4,6,8 or 9) and consider all of the extra little cases.

The thing which I'm still thinking about with this, is from the set up in the question: "Find the sum of the only eleven primes that are both truncatable from left to right and right to left." So there are only eleven primes that satisfy this, huh? I wonder how we can prove that those are the only ones? My program has shown that there are only eleven primes satisfying that condition up to one million... Why are there none beyond that?