Euleryx Problem 29 – Distinct Powers
My workflow & macros:
Spoiler
Workflow:
List Prime Factors Macro:
Prime Factor Power Macro:
Answer: 9183
Last Week's Favourite Solution:
Seeing the different breakdowns for last week's project was very interesting, and I’m obviously always a fan of the mathematical formulas! That being said, @AncientPandaman, provided two solutions, one using the formula, and another creating the full grid itself (which is more challenging that is sounds). This double solution has been selected as last weeks favourite solutions. Please find both solutions on page one of last week's post or click here.
Mathematical Theory:
This week is another problem that, on the face of it, will involve some very large values, too large to be handled by the standard Int64 data type. These values could be calculated using strings or through the use of the BigInt functions recently created by @AncientPandaman. If you haven't already seen them, I highly recommend checking them out here.
Instead of tackling the problem as a BigInt challenge, the approach below centres on the idea of prime factors (a concept first visited in project 3). As a quick reminder, a value's prime factors are the set of prime numbers, which when multiplied together will equal the starting value, i.e:
- 30 = 2 x 3 x 5
- 28 = 2 x 2 x 7
As each number can be expressed in the form of its prime factors, if we can calculate the prime factors for all the values in the question (a^b), then we can unique this list of values to arrive at the answer. I.e
- 2 squared = 4 and has prime factors (2,2)
- 4 =4 and has prime factors (2,2)
We can see that as 2 squared has the same prime factors as 4, the two values are clearly the same. Now the main question, is how to find the list of prime factors, for the different powers.
As hinted at above, Problem 3 shows how to find the factors of a given value, so the same technique can be used on the starting values (2-100) in this challenge. Once we have this list, there is a trick we can exploit to calculate the list of values for the power. Let's use the number 12 as an example.
- 12 has prime factors (2,2,3). This means that 12 can be written as 2 x 2 x 3 = 12
- 12 squared can be written as 12 x 12; however, if we substitute the equation from above in, we can also write it as (2 x 2 x 3) x (2 x 2 x 3) = 12 x 12
- After making the substitution, it’s easy to see that the prime factors of 12 squared are (2,2,2,2,3,3). Each one of 12’s prime factors simply appears twice!
This idea applies to all the powers, i.e for 12 cubed, we can simply list the prime factors of 12, 3 times. Using this simple principle, there is actually no calculation required to identify the prime factors for the different powers. As mentioned above, we can then simply count the unique prime factor lists to solve the problem.
Method:
1) The first step is to simply create the input list of values ranging from 2-100
2) The next objective was to List the prime factors for all of the input values (2-100). To do this the “List Prime Factors” macro from Project 3 was reused.
3) Now the prime factors had been found, they were split to rows so that there was a single factor per row.
4) The data is now ready for the iterative macro. This macro aims to list the prime factors for all the relevant powers.
a) Based on the reasoning in the above section, we know that the to get the prime factors of a given number, multiplied by itself, we simply repeat the current list of prime factors. This can be achieved by simply unioning the list of prime factors onto itself.
b) As we need to see the prime factors for each and every power, I then sorted and concatenated the values for outputting.
c) In order to find the third power, we need the list calculated in part “a” to be looped back to the start, so we can union the original list of prime factors on again (3 times total).
d) This process then repeats, each iteration finding the prime factors for the next power.
5) The output from the macro contains lists of all the values a^b, expressed in their prime factor form.
6) By counting the number of distinct lists, the answer can be found.
7) Submit your answer to the Project Euler Website!
Summary:
The solution to this problem was found without once calculating any of the raw values, for a^b. By expressing numbers in their prime factor forms, the need for Big Int calculations was completely eradicated, leading to a quick, simple solution.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
