Home > Programming > Project euler 29: Distinct powers

Project euler 29: Distinct powers


Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

def distpowers(n):
    a={2} # initialize the set
    d={}  # map for total number of elements for each power
    s=[0 for x in range(n + 1)]
    for i in range(1, 8):
        for j in range(2, n + 1):
            a.add(i * j)
        d[i]=len(a)
    tot = 0
    for i in range (2, n + 1):
        if s[i] == 0:
            prod = i
            power = 0
            while prod <= n:
                s[prod] = 1
                prod *= i
                power += 1
            tot += d[power]    
    print (tot)          

if __name__ == '__main__':
    distpowers(100)

Time complexity O(8 * n) ~ O(n)
Space complexity O(n)
Answer: 9183

Advertisements
Categories: Programming Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: