General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 16 – Power Digit Sum
My workflow and macro:
Workflow:
Macro:
Answer: 1366
Last Week's Favourite Solution:
Last week saw some very different approaches. Whilst I would like to give a shout out to @patrick_digan for the commitment to the macro-less brute force method, @DaisukeTsuchiya has won the favourite solution award. In this solution, you will see several different macros built to calculate the multiplication or division of numbers using string values instead of numeric, meaning it should work for numbers of any size. (You might even find some of the techniques @DaisukeTsuchiya used in my solution to this week's problem). Please find their solutions on page one of last week's post or click here.
Definitions:
- Power: The power of a number is the result of multiplying said number by itself a set number of times. I.e 2 to the power of 3, is 2 x 2 x 2 = 8
Mathematical Theory:
This week's challenge can be quickly optimised by using one of the exponent laws, commonly referred to as the Power of a Power rule.
The “Power of a Power” rule states that we can rewrite the power of a number as follows:
What this is telling us is that if we have a number “a” multiplied by itself “n” times, which is then multiplied by itself “m” times, it’s the same as just doing to the original number “a” multiplied by itself (n x m) times. So if we had two to the power of 2 all to the power of 3, we could rewrite this as follows:
Intuitively, this works well too because if we write out both sides of the equation in full, we get:
However, for this particular problem, we don’t have an “n” and an “m” value; we just have 2 to the power of 1000.
The trick here is to look at things the other way around. As we know:
We therefore also know that:
The beauty of looking at things this way round means that not only can we now start with 2 to the power of 1000, but we can also choose our own values for n and m.
Two to the power of 1000 is a very large number; therefore cannot just be calculated using the Pow() function, as it exceeds the numerical limit in Alteryx. Instead, we are going to have to use string values to help us calculate things one digit at a time.
Now - slight spoiler alert - I used an iterative macro to solve this week's problem, so ideally I want to minimise the number of iterations. I'm also conscious that I cannot exceed the maximum integer value (int64), so I decided to set n = 40 and m = 25 (as 25 x 40 = 1000).
This means that instead of doing 1000 iterations where I multiply by two each time, I can do just 25 iterations, and multiply by 1099511627776 (2 to the power of 40) each time.
Method:
1) Create an input (although this will actually be overwritten shortly).
2) Implement the optimisation we mentioned above and update the starting value and Power accordingly:
3) Update the column called “Number” to be a string, and feed the data into the Power Macro.
a) Begin by reversing the string and parsing it out so we have one digit per line:
b) Multiply each digit by the starting value:
c) Now implement a multirow. We effectively need to add the row above, onto the current row. However, don’t forget that each row is out by a factor of 10 when compared with the row above, hence we need to ignore the units (I did this by dividing by 10 and using the floor function).
d) It's important to know which row is the final one, hence I used the summarise tool and append to help with this.
e) For all rows except the last one, we only care about the end digit, as all other digits were added to the line below. Hence, we use a formula tool to remove the unwanted values.
We have also updated the Power column, as each iteration is a single multiplication, hence reducing the remaining required multiplications by 1.
f) Finally, I sorted the Record ID in descending order and concatenated the string. If the remaining power is 1, we have finished; therefore can exit the loop, otherwise we require another iteration.
4) Back outside the macro, I parse the digits so we have one per record:
5) Finally, the digits are summed using the summarise tool to get to the final answer.
6) Submit your answer to the Project Euler Website!
Summary:
The Power of a Power rule was not able to help us arrive at an immediate solution; however, it did reduce the required iterations from 1000, down to just 25. With a 97.5% reduction of iterations, it proved to be a valuable tool in a very large number problem.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
built BigInt product macro to multiply by digit and group.
So generate 1000 rows of 2.
I process the multiply by pairs. hence 1000 rows will be 10 iteration where (2^10 = 1024).
Thanks so much for the great feedback on my WF! I'm thrilled to hear you liked it.
I really struggled to build that multiplication and division macro to handle huge numbers, but I pushed through to get it done for the Euleryx problems after #50.
For this week's problem, I just had to tweak the macro from last week a bit to get it working.
=============<Comment for #15 >===========================
Many of the Project Euler problems, especially from around #50, involve calculations that exceed the limits of INT64.
I actually built this workflow in the weekend to tackle such issues to solve the combinatorics problem in #53, where some intermediate values grew to over 150 digits long. So, I figured I might as well use it here too.
========================================================
My solution!
