My workflow (Spoiler - Please skip the next few lines if you don't want to see the answer):
Workflow:
Answer: 872187
Last Week’s Favourite Solution:
While the yxdbs still still to open an xml in teh browser, fortunatly the yxzp files can be downloaded, meaning I was able to opan and learn from many of last weeks solutions. Having said that, last weeks favourite solution was awarded largley do to a techniequ explained in the post. @AncientPandaman detailed, how using the sqrt() funciton, we could actually identify many new primes, every iteration, not just at the end. For more details on this, please find their solution on page one of last week’s post or click here.
Definitions:
- Palindrome: A value which reads the same forwards as it does backwards ie. 121 is a palindrome because reversing its digits still gives 121.
Mathematical Theory:
This problem asks us to find all numbers less than one million which are palindromic in both base 10 (what we consider normal numbers) and base 2 (binary), then sum them.
The key insight this week is how we generate our list of palindromic numbers. In the past I have seen several people computing the starting values more directly, instead of generating a larger list and then filtering it down, so this week, I have attempted this myself. Instead of generating every number from 1 to 999,999 and checking whether each one is a palindrome in base 10, we can be much smarter. We can construct palindromes directly.
The trick is to simply take any number, reverse its digits, and append the reversed digits onto the end of the original. The result is guaranteed to be a palindrome. For example, if we start with 12, reversing it gives us 21, and appending gives us 1221. Reading 1221 forwards or backwards gives the same value, so it is a palindrome by construction.
However, this approach only produces palindromes with an even number of digits. To also capture odd-length palindromes, we use a second method: reverse the number, remove the first digit of the reversed string, and then append what remains. Using the same example of 12, reversing gives 21, dropping the first character leaves just 1, and appending gives us 121. This is also a palindrome, but with an odd number of digits.
By applying both of these methods to every number from 1 to 999, we can generate all base 10 palindromes below one million. (We know 999 is sufficient as when applying this method, it will generate 999,999, the largest possible 6 digit value).
Method:
- The first step is to generate our seed values using a Generate Rows tool, creating all whole numbers from 1 to 999. Although it may seem strange, I have stored the numbers as string values to help when constructing the palindromes.
- Next, using a Formula tool, we create two new columns containing palindromes as discussed in the previous section. The first uses ReverseString to reverse the digits and appends the result onto the original, producing an even length palindrome. The second does the same but removes the first character of the reversed string before appending, producing an odd length palindrome.
- The Transpose tool is then used to pivo the two columns of palindromes down into a single list.
- The next step is to convert each palindrome into its binary representation. I discovered that alteryx has an inbuilt function for this, found within the formula tool.
- Now we filter to only those records where the binary representation is also a palindrome. Using a Filter tool, we check whether the Binary column equals the ReverseString of itself. Any record passing this test is a confirmed double-base palindrome.
- Finally, we use a Summarise tool to sum all the remaining values, giving us our answer.
- Submit your answer to the Project Euler Website!
Summary:
This week’s challenge was a neat example of how generating the input candidates smartly can save a lot of computation. Rather than testing every number below one million for the palindrome property, we constructed all possible base 10 palindromes directly by reversing and appending digit strings. This reduced the problem to a much smaller set of values.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
