List of numbers whose squares are the sum of two squares

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!

Delmerdelmor

Well, for one, you can restrict the second for loop to numbers below x. 8**2=64 for example cannot be expressed as the sum of any numbers greater than 64. – Volcanic

Are you given how many such numbers there are? – Procurance

I was thinking that but I wasn't sure how to write that exactly in Python. Thanks for the hint :D – Delmerdelmor

No answers at all, just the "tasks" themselves information about lists etc. – Delmerdelmor

Answer 1

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

Geerts

Answer 2

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.

Amid

Ahh okay. Thank you very much :D, I think I've cracked it!! – Delmerdelmor

This is basically a problem of finding Pythagrean triples. Just keep the c in a**2 + b**2 = c**2. – Standup

Answer 3

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

Procurance

I tried it and it didn't work, tried to make some changes to fix and still no. Thanks anyway :) – Delmerdelmor

I ran it and got 567 entries in [1, 1000]. If you could be more specific about what doesn't work, I could try and fix it – Procurance

Answer 4

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.

Standup

I am very impressed by the speed of your implementation, however you only get one solution pr hypotenuse, and therefore your final list is smaller than the full set of solutions because for c=25 there are two solutions: (15, 20, 25) and (7, 24, 25), the len of my list comprehension is 881 because it contains all 'unique solutions where a < b < c, however i am still very impressed by the speed of your algorithm – Geerts

OP's title is a bit misleading: List of numbers whose squares are the sum of two squares vs. what I read: List of numbers whose square is the sum of two squares – Standup