notebook.community

Edit and run

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 2² + 2³ + 2⁴
33 = 3² + 2³ + 2⁴
49 = 5² + 2³ + 2⁴
47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?



In [1]:

    
from euler import gen_prime, gen_lte
from math import sqrt



In [2]:

    
def foo(n):
    triples = set([])
    alimit = int(sqrt(sqrt(n)))
    for a in gen_lte(gen_prime(), alimit):
        aa = a * a
        aaaa = aa * aa
        if aaaa >= n:
            break
        blimit = int((n - aaaa) ** (1./3))
        if (blimit + 1) ** 3 <= n - aaaa:
            blimit += 1
        for b in gen_lte(gen_prime(), blimit):
            bbb = b * b * b
            if aaaa + bbb >= n:
                assert False, 'aaaa + bbb >= n'
            climit = int(sqrt(n - aaaa - bbb))
            for c in gen_lte(gen_prime(), climit):
                triple = aaaa + bbb + c*c
                if triple >= n:
                    assert False, 'aaaa + bbb + cc >= n'
                triples.add(triple)
    return len(triples)



In [3]:

    
n = 50000000
%timeit foo(n)
foo(n)









    



1 loops, best of 3: 1.43 s per loop






    Out[3]:





1097343



In [4]:

    
def foo(n):
    triples = set([])
    alimit = int(sqrt(sqrt(n)))
    for a in gen_lte(gen_prime(), alimit+1):
        aa = a * a
        aaaa = aa * aa
        if aaaa >= n:
            break
        blimit = int((n - aaaa) ** (1./3))
        if (blimit + 1) ** 3 <= n - aaaa:
            blimit += 1
        for b in gen_lte(gen_prime(), blimit+1):
            bbb = b * b * b
            if aaaa + bbb >= n:
                break
                assert False, 'aaaa + bbb >= n'
            climit = int(sqrt(n - aaaa - bbb))
            for c in gen_lte(gen_prime(), climit+1):
                triple = aaaa + bbb + c*c
                if triple >= n:
                    break
                    assert False, 'aaaa + bbb + cc >= n'
                triples.add(triple)
    return len(triples)



In [5]:

    
n = 50000000
%timeit foo(n)
foo(n)









    



1 loops, best of 3: 1.44 s per loop






    Out[5]:





1097343



In [6]:

    
def foo(n):
    triples = set([])
    for a in gen_prime():
        aa = a * a
        aaaa = aa * aa
        if aaaa >= n:
            break
        for b in gen_prime():
            bbb = b * b * b
            if aaaa + bbb >= n:
                break
            for c in gen_prime():
                triple = aaaa + bbb + c*c
                if triple >= n:
                    break
                    assert False, 'aaaa + bbb + cc >= n'
                triples.add(triple)
    return len(triples)



In [7]:

    
n = 50000000
%timeit foo(n)
foo(n)









    



1 loops, best of 3: 1.24 s per loop






    Out[7]:





1097343