Project Euler 500 - Problem 500!!!
Official link: https://projecteuler.net/problem=500
Thought Process
I am very happy with this solution it is my first solution that I have not yet seen anyone else do
First thing to do is go straight to the Wikipedia page or WolframAlpha page on Divisor function, I gained 2 very useful pieces of information, first one from Wiki, 2nd one from Wolfram, see below
We have now found an upper limit for n, and we know the largest prime factor in n is 7376507, now we want a find a way to build the number n such that σ(n) = 2^500500, lets try with smaller numbers
σ(n) = 2^1 = 2
n = 2^1
σ(n) = 2^2 = 4
n = 2^1 * 3^1
Because if we had n = 2^2 then σ(n) = 3
σ(n) = 2^3 = 8
n = 2^3 * 3^1
Here is where we start to understand what we are doing, notice that we are simply building from the previous pattern, from step 2 we have n = 2^1 * 3^1, so we have 3 options, either we multiply by
5^1
2^2
3^2, (note we cannot do 2^1 because then σ(n) would not be a power of 2)
obviously 2^2 < 5^1 < 3^2, so we pick 2^2, lets continue a little bit
σ(n) = 2^4 = 16
n = 2^3 * 3^1 * 5^1
from step 3 we have 3 options:
2^4 (We always need to keep the power of exponents 1 less than a power of 2: (2,4,8,16,32, etc)
3^2
5^1
5^1 < 3^2 < 2^4, so we pick 5^1, lets do one last one
σ(n) = 2^5 = 32
n = 2^3 * 3^1 * 5^1 * 7^1
from step 4 we have 4 options:
2^4
3^2
5^2
7^1
7^1 < 3^2 < 2^4 < 5^2, so we pick 7^1, I think you got it by now
So we simply need to make an algorithm which picks the right number and it turns out there is a very simple way to do this!
Remember our biggest factor possible is 7376507? We only need primes such that when squared or to the power 4, 8, 16, 32, etc are < 7376507, this means we have can essentially build all the possible options of n straight away!
We need all the possible primes which are:
primes^1 < 7376507, there are 500500
primes^2 < 7376507, there are 396
primes^4 < 7376507 there are 16
primes^8 < 7376507, there are 4
primes^16 < 7376507, there are 2
primes^32 < 7376507, there is 1
Simply add all of these numbers to a list, sort it and reverse it and multiply the first 500500 of them! This works because they are already in order same as our options list when we build them up.
As usual I used my Prime Generator
Interactive Code
Enter an integer (yourinput)
Code will output the minimum n modulo (500500507) such that σ(n) = 2^yourinput