Monday, September 22nd, 2025¶

Project 1: A prime or not a prime¶

Reminder, Project 1: A prime or not a prime, is due this Wednesday at 11:59PM. Some comments:

  • Your report should be written with the expectation that the reader will be someone not from our class. They will not be familiar with the terms that we have introduced, so your report will need to introduce them (e.g. define prime numbers, define what it means to be prime-like, to be a false prime, etc.). See the sample project to get an idea of the style.
  • Your report should be written as a self-contained work. There should not be references to "Exercise 1", or "Part 1", "Part 2", etc. that are described on the project page. These parts will likely show up somewhere in the report (e.g. you will want to define and use a get_primes function), but they should come up naturally through the narrative of the report.
  • Your code should be able to find the first 20 false primes in a reasonable amount of time (say, 30 seconds or less). If it takes longer, try to think of ways that we can improve the speed (e.g. use the pow function, use the $\sqrt{n}$ optimization for identifying primes, etc.). You can also ask for tips on making improvements.
  • Before submitting your report, please go through the checklist at the top of the Project Report Guide. You should make absolutely sure that your notebook can be run top-to-bottom with no errors.

Experiment:¶

In [1]:
import time

From the time module, there is a function sleep that will cause Python to hold for a desired number of seconds.

In [8]:
def f():
    print('Hello')
    return True
In [9]:
def g():
    print('Goodbye')
    return False
In [10]:
def h():
    time.sleep(5)
    print('Good morning')
    return True
In [11]:
def i():
    time.sleep(5)
    print('Good night')
    return False
In [12]:
if f() and h():
    print('Done')

Hello
Good morning
Done
In [13]:
if f() and i():
    print('Done')

Hello
Good night
In [14]:
if h() and f():
    print('Done')

Good morning
Hello
Done
In [15]:
if i() and f():
    print('Done')

Good night
In [16]:
if g() and h():
    print('Done')

Goodbye

How does this connect to Project 1?

In [ ]:
def is_prime(n):
    ...
In [ ]:
def is_prime_like(n):
    ...
In [ ]:
def is_false_prime(n):
    if is_prime_like(n) and not is_prime(n):
        return True
    else:
        return False

Some thoughts:

If $n$ is an even false prime, consider what happens for $a = n - 1 \equiv -1 \pmod n$. We must have $$(n-1)^n \equiv (n-1) \mod n$$

or

$$(-1)^n \equiv -1 \pmod n$$

$$n = p_1 * p_2 * ... * p_m$$

$$n = p_1 \cdot p_2 \cdots p_m$$

In [ ]:
def get_false_primes(N=20):
    ...
    return first_N_false_primes
In [ ]:
false_primes = get_false_primes(20)

Project 2: Pythagorean triples¶

The second project deals with Pythagorean triples, that is, triples of integers $(a,b,c)$ such that $a^2 + b^2 = c^2$. The project is due Monday, October 6th at 11:59PM. We've already seen all of the Python tools necessary to complete this project, so I would encourage you to get started as soon as you are finished with Project 1.

Plotting with matplotlib.pyplot (continued)¶

Last week, we looked at using the plot function from matplotlib.pyplot for creating graphs in Python. Recall, we typically use import matplotlib.pyplot as plt to get access to the plot function via plt.plot.

Exercise: Use plt.plot to plot $y = \sin(x)$ and $y=\cos(x)$ for $0 \leq x \leq 2\pi$.

Note: we can import the sin and cos functions from the math module.

In [18]:
from math import sin, cos, pi

N = 1000          # We're going to plot using N+1 data-points
a = 0             # Left end of the the x-interval
b = 2*pi          # Right end of the x-interval

dx = (b-a)/N                             # The width between adjacent x-values
x_list = [a + i*dx for i in range(N+1)]  # List of N+1n equally spaced x-values from a to b
sin_x_list = [sin(x) for x in x_list]    # sin(x) list
cos_x_list = [cos(x) for x in x_list]    # cos(x) list
In [19]:
import matplotlib.pyplot as plt

plt.plot(x_list, sin_x_list, label='$y=\sin x$')
plt.plot(x_list, cos_x_list, label='$y=\cos x$')

plt.legend()
plt.title('Sine and cosine')
plt.xlabel('$x$')
plt.ylabel('$y$')
Out[19]:
Text(0, 0.5, '$y$')
No description has been provided for this image

Some thoughts:

  • It would be nice if we could more easily generate a list of equally spaced $x$-values between $0$ and $2\pi$ (or, more generally, spanning some interval).
  • It would be nice if we could more easily apply a function to a list of data points (e.g. something like sin(x_list)).
In [20]:
sin(x_list)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[20], line 1
----> 1 sin(x_list)

TypeError: must be real number, not list

NumPy¶

The NumPy (Numerical Python) module contains many useful tools for numerical calculations in Python. We typically import the module and assign the name np.

In [21]:
import numpy as np

The basic building blocks in NumPy are arrays, which in many ways behave like lists. We can use the np.array function to convert a list to an array.

In [22]:
my_array = np.array([0,1,2,3,4,5,6])
my_array
Out[22]:
array([0, 1, 2, 3, 4, 5, 6])

Just like with lists, we can acccess elements of an array by index using square brackets:

In [23]:
my_array[0]
Out[23]:
np.int64(0)
In [24]:
my_array[-1]
Out[24]:
np.int64(6)

We can also use slicing to access parts of an array:

In [25]:
my_array[1::2]
Out[25]:
array([1, 3, 5])

Unlike lists, NumPy arrays are built to perform arithmetic operations on an element-by-element basis. For example, compare what happens when we multiply a list by an integer and what happens when we multiply an array by an integer:

In [26]:
my_list = [0,1,2,3,4,5,6]
3 * my_list
Out[26]:
[0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6]
In [27]:
3 * my_array
Out[27]:
array([ 0,  3,  6,  9, 12, 15, 18])

In a similar way:

  • Adding/subtracting/multiplying/dividing an array by an integer/float adds/subtracts/multiplies/divides each element by the integer/float.
  • Exponentiating/modular dividing an array by an integer/float is performed on each element.
  • If we have two arrays of the same shape, we can add/subtract/multiply/divide/exponentiate/modular divide one by the other. The operation will be performed element-by-element (that is, the first elements from each array will be added/subtracted/multiplied/etc., the second elements from each array will be...).
In [28]:
my_array1 = np.array([0,1,2,3])
my_array2 = np.array([4,5,6,7])
In [29]:
my_array1 + my_array2
Out[29]:
array([ 4,  6,  8, 10])
In [30]:
my_array1 ** my_array2
Out[30]:
array([   0,    1,   64, 2187])

Let's return to the earlier exercise of plotting $y=\sin(x)$ and $y=\cos(x)$. The np.linspace function can be used to easliy generate an array of evenly spaced points over some interval. The basic syntax

np.linspace(a,b,N)

generates an array of $N$ evenly spaced points over the interval $[a, b]$.

In [32]:
#help(np.linspace)
In [33]:
N = 1000
a = 0
b = 2*pi

x = np.linspace(a,b,N+1)

We now want to apply the sin and cos functions to each element in the array.

In [34]:
sin(x)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[34], line 1
----> 1 sin(x)

TypeError: only length-1 arrays can be converted to Python scalars

Note: We imported the sin and cos functions from the math module, but they are not designed to work with arrays. Instead, we can either import sin and cos from the numpy module (replacing the previously imported versions from the math module), or we can use np.sin and np.cos.

Exercise: Use NumPy and plt.plot to plot $y = \sin(x)$ and $y=\cos(x)$ for $0 \leq x \leq 2\pi$.

In [35]:
sin_x = np.sin(x)
cos_x = np.cos(x)
In [36]:
plt.plot(x,sin_x,label='$y=\sin x$')
plt.plot(x,cos_x,label='$y=\cos x$')

plt.title('Sine and cosine')
plt.xlabel('$x$')
plt.ylabel('$y$')
plt.legend()
Out[36]:
<matplotlib.legend.Legend at 0x14f94589e50>
No description has been provided for this image