Weekly Challenges
Solve the challenge, share your solution and summit the ranks of our Community!Also available in | Français | Português | Español | 日本語
IDEAS WANTED
Want to get involved? We're always looking for ideas and content for Weekly Challenges.
SUBMIT YOUR IDEA
Brute force but a much more elegant solution would be with iterative macros and to only test each numbers divisors as minimally as possible. EG: for 12 you only need to test until 6 to know all divisors. No point in testing 7 through 11 for 12 since 2 is a factor and therefore 6 is the largest factor.
A CHALLENGE for the Math ACEs out there:
---->>> Are there any perfect odd numbers out there?
Anyway, here's my solutions which is the BRUTE FORCE also leveraged by others.
Instead of starting with the product, I generated all possible factors. I was able to test numbers up to 10,000,000.
My try (with math applied)! Thanks, @gawa for the challenge!
We can greatly reduce number of generated rows using divisors properties. Basically we only need to check check numbers up to sqrt(n). I believe, @Chris-Nienart mentioned this in his reply.
‼️math in spoiler!
The divisors of a positive integer, n, always exist in pairs. For instance, if d is a divisor of n, then there exists another divisor k such that n/d = k. This implies that n = d*k.
For example, the number 10 has four divisors: 1, 2, 5, and 10. These divisors can be grouped into two pairs: (1,10) and (2,5).
A key observation is that for each pair of divisors, one divisor is smaller than the other. This holds true for all positive integers. The only exception is when n is a perfect square. In this case, there exists a divisor d such that d = k, and n = d^2.
This observation leads to an efficient method for computing the divisors of n. Instead of checking all numbers up to n, we only need to check numbers up to sqrt(n). For each divisor d found in this range, we can compute its corresponding pair k = n/d.
This method significantly reduces the computational resources required. For instance, to find the divisors of 100, we only need to check numbers from 1 to 10. Similarly, to find the divisors of 10,000, we only need to check numbers from 1 to 100.
In comparison, if we were to check all numbers up to n/2, the number of computations would be significantly larger. For all numbers from 1 to 10,000, this method would require checking 661,750 cases, compared to 25,000,000 cases using the n/2 approach. Thus, the sqrt(n) method is far more efficient.
Workflow:
This is a perfect Advent of code first half problem. It can be brute forced because N is small.
The second half would inevitably be "oops, there was a decimal point moved in the input. Actually find the perfect numbers in the first 1 trillion integers."
I'm not sure there is a way to not brute force this a little, but we can math our way down to a much smaller problem.
First, perfect numbers grow faster than log10. That means that we can reduce the problem of "Find all perfect numbers < N" to "Find the first X = Log10(N)+1 perfect numbers."
Second, the relationship between Perfect Numbers, Mersenne Primes and Primes means we can solve the equivalent simpler problem "Find the first X Mersenne Primes" and further to "Find the first X Primes."
Third, the Nth prime is approximately N* ln(N). If we take close to to mean within 50% we can solve the equivalent problem Find all primes < Y = 1.5* X * ln(X)
Brute forcing Y-1 to check for Primes is much faster than brute forcing N^2 to check for perfect numbers. For N = 10000, Y =13 and for N = 1T, Y = 51
Once you've solved the small brute force problem, all that's left is to convert from prime to perfect number and check for output < N because the close approximation will generally calculate more perfect numbers than the set.
Screen shot is of the 1 Trillion run, three tenths of a second. Didn't actually read that many rows because only the maximum number matters.
