Hint for Project Euler Problem 500

Problem 500!!!

Problem 500

The number of divisors of 120 is 16.
In fact 120 is the smallest number having 16 divisors.
Find the smallest number with 2⁵⁰⁰⁵⁰⁰ divisors.
Give your answer modulo 500500507.

120 = 2^3 * 5^1 *7^1
Number of Divisors =  4 * 2 * 2

While trying to obtain the smallest number with 2^4 divisors, here are the steps:

1, Understand that what we're really doing is picking 4 smallest numbers from the below table, which is 2,3,4,5;

P P^2 P^4
2  4   16
3  9   81
5  25 ...
7  49 ...
11 ...
13 ...

2, Generalize that; We will pick 500500 smallest numbers from the exact same table.
Thanks to Wolfram Alpha, we can get the whole table in no time.

prime(500500) = 7376507
prime(500500)^(1/2) ~= 2713 = prime(396)
prime(500500)^(1/4) ~= 47 = prime(15)
prime(500500)^(1/8) ~= 7 = prime(3)
prime(500500)^(1/16) ~= 2 = prime(1)

That is approximately 396+15+3+1=415 less primes needed.
Since, we also have below results.
prime(1)^16 < prime(500085) = prime(500500-415) = 7369969
prime(3)^8 < prime(500085)
prime(15)^4 < prime(500085)
prime(396)^2 < prime(500085)

The numbers we're gonna pick is listed as below:
prime(1) - prime(500415) altogether 500415 numbers
prime(1)^2 - prime(396)^2 altogether 396 numbers
prime(1)^4 - prime(15)^4 altogether 15 numbers
prime(1)^8 - prime(3)^8 altogether 3 numbers
prime(1)^16 altogether 1 number

Multiply all those numbers and mod 500500507 reveals our answer.

---------------------

With the above information, below python code reach the correct answer:

import math

maxn=500500
#the 500500th prime number, use wolfram alpha
maxp=7376507
div=500500507

#the max prime with log(maxp)/log(prime) = 16,8,4,2
#meaning adding prime^8 cost less than adding a maxp 
#tested in excel the 4998xx th prime returns same result as the 500500th

expmap = {2:31,7:15,47:7,2713:3}
def lookupexp(prime):
if prime <=2:
return 31
elif prime <= 7:
return 15
elif prime<=47:
return 7
elif prime<=2713:
return 3
else:
return 1

def nextprime(prime,primemap):
prime+=1
while(primemap[prime]==False):
prime+=1
return prime

primemap=[ True ]*(maxp+1)
for i in range(2,maxp+1):
#prime
if primemap[i] == True:
for j in range(2,((maxp//i) +1)):
primemap[i*j]=False
#print(i)

count = 0
number = 1
prime = 2
while(count<500500):
exp = lookupexp(prime)
number *= (prime**exp)
number = number%div
prime = nextprime(prime,primemap)
count+=(math.log((exp+1),2))

print (number,count)