2
\$\begingroup\$

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):
                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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Martin R Aug 18 '16 at 19:39
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Oscar Smith Aug 19 '16 at 12:17
  • \$\begingroup\$ @OscarSmith Ok, so I quickly changed some variable names and added some comments, it might be easier to understand now, it might not though. \$\endgroup\$ – Jacob Aug 19 '16 at 17:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Oscar Smith Aug 22 '16 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.