If you want to challenge yourself at writing algorithms to solve mathematical problems, then Project Euler is a nice site for you. The problems have a wide range of difficulty. I found the problem 49 surprisingly rich in terms of strategies that can be employed to solve it.
The problem statement is :
The problem statement is :
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
Unusual indeed. The numbers have to be prime and permutations of each other, and make up an arithmetic sequence.
Of course, there are many ways to solve the problem. One obvious candidate is use some sort of brute force approach. But what's the fun in doing that ? So I decided to try an efficient approach. I am sure there are many alternatives. The one I tried is as follows.
Note that there are 3 unusual properties. I used them to break the problem in 3 steps and wrote a small, efficient program for each step.
1. Generate Prime Numbers.
Obviously, if we inspect only the 4 digit prime numbers, it's going to reduce the problem space and speed up the solution. As long as generating prime numbers is not expensive. The standard textbook solution for this is to use "Sieve Of Eratosthenes", that offers a near linear algorithm to generate the prime numbers. You can find more explanation here. Using this program, we generate a list of 4-digit primes in ascending order.
2. Group the numbers that are permutations of each other
By treating the numbers as string of digits, we can compare any two numbers to check if they are permutations of each other. The brute force algorithm will have O(N^2) complexity. I wrote an algorithm with linear complexity that works especially well when the cardinality of alphabet set is not very high. You can find the algorithm here. With this step done, we have grouped together all the 4 digit primes that are permutations of each other. Since the original list of all the primes was already in sorted order, each group is also sorted in ascending order.
3. Find the arithmetic sequence
This is bit harder than the first 2 steps. Now, if you just want to examine a given sequence of numbers to decide if it is an arithmetic sequence, then that's very easy to do. But that's not what I wanted. I wanted to write an algorithm to find all the arithmetic sequences within a given sequence. Solving this more generic problem is NOT necessary to solve the Project Euler problem. Becase we are told that the sequence contains only 3 numbers. Moreover, we have already grouped the numbers based on permutations. So either the group is a desired sequence or not. That's simple to test. But if you were not given the problem specific information, then you have to find an arithmetic sequence within a larger sequence. For example, I found a set of 11 primes that are permutations of each other. The entire set is not an arithmetic sequence. But a subset could have been. You can find the details of my solution to the generic problem here.
By connecting these steps, you can find the solution of the problem. On my MacBook Pro, it took less than one minute for my Java program to generate all the prime numbers, group them based on permutations and find the sequence.
Some interesting facts. There are 174 permutation groups within the 4 digit primes that have more than 3 members in it. For example
[3253, 5233, 5323]
[6899, 8699, 8969, 9689]
[2039, 2309, 2903, 3209, 9203].
The longest two have 11 primes in each !
[1237, 1327, 1723, 2137, 2371, 2713, 2731, 3217, 3271, 7213, 7321]
[1279, 1297, 2179, 2719, 2791, 2917, 2971, 7129, 7219, 9127, 9721].
But none of these contain any sequences.
The most curious fact is not mentioned in the problem. The other prime permutaiton sequence, has exactly the same difference in it's terms, 3330 !! That means : The only 2 arithmetic sequences of 4 digit primes such that the numbers are permutations of each other, have exactly the same difference. The one was already given in the problem. The other one we have to find. Both sequences have the same difference, 3330. Really interesting.
The Project Euler guidelines suggest not to disclose the solution. It's OK to explain the strategy. Hence I have not given the solution here.
Of course, there are many ways to solve the problem. One obvious candidate is use some sort of brute force approach. But what's the fun in doing that ? So I decided to try an efficient approach. I am sure there are many alternatives. The one I tried is as follows.
Note that there are 3 unusual properties. I used them to break the problem in 3 steps and wrote a small, efficient program for each step.
1. Generate Prime Numbers.
Obviously, if we inspect only the 4 digit prime numbers, it's going to reduce the problem space and speed up the solution. As long as generating prime numbers is not expensive. The standard textbook solution for this is to use "Sieve Of Eratosthenes", that offers a near linear algorithm to generate the prime numbers. You can find more explanation here. Using this program, we generate a list of 4-digit primes in ascending order.
2. Group the numbers that are permutations of each other
By treating the numbers as string of digits, we can compare any two numbers to check if they are permutations of each other. The brute force algorithm will have O(N^2) complexity. I wrote an algorithm with linear complexity that works especially well when the cardinality of alphabet set is not very high. You can find the algorithm here. With this step done, we have grouped together all the 4 digit primes that are permutations of each other. Since the original list of all the primes was already in sorted order, each group is also sorted in ascending order.
3. Find the arithmetic sequence
This is bit harder than the first 2 steps. Now, if you just want to examine a given sequence of numbers to decide if it is an arithmetic sequence, then that's very easy to do. But that's not what I wanted. I wanted to write an algorithm to find all the arithmetic sequences within a given sequence. Solving this more generic problem is NOT necessary to solve the Project Euler problem. Becase we are told that the sequence contains only 3 numbers. Moreover, we have already grouped the numbers based on permutations. So either the group is a desired sequence or not. That's simple to test. But if you were not given the problem specific information, then you have to find an arithmetic sequence within a larger sequence. For example, I found a set of 11 primes that are permutations of each other. The entire set is not an arithmetic sequence. But a subset could have been. You can find the details of my solution to the generic problem here.
By connecting these steps, you can find the solution of the problem. On my MacBook Pro, it took less than one minute for my Java program to generate all the prime numbers, group them based on permutations and find the sequence.
Some interesting facts. There are 174 permutation groups within the 4 digit primes that have more than 3 members in it. For example
[3253, 5233, 5323]
[6899, 8699, 8969, 9689]
[2039, 2309, 2903, 3209, 9203].
The longest two have 11 primes in each !
[1237, 1327, 1723, 2137, 2371, 2713, 2731, 3217, 3271, 7213, 7321]
[1279, 1297, 2179, 2719, 2791, 2917, 2971, 7129, 7219, 9127, 9721].
But none of these contain any sequences.
The most curious fact is not mentioned in the problem. The other prime permutaiton sequence, has exactly the same difference in it's terms, 3330 !! That means : The only 2 arithmetic sequences of 4 digit primes such that the numbers are permutations of each other, have exactly the same difference. The one was already given in the problem. The other one we have to find. Both sequences have the same difference, 3330. Really interesting.
The Project Euler guidelines suggest not to disclose the solution. It's OK to explain the strategy. Hence I have not given the solution here.
No comments:
Post a Comment