Need help solving Project Euler problem 200

Question

I am trying to formulate an algorithm to solve Project Euler's Problem 200.

We shall define a sqube to be a number of the form, p²q³, where p and q are distinct primes. For example, 200 = 5²2³ or 120072949 = 23²61³.

The first five squbes are 72, 108, 200, 392, and 500.

Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.

Find the 200th prime-proof sqube containing the contiguous sub-string "200".

Can someone please point me in the right direction to help me solve this problem?

Answer 1

I'm not sure this is a great SO question, but this should get you started at least.

Algorithmically, the brute force and ignorance approach to this should be pretty straightforward:

1. Start with set of primes P
2. Generate "squbes" by looking at all ordered pairs (p1,p2) with p1,p2 in P
3. Order this list, call the set S (think: how can you do this while generating them)
4. Test each s in S in turn, looking for substring 200
5. If s contains "200" test each one-digit modification of s to see if it's prime
6. If none of them are prime, you've found a prime-proof sqube. Put it in a list, and when you've found the 200th one you're done.

Now the more interesting thing here is to see if you can do something a bit less brute force and ignorance. First off, is the above even practical (assuming a fast primality test)? Easy enough to estimate how fast the squbes grow, but not so much with the prime-proof ones, or the ones containing 200. Can you see any shortcuts?

Have fun!

Answer 2

As has been stated, the question (as originally formulated) isn't a great SO question... however, I haven't really been able to find much other discussion around the 'net on this particular problem. So, if you would be so kind, I would like to resurrect this thread and massage it into something that would pass as a reasonable discussion for this (particularly tricky) Euler problem.

The solution that I've been working on is very similar to the brute force algorithm presented by Simon on 4/22/09. The main differences are that 1.) I'm not ordering my list of Squbes until after they are 'tested', 2.) and i'm enforcing the rule that the primes must be distinct.

the only relatively complex components of this problem is the "Prime Proof" test. The set size of candidate primes grows as the squbes grow. A fully deterministic, naiive prime verifier is way too slow. A probabilistic prime verifier is significantly faster (I can easily generate the required 200 squbes in <30 seconds), but the answer that I produce is incorrect (likely due to false positives in the probabilistic verifier).

Has anyone here had any success with this problem? I'm not looking for a solution- I would, however, appreciate some guidance as to the overall direction that i'm taking.

Thanks!