Generating numbers that are a product of consecutive primes

Question

I have implemented a correct but horribly coded solution to Project Euler Problem 293.

An even positive integer N will be called admissible, if it is a power of 2 or its distinct prime factors are consecutive primes. The first twelve admissible numbers are 2,4,6,8,12,16,18,24,30,32,36,48.

If N is admissible, the smallest integer M> 1 such that N+M is prime, will be called the pseudo-Fortunate number for N.

For example, N=630 is admissible since it is even and its distinct prime factors are the consecutive primes 2,3,5 and 7. The next prime number after 631 is 641; hence, the pseudo-Fortunate number for 630 is M=11. It can also be seen that the pseudo-Fortunate number for 16 is 3.

Find the sum of all distinct pseudo-Fortunate numbers for admissible numbers N less than 10⁹.

I use several nested loops that I wish to make into some nicer functions or such. The following is the first three sections of the code, out of 10 sections required to solve the problem. Each has one more nested loop, and while the time is not an issue I would like to improve this code, but I am not sure how to implement this algorithm in a more concise manner.

What the nth section does is generate all numbers less than 1e9, that contain only the first n prime numbers(and then add numbers relating to the problem to a set).

I have tried for example to have a list of exponents for all primes, and incrementing the outermost nonzero exponent, and then backtracking when the product is larger than 1e9, however I have not been able to do anything successful.

pseudofortunate=set()
pr=generate_primes(24)
num1=1
while num1<1e9/2:
 num1*=pr[0]
 num2=num1
 while num2<1e9/3:
 num2*=pr[1]
 m=num2+3
 while True:
 if is_prime(m):
 pseudofortunate.add(m-num2)
 break
 m+=2
num1=1
while num1<1e9/2:
 num1*=pr[0]
 num2=num1
 while num2<1e9/3:
 num2*=pr[1]
 num3=num2
 while num3<1e9/5:
 num3*=pr[2]
 m=num3+3
 while True:
 if is_prime(m):
 pseudofortunate.add(m-num3)
 break
 m+=2
num1=1
while num1<1e9/2:
 num1*=pr[0]
 num2=num1
 while num2<1e9/3:
 num2*=pr[1]
 num3=num2
 while num3<1e9/5:
 num3*=pr[2]
 num4=num3
 while num4<1e9/7:
 num4*=pr[3]
 m=num4+3
 while True:
 if is_prime(m):
 pseudofortunate.add(m-num4)
 break
 m+=2

• Martin R: If you submitted the correct solution then you should have access to the thread for problem 293 in the forum. There are some nice (and short!) Python solutions presented, including a generator which yields all admissible numbers.

Answer 1

Ok so I figured this one out, by doing the nested loops recursively as a generator. Below is a MUCH nicer code that yields the same answer.

def loop(n,depth):
 """generates numbers containing "depth" primes, up to n"""
 if depth==0: #generates the powers of two
 num1=1 
 while num1<n/2:
 num1*=pr[0]
 yield num1
 else:
 for i in loop(n,depth-1): #generates all numbers containing the first n prime numbers
 num_depth=i #number containing all previous primes
 while num_depth<n/pr[depth]:
 num_depth*=primes[depth] #successively multiplies the nth prime
 yield num_depth
def admissiblenums(n=1e9):
 """generates a set of all admissible numbers not exceeding 1e9"""
 admissibleset=set()
 for i in range(len(pr)):
 nth_admissible_prime=set(loop(n,i))
 admissibleset|=nth_admissible_prime #union of admissibles up to nth prime 
 return admissibleset
def pseudofortunate(n):
 """returns the pseudofortunate number of n
 (the difference between n, and the first prime larger than or equal to n)"""
 prime_candidate=n+3#defined as prime larger than n+1, so starting the search for a prime at n+3, since admissible numbers are always even
 while True:
 if is_prime(m):
 return prime_candidate-n #returns the difference(pseudo-fortunate number) if prime_candidate is prime
 prime_candidate+=2 #check odd numbers
t1=time()
primes=generate_primes(24) #the primes less than 24, since the primorial needs to be less than 1e9
pseudofortunates=set() 
for i in admissiblenums():
 pseudofortunates.add(pseudofortunate(i)) #adds psuedo-fortunate numbers to set
print sum(pseudofortunates) #sum of unique pseudo-fortunate numbers
t2=time()
print t2-t1

• Oscar Smith: can you please update your variable names? Specifically, I have no idea what num1, pr, or m are. This is a really cool problem, but I don't really want to have to spend a lot of time figuring out what all the variables are.
• Jacob: @OscarSmith Ok, so I quickly changed some variable names and added some comments, it might be easier to understand now, it might not though.
• Oscar Smith: in some ways it is better, but you didn't change your variables consistantly, so now your code doesn't work. I'm guessing that pr changed to primes and that m==n. Is that right? Either way, please update your code so that this works.