Compute Pythagorean triplets in Python via Euclid's method

Hellenic Legacy
8 followers
1 Video View·Sep 25, 2024
This is part of an online course about learning how to use Python to learn mathematics. You don't need to know anything Python before starting this course!
Number theory is so pervasive in mathematics, it's so ubiquitous in mathematics,
that you've actually already studied some components of number theory,
even if you didn't know that what you were studying was actually called number theory.
And in particular, I'm referring to the Pythagorean theorem and the Pythagorean triplets.
So it turns out that the Pythagorean triplets are an important foundation principle
of number theory. It's one of the things that you learn in number theory.
So I'm going to give you a quick reminder of the Pythagorean theorem and a reminder of what
the Pythagorean triplets are, what it means to be a Pythagorean triplet.
It turns out that the mathematician Euclid developed a formula for finding triplets.
So we don't have to just kind of randomly guess we can apply Euclid's formula to find
triplets. So a set of three numbers that conform to the Pythagorean theorem.
So and then I'm going to show you the math formulas and you are going to translate
those formulas into code. Well, I don't think you need a reminder of the Pythagorean theorem.
It's a squared plus b squared equals c squared. You can express it algebraically like this.
You can visualize it geometrically like this on the right triangle.
And yeah, I mean, this is something that I'm sure you know by this point in the course.
Now, you've probably also heard of Pythagorean triplets. I've also mentioned these earlier.
These are sets of integers where the Pythagorean theorem works for integers.
So for example, the two most widely used cases are 3, 4, 5. That's a Pythagorean
triplet because 3 squared plus 4 squared equals 5 squared. And another one that's often used
is 5, 12, and 13. So 5, 12, and 13 is a Pythagorean triplet because 5 squared plus
12 squared equals 13 squared. OK, so the question is, how do we find these three?
How do we find a set of three positive integers where this works, where the Pythagorean theorem
works, where these are integers? So this is the insight that Euclid had. So Euclid discovered
this formula. And basically, we start from integers m and n. And then you compute a as
m squared minus n squared, b as 2 times m times n, and c as m squared plus n squared. So it's
similar to a, but it's plus. Now, it turns out that if you follow this formula, then a squared
plus b squared equals c squared. That's a pretty remarkable feature of numbers. And this is why
it fits into number theory. Now, there's one constraint that Euclid had, well, two constraints.
One is m is greater than n. And the other constraint is that both m and n need to be
integers, need to be positive integers. And so I am modifying that constraint a little bit. So I'm
saying m and n need to be in the set of integers between two and 50. Now, limiting these to be
integers between two and 50 is purely for the purposes of our implementation. But the other
four lines here are part of Euclid's formula. Okay, so what you want to do in Python is implement
this set of equations to get to obtain these Pythagorean triplets. And once you do,
you can make a beautiful image that looks something like this is a really, really
pleasing thing to look at. So what are we looking at here? Well, the x axis is a, and the y axis is
B, and the color axis is C. So we are looking at the Pythagorean triplets represented geometrically
in this ABC space. So again, this is a and this is B, and you see the coordinates of A and B,
and the color maps onto the value of C. So obviously, the further away from the origin
you get this the origin 00. So the further away from the origin, you get the more yellowish the
colors because yeah, the larger A and B are then obviously the larger C is going to be.
Okay, so this is the first part of the Python section is going to be to produce a graph that
looks like this, based on plotting a comma B with colors mapped onto C. And then what we want
to do is empirically confirm that these really are Pythagorean triplets. And the way that we're
going to do that is by just manipulating the Pythagorean theorem a little bit. So the main
Pythagorean theorem is a squared plus b squared equals c squared. So we are going to do is compute
a squared plus b squared minus c squared. Now if these really are Pythagorean triplets,
then the then the result of this equation should be zero should always be zero. So we want to
compute that for all pairs of A and B. So we take all pairs of A and B that we've computed by
following this formula, we compute a squared plus b squared minus c squared. And if that number ever
deviates from zero, then either Euclid was wrong, this formula is wrong, or we've made a coding
error. So we're going to assume Euclid was right. So if this you know, this is just an empirical
confirmation check, a bit of a sanity check. If we get any non zeros, then we've done something
wrong. Alright, so now you can switch to Python, implement these formulas in code with these
constraints, produce a graph that looks like this produce a graph that looks like this. And now I
will switch to Python. For this exercise, I'm going to use NumPy. So import NumPy. And we also
need to do some visualizations. So we need matplotlib.pyplot as pl t. Okay, so now we've
imported the libraries that we need. And let's see, so we want to do something like a double
for loop. So we want to loop over m. So for m, in, in what, well, we want a range that goes from,
from two to 50, which means the range has to be defined by as 51. But I'm actually going to
take this out of the for loop. So I can create it as a separate variable. I'm going to call this
number range equals now here, I'm going to use NumPy. So I'm going to say NumPy dot a range,
two to 51. Okay, so now we can say for m in number range, and then we also want for n in the same
range, the same number range. Okay, so now we have, we're going to get all possible pairs of
m and n in between two and 50. And what do we want to do with these? Well, we want to compute a
equals m squared minus n squared, b, according to the formula was two times m times n, and c
is equal to m squared plus n, m squared plus n squared. Okay, so these are the three formulas.
Now we can run this loop. And it runs successfully in the sense that you don't get any error messages
or warning messages or anything. And it did actually compute these things. But the goal is
not just to compute them, the goal is to store them in a list so that we can make a visualization
out of it. By the way, it's not surprising that a is zero here, because on the last iteration,
m equals n. And so this is just saying, you know, whatever 50 squared is minus 50 squared,
of course, that's trivially equal to zero. Okay, so let's see. So what we want to do
is define these as lists as empty lists. So I'm going to say a, and B and C are equal to empty
lists. And then we can say a dot append equals this thing. And then likewise, let's see, I'll
do a little bit of copy pasting here. So then we're going to append on to B and append on to
C, like this. Okay, and then we can run a again. And now you can see it's it's a really large list
of numbers goes really, really long. We ended up with some variety of numbers and doesn't even show
the whole thing here. Okay, let's see. Now that we have our list of A, B and C, we want to make
a plot. Now you can say PLT dot plot, a comma B, and you know, set these to be circles. And this
confirms that we get the right shape. But in order to map the color onto it, I'm actually
going to use PLT dot scatter. So let's make a scatter plot. And now we can add some additional
options. So scatter is basically, you know, it's almost the same thing as, as regular plot,
it's just going to simplify calling these circles and filling them in with colors a little bit.
So it turns out that to specify the color, you say C equals so the C here is for color
as an input into scatter. So you can see that by looking at the help doc. So I, you know, clicked
inside here, and I press Shift tab on the keyboard. And now we can open up this doc string.
And you can see C is for the color. So we can go down and see here C is for the color. Okay,
so we say C is equal to C. So that's why it's a little bit confusing sometimes when you have the
input to a function be the same as the variable name like this. Okay, so this is getting close.
This is not exactly how I showed it in the slides. So I'm just going to show you some of the things
that I added to make this look a little bit nicer. So the marker, marker is already a circle,
but I'm going to specify that it needs to be a circle. And let's see, I specified that there's
going to be alpha now alpha is the transparency, and it varies between zero and one. So if I set
this to, for example, point one, you can see it's quite dim. And if I or it's dim, because it's
translucent, and and the background is white, and I can set it to be point nine. And now it's darker
because it's only 10% translucent. So I went with point five, which looks like this. And then I
specified that there's going to be a line width of point five. So all of the circles are going to
have a point five line width here. Now you don't really see those here. Because we need to specify
the edge colors to be black. Okay, so that's basically what I showed in the slides. There's
some one more thing, which is just to force the figure size. So set up a figure with one subplot.
And then basically just want to hard code the figure size to be let's try 10 by seven. Yeah,
so that makes it look nicer, forcing the size. And then of course, in the in the slides, I showed
this image with the axis off and then pl t dot show. Alright, so this was the image that I showed
in the slides. And it looks really beautiful. I think it looks like, you know, some kind of could
be the the roof of a building, some some some Middle Eastern architecture or something like
that. It looks looks pretty neat. Or maybe you think it looks like a music hall. These are all
the seats and this would be the stage here. So this is where the musicians are performing,
or where the theater, the actors are. And then here's all the seats in here. And everyone is
really interested. Anyway, so what we want to do now is the empirical confirmation that all of
these pairs of numbers, so A, B, and C, that they really do conform to the Pythagorean theorem. So
that's got to be something like a squared plus b squared, minus c squared. And again, the idea
is that these should all be equal to zero. Now it turns out that if you try to do this,
you're going to get an error. And the error message is that is unsupported operand type for
star star or pow list. And so it's a little bit of a dense error message. But it basically says,
Python is saying, I don't know what to do with a double asterisk on a list. And the problem here
is that, you know, what we want, so here's just a list, you know, what we want to do is say
something like two squared, and then three squared. So we want the answer here to be four
and nine. But it turns out that, yeah, well, this is exactly the error. So we cannot run powers on
a list. However, we can compute element wise powers on a NumPy array. So we can convert this
list into a NumPy array. And that is going to give us the answer that we want. Now, this is
something I discussed earlier in the course in the I forget what that section was called.
Okay, I just looked it up, the section was called Python data types. So if this thing that I just
explained seems confusing, you might want to go back to the section of this course called Python
data types. Anyway, the point is that what we want to do here is convert these lists into NumPy
arrays. And that will allow us to compute our check like this, I'm going to call this
Pythagorean check like this. And then we just want to make a plot. So plt dot plot of
Pyth check, and let's make these circles. And we should see that these are all zero,
which they are. And now there's like 2400 of these, because this is all possible combinations
of A and B. The main part of this video involve translating these equations with these constraints
into code and then visualizing it. But if you were paying attention, you might have noticed
that in fact, we did something wrong, we made a mistake. And maybe it wasn't entirely a mistake,
maybe I did it on purpose. But there is certainly something wrong. That's the important part.
Our code here that we wrote, did not follow this, these equations and these constraints
exactly. So what did we miss? What did we do wrong? Well, that is the goal of this exercise.
So our code did not perfectly match the formula or the constraints. So what you need to do is
look through all of the math on the left hand side of this screen, and look through the code,
either you know this code here or your code on Python in front of you, figure out what we did
wrong, and then fix it. Okay, now I am about to tell you what we did wrong. So So if you want,
if you want to figure it out for yourself, that now is your last opportunity to pause the video.
Okay, so what we did wrong was we ignored this constraint altogether. So these three equations
we implemented perfectly, this constraint, or this, the this list of numbers we implemented,
and that was also fine. We completely ignored this constraint here m greater than n. Now you
can see that here because we set m to be in the number range and n also to be in the number range.
So that means there's going to be many iterations inside this double for loop, where n is actually
greater than m. Okay, so with that in mind, now I'm going to switch back to Python. And we're
going to fix this code to to get that to be correct. So it turns out it's not a very difficult
fix, we just need to change this. So we don't want to loop through for n in the entire number
range, we want for every iteration inside m, n is just going to start at well, it's always going to
start at, let me see, it's always going to start at the at two here, it's always going to start at
the iteration here. And then it's going to go from the first element of two, up to but not including
m. So I'm going to write range like this. So I hope that makes sense. So now, for each iteration
inside m, n is going to start at the number two, which is, you know, the first element of number
range here. And then it's going to go up to m but not including m. So up to but excluding m. And this
little change here gives us our, our constraint specified in the slides that m is greater than n.
Okay, so run that again. And then let's see, I'm actually going to copy and insert cell above,
just because I want to leave this image here, I don't want to overwrite this.
So now we can rerun this. And we can see this looks a little bit different. And in fact, what's
going on is that this is only half of the image here. And to understand why we have that constraint
here, I'm actually going to leave the axis on by commenting out axis off. Oh, yeah, wait,
no, I wanted to show the original one. Sorry, let me go back. So now this is number range to rerun
that. So now you see that we only have all positive values here. Previously, this is what we did in
first part of the course, we ended up with a having negative values. So B had positive values,
but a could have positive values or negative values, this is the consequence of ignoring the
constraint, m must be greater than n. So in this video, I gave you a quick reminder of the
Pythagorean theorem. And in particular, we focused on Euclid's formula for computing Pythagorean
triplets. Transcribed by https://otter.ai
