Geek Answers Handbook

List of numbers whose squares are the sum of two squares

I just started to learn Python and started to make some problems just to help build my skills, but I am very fixated on this issue.

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

Tips: There are several approaches. You may find it helpful to have a list of all square numbers. An operator may be helpful.

Here is the code I came 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 am facing is that Python takes many years to perform these calculations (I waited about ten minutes and still printed the numbers). Any hints on how to solve this problem would be greatly appreciated.

ps The main thing is to use lists. Hints would also be more appreciated than the decision itself.

Thanks!

+7
source share
4 answers

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

in the following way:

 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 timed it and it takes 46 seconds on my computer.

+2
source

First of all, you do not solve the problem. You need to check to make sure that (x+b)**.5 is actually an integer. Secondly, if you print numbers, you have already calculated all the numbers. Doing the above will reduce the time required for this step.

+7
source

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.

+1
source

I just answered it 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

It runs almost instantly.

0
source

More articles:


All Articles