Wednesday, October 1st, 2025¶

In [1]:

import numpy as np
import matplotlib.pyplot as plt

The Euclidean algorithm (continued)¶

Last class, we looked at applying the Euclidean algorith to compute greatest common denominators.

In [2]:

def Euclidean_algorithm(a,b):
    while a != 0 and b != 0:
        if a > b:
            a,b = b,a
        b = b - a
    return a

In [3]:

Euclidean_algorithm(15,10)

Out[3]:

In [4]:

Euclidean_algorithm(2**3 * 3**4, 2**2 * 3**2)

Out[4]:

Suppose we use the function above to compute the greatest common divisor of $a = 2$ and $b = 100,000,000$.

In [5]:

Euclidean_algorithm(2,100000000)

Out[5]:

How did the algorithm proceed? Within the while loop, the function went through the sequence b = 999999998, 999999996, 999999994, 999999992, .... In other words, we had to perform many subtractions before finally ending up at b=0 and a=2, giving the greatest common divisor 2. Can we do anything to speed this process up?

In [6]:

def Euclidean_algorithm2(a,b):
    while a != 0 and b != 0:
        if a > b:
            a,b = b,a
        b = b % a
    return a

In [7]:

Euclidean_algorithm2(2,100000000)

Out[7]:

Project 2: Pythagorean triples¶

Exercise: Write a function get_ptriples that takes in an integer n and returns a list of all Pythagorean triples $(a,b,c)$ where $1 \leq a, b \leq n$.

In [22]:

def is_square(n):
    sqrt_n = n**(1/2)
    if round(sqrt_n)**2 == n:
        return True
    else:
        return False

In [ ]:

for a in range(1,n+1):
    for b in range(1,n+1):
        if is_square(a**2 + b**2):
            c =

In [ ]:

ptriples = get_ptriples(1000)

In [ ]:

print(ptriples[:10])

Exercise: Plot $a$ vs $b$ for the triples obtained from get_ptriples for various values of n and describe any patterns that emerge.

Some thoughts:

It might be worthwhile to use subplots to include several graphs of Pythagorean doubles (with varying maximum $a$/$b$ values) within a single figure. You can then try to identify what patterns become apparent at different scales.
Try to explain some of the patterns that appear. For example, we have discussed the $a$-$b$ symmetry in class. What other structures can we see? Can we explain them?
In studying the structure of the Pythagorean doubles, it will be helpful to look separately at the primitive Pythagorean doubles. That is, Pythagorean doubles $(a,b)$ such that $\gcd(a,b) = 1$ (or equivalently, Pythagorean triples $(a,b,c)$ such that $\gcd(a,b,c) = 1$).

Exercise: Given a list ptriples of Pythagorean triples, use list comprehension to generate the sub-list of primitive Pythagorean triples.

In [8]:

ptriples = [[3, 4, 5],
[4, 3, 5],
[5, 12, 13],
[6, 8, 10],
[8, 6, 10],
[8, 15, 17],
[9, 12, 15],
[12, 5, 13],
[12, 9, 15],
[12, 16, 20],
[15, 8, 17],
[15, 20, 25],
[16, 12, 20],
[20, 15, 25]]

In [11]:

ptriples_a_lt_b = [[a,b,c] for a,b,c in ptriples if a <= b]
ptriples_b_lt_a = [[a,b,c] for a,b,c in ptriples if b <= a]

plt.figure()
plt.subplot(aspect='equal')

a_lt_b_a_list = [a for a,b,c in ptriples_a_lt_b]
a_lt_b_b_list = [b for a,b,c in ptriples_a_lt_b]

b_lt_a_a_list = [a for a,b,c in ptriples_b_lt_a]
b_lt_a_b_list = [b for a,b,c in ptriples_b_lt_a]

plt.plot(a_lt_b_a_list, a_lt_b_b_list, 'mo')
plt.plot(b_lt_a_a_list, b_lt_a_b_list, 'go')

plt.plot([0,20],[0,20],'k--')

Out[11]:

[<matplotlib.lines.Line2D at 0x2a56ce7f890>]

No description has been provided for this image

In [ ]:

for a in range(1,n+1):
    for b in range(1,a+1):
        # check if (a,b) is a Pythagorean double
        append([a,b,c])
        append([b,a,c])

In [14]:

def plot_pdoubles(ptriples, color='m'):
    a_list = [a for a,b,c in ptriples]
    b_list = [b for a,b,c in ptriples]
    plt.plot(a_list, b_list, 'o', color=color)

Visualizing 2-dimensional arrays¶

Consider the following 2D-array, filled with integers 0 up to 99.

In [23]:

A = np.arange(100).reshape(10,10)
print(A)

[[ 0  1  2  3  4  5  6  7  8  9]
 [10 11 12 13 14 15 16 17 18 19]
 [20 21 22 23 24 25 26 27 28 29]
 [30 31 32 33 34 35 36 37 38 39]
 [40 41 42 43 44 45 46 47 48 49]
 [50 51 52 53 54 55 56 57 58 59]
 [60 61 62 63 64 65 66 67 68 69]
 [70 71 72 73 74 75 76 77 78 79]
 [80 81 82 83 84 85 86 87 88 89]
 [90 91 92 93 94 95 96 97 98 99]]

For this array, it is small enough that we can simply print the array to understand its contents. For other larger arrays, this becomes infeasable. The plt.imshow function is a very useful tool for visualizing 2D arrays of any size. The basic syntax is plt.imshow(<some 2D array>).

When calling plt.imshow on a 2D array, the graph places a colored block at each row & column index pair. The color of the block is determined by the value of the array in that row & column position. The colors are assigned according to a designated colormap.

The colors are assigned so that the lowest value in the array is assigned the "lowest" color in the colormap (dark blue by default) and the highest value of the array is assigned the "highest" color in the colormap (yellow by default). Intermdiate values are assigned intermediate colors between the "lowest" and "highest" colors in the colormap.

In [24]:

plt.imshow(A)

Out[24]:

<matplotlib.image.AxesImage at 0x2a5726c4590>

Let's make some changes to the A array and see how the output of plt.imshow is affected. For example, suppose we want to set the values in rows 3 or 4 and columns 6 or 7 to be 120.

In [25]:

A[3:5, 6:8] = 120
print(A)

[[  0   1   2   3   4   5   6   7   8   9]
 [ 10  11  12  13  14  15  16  17  18  19]
 [ 20  21  22  23  24  25  26  27  28  29]
 [ 30  31  32  33  34  35 120 120  38  39]
 [ 40  41  42  43  44  45 120 120  48  49]
 [ 50  51  52  53  54  55  56  57  58  59]
 [ 60  61  62  63  64  65  66  67  68  69]
 [ 70  71  72  73  74  75  76  77  78  79]
 [ 80  81  82  83  84  85  86  87  88  89]
 [ 90  91  92  93  94  95  96  97  98  99]]

In [26]:

plt.imshow(A)

Out[26]:

<matplotlib.image.AxesImage at 0x2a573125bd0>

Note: Just like the plt.plot function, we can take manual control of the figure and axes generation using plt.figure and plt.subplot. We can use plt.imshow within a subplot in the same way that we use plt.plot. There are also many optional arguments that can be included to modify the default behavior of plt.imshow. For example:

We can supply a value vmin that the "darkest" color will be assigned to. Any values in the array that are below this minimum value will also be mapped to the "darkest" color.
We can supply a value vmax that the "brightest" color will be assigned to. Any values in the array that are above this maximum value will also be mapped to the "brightest" color.

In [29]:

plt.imshow(A, vmin=20, vmax=99)

Out[29]:

<matplotlib.image.AxesImage at 0x2a573268e10>

By default, plt.imshow will not interpolate colors between neighboring array positions (unless your screen's resolution is too low to display all of the colored blocks). That is, we can see a discrete set of boxes of colors. We can modify this behavior by using the interpolation keyword. Some available interpolation methods include:

'nearest': each pixel is colored according to the closest colored block to that pixel
'bilinear': each pixel is colored according to a bilinear interpolation (both horizontally and vertically) between nearby colored blocks
'bicubic': each pixel is colored according to a bicubic interpolation (both horizontally and vertically) between nearby colored blocks
'lanczos': each pixel is colored according to Lancsoz interpolation (both horizontally and vertically) between nearby colored blocks

In [30]:

plt.imshow(A, vmin=20, vmax=99, interpolation='bilinear')

Out[30]:

<matplotlib.image.AxesImage at 0x2a5732c9d10>

In [31]:

plt.imshow(A, vmin=20, vmax=99, interpolation='bicubic')

Out[31]:

<matplotlib.image.AxesImage at 0x2a57332ec10>

We can also modify the color choices used by plt.imshow. These choices are called colormaps. A collection of colormaps can be found on the Matplotlib documentation page.

The cmap keyword argument can be used to change colormaps:

In [32]:

plt.imshow(A, vmin=20, vmax=99, interpolation='bicubic', cmap='plasma')

Out[32]:

<matplotlib.image.AxesImage at 0x2a57337fd90>

Note: The figures produced above do not indicate what the actual values in the array are. We can call plt.colorbar to add a colorbar that indicates which values correspond to which colors.

In [34]:

plt.imshow(A, interpolation='bicubic', cmap='plasma')
plt.colorbar()

Out[34]:

<matplotlib.colorbar.Colorbar at 0x2a5734cbed0>

We can also use colormaps in plt.plot to assign colors to our plots. The colormaps can be found in the cm submodule of matplotlib.

In [35]:

import matplotlib.cm as cm

In [36]:

cm.plasma

Out[36]:

plasma

under

bad

over

Each colormap works as a function that takes in a float, where:

any input 0 or less returns the color at the left-end of the colormap,
any input 1 or more returns the color at the right-end of the colormap,
any input between 0 and 1 returns the color that is proportionally between the left-end and right-end of the colormap.

In [41]:

x = np.linspace(0,1,1000)
plt.plot(x, x**2, color=cm.plasma(.1), label='10%')
plt.plot(x, 1 + x**2, color=cm.plasma(.5), label='50%')
plt.plot(x, 2 + x**2, color=cm.plasma(.9), label='90%')

plt.legend()

Out[41]:

<matplotlib.legend.Legend at 0x2a5726c56a0>

What does the output actually look like when we plug a float into a colormap?

In [40]:

cm.plasma(.25)

Out[40]:

(np.float64(0.494877),
 np.float64(0.01199),
 np.float64(0.657865),
 np.float64(1.0))