Question

I've just started learning Python and have started doing some problems just to help buid my skills however I am pretty stuck on this question.

Make a list containing all positive integers up to 1000 whose squares can be expressed as a sum of two squares, (i,e., integers p for which p^2=m^2+n^2, where m and n are integers greater than 0.)

Hints: There are several approaches. You might find it helpful to have a list of all the square numbers. The in operator might be useful.

Here's the code that I've come up with so far:

    numbers=xrange(1001)
    numbers_squared=[x**2 for x in numbers]
    a=[]

    for x in numbers_squared:
        for b in numbers_squared:
            if (x+b)**.5 <= 1001:
                a.append(x+b)
    print a

The problem I get with this is that Python takes years to do these calculations (I've waited about ten minutes and it's still printing numbers). Any hints on how to solve this would be very appreciated.

p.s. The main point is to use lists. Also hints would be more appreciated than the solution itself.

Thank You!

Was it helpful?

Solution

how about a list comprehension? calculate for c in range(1,1011) for b in range (1, c) for a in range (1, b)

as follows:

x = [(a,b,c) for c in range(1,1001) for b in range(1, c) for a in range(1,b) if a**2+b**2==c**2]
print x 

I have timed this and it takes 46 seconds to complete on my computer

OTHER TIPS

First of all, you aren't solving the problem. You need to do a check to make sure (x+b)**.5 is actually an integer. Secondly, if you are printing numbers, you have already calculated out all the numbers. Doing the above will decrease the time required for this step.

This might work:

def isSumOfSquares(n):
    """return True if n can be expressed as the sum of two squares; False otherwise"""

    for a in xrange(1,n):
        b = n-(a**2)
        if b<=0:
            return False
        elif not math.sqrt(b)%1:
            return True
    return False

answer = [i for i in xrange(1,1001) if isSumOfSquares(i**2)]

Let me know if this works for you

I just answered this elsewhere!

import math

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""
    if hypotenuse < 4:
        return None

    c = hypotenuse ** 2

    for a in xrange(3, hypotenuse):
        b = math.sqrt(c - (a ** 2)) 
        if b == int(b):
            return a, int(b), hypotenuse

    return None

>>> results = [x for x in range(1001) if is_triple(x)]
>>> len(results)
567

Runs almost instantly.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top