# Generating numbers that are a product of consecutive primes

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

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):
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):
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):
break
m+=2

• 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. – Martin R Aug 18 '16 at 19:39

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

"""generates a set of all admissible numbers not exceeding 1e9"""
for i in range(len(pr)):

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()