Monday, August 9, 2010

Looking at the 4th ten Project Euler problems.

Problem 31 is a straightforward recursive count. Once you get to the 1p, the number of combinations is 1.

For problem 32, 99×99 = 9801 and 111×111 = 12321, so all the solutions have to be a two-digit number × a three-digit number resulting in a four-digit number. I did a brute-force search through all the combinations of 5 digits of the multiplicands.

Problem 33 just involved searching with 1 through 9 to see if any pair of digits had the property, so that was a small search. Also, there were only 36 pairs of digits to check.

Problem 34 is just like problem 30 with a larger bound.

For problem 35, I partitioned the primes by number of digits, then filtered out the numbers that were not the minimum of the digit rotations, which conveniently eliminated all numbers with zeros. I then filtered out the numbers for which not all of the rotated numbers were in its partition, which eliminated 11. 111, 1111, 11111, 111111 are all not prime. Then multiple the size of each partition by its number of digits, sum, add 1 for 11 gives the answer.

Problem 36 was a brute-force filter. Since leading zeros weren't allowed, even numbers could be eliminated, cutting the problem in half.

For problem 37, I built lists of n-digit primes that could be truncated from the left to n-1-digit primes, and lists of n-digit primes that could be truncated from the right to n-1-digit primes. The intersection of the left and right lists gives the 11 numbers.

From the example in problem 38, the first digit had to be a 9, so it was just a matter of searching 91..98, 912..987, 9123..9876, and 91234..98765.

For problem 39, p/3 < c < p-3, and c/2 < b < c-1. After that, I just did a brute-force search, which was kind of slow.

Problem 40 is just multiplying 7 single-digit numbers, and at least 2 of them are 1. It's straightforward to figure out those numbers, and, as it turns out, the product of those numbers is simple to mentally compute.

No comments:

Post a Comment