CODEWITHSUNDEEP
pythonpython-2.7sumnumbersperfect-square
Dizzle
Dizzle

Reputation: 63

List of numbers whose squares are the sum of two squares

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!

Upvotes: 6

Views: 4768

Answers (4)

yurisich
yurisich

Reputation: 7119

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.

Upvotes: 0

inspectorG4dget
inspectorG4dget

Reputation: 114035

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

Upvotes: 1

jcr
jcr

Reputation: 1015

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

Upvotes: 2

pydsigner
pydsigner

Reputation: 2885

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.

Upvotes: 7

Related Questions