Euleryx Problem 23 – Non-Abundant Sums
My workflow:
Spoiler
Workflow:
Answer: 4179871
Last Week's Favourite Solution:
Last weeks favourite solution is going to @Qiu . Whilst I do commend the effort for creating manual lookups for the alphabet, @Qiu , used a generate rows, and then the formula tool with the CharFromInt() function to dynamically create a standalone lookup table. Having the table isolated before joining to the data made the solution very intuitive! Please find their solutions on page one of last week's post or click here.
Mathematical Theory:
Abundant numbers are found based on the sum of their factors, meaning a good place to start for this problem, is to identify all the factors of a given number. As we discussed in Project 21, there are multiple ways to do this.
Similarly to before, in order to decide upon the best approach we must consider the size of data we are dealing with. In the question itself, we are made awear that beyond the number 28,123, all numbers can be created by summing two abundant numbers. We also know that summing two numbers only leads to a bigger number (in the context of positive numbers), so we wont need to consider any abundant numbers greater than 28,123, for this problem. With this in mind, I decided the required data was small enough to go with Approach 2 (from project 21), which is the more bruit force method of identifying factors, as it tests all numbers up to (and including), the square root of a number.
If you want to see the alternative method, where prime factors are used to identify all factors of a given number, then I recommend looking at @DaisukeTsuchiya's solution from Project 21.
Method:
1) Step one was to create a list of all whole numbers up to 28123.
2) Now, for each of those numbers, generate rows up to and including the square root of the number.
3) Find the factor pair for all of these potential factors, then confirm it is a valid factor pair, by filtering to pairs where both numbers are integer values.
4) Next pivot the data so we have a single column, containing all the factors.
5) Remove any factors equal to the starting number, and them sum all the remaining unique factors (per starting number).
6) Filter to the abundant numbers (where the sum value is greater than the Number itself).
7) Create all possible abundant number sums, by appending the list of anundant numbers to itself, (filtering out duplicate sums), calculating the sums, then uniquing the final list of values with a sample tool.
8) Joining the list of abundant number sums, back to the initial input (all numbers <= 28,123, we are then left with all the non-abundant sums, on the right anchor of the join.
9) Sum all these values to arrive at the final value.
10) Submit your answer to the Project Euler Website!
Summary:
A different application in terms of how to use the factors, but non the less, we were again able to bring forward some valuable tricks from previous projects. Don’t get too comfortable with factors though as next week we will be tackling permutations.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
