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

1. σ(n) = 2^1 = 2

   • n = 2^1

2. σ(n) = 2^2 = 4

   • n = 2^1 * 3^1

   • Because if we had n = 2^2 then σ(n) = 3

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

     1. 5^1

     2. 2^2

     3. 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

4. σ(n) = 2^4 = 16

   • n = 2^3 * 3^1 * 5^1

   • from step 3 we have 3 options:

     1. 2^4 (We always need to keep the power of exponents 1 less than a power of 2: (2,4,8,16,32, etc)

     2. 3^2

     3. 5^1

   • 5^1 < 3^2 < 2^4, so we pick 5^1, lets do one last one

5. σ(n) = 2^5 = 32

   • n = 2^3 * 3^1 * 5^1 * 7^1

   • from step 4 we have 4 options:

     1. 2^4

     2. 3^2

     3. 5^2

     4. 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:

1. primes^1 < 7376507, there are 500500

2. primes^2 < 7376507, there are 396

3. primes^4 < 7376507 there are 16

4. primes^8 < 7376507, there are 4

5. primes^16 < 7376507, there are 2

6. 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