Description
Problem 1
Euler’s sieve is a souped-up version of the sieve of Eratosthenes, which finds the prime numbers. It works
as follows
L = the list of numbers from 2 to N;
P = 2; /* The first prime */
while (P^{2} < N) {
L1 = the list of all X in L such that P <= X <= N/P.
L2 = P*L1;
delete everything in L2 from L;
P = the next value after P in L;
}
return L;
For instance, for N=27, successive iterations proceed as follows:
Initialization
L = [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]
P = 2
First iteration
L1 = [2 3 4 5 6 7 8 9 10 11 12 13]
L2 = [4 6 8 10 12 14 16 18 20 22 24 26]
L = [2 3 5 7 9 11 13 15 17 19 21 23 25 27]
P = 3
Second iteration
L1 = [3 5 7 9]
L2 = [9 15 21 27]
L = [2 3 5 7 11 13 17 19 23 25]
P = 5
Third iteration
L1 = [5]
L2 = [25]
L = [2 3 5 7 11 13 17 19 23]
A. Write a Matlab function EulerSieve1(N) which constructs the Euler sieve, implementing L, L1, L2 as
arrays of integers, as above.
B. Write a Matlab function EulerSieve2(N) which constructs the Euler sieve, implementing L, L1, and
L2 as Boolean arrays, where L[I] = 1 if I is currently in the set L. Thus, the final value returned in the above
example would be the array
[0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0]
1
Problem 2:
There is a theorem that states that, if you carry out the following procedure:
P = any polygon (this can be concave or even cross itself).
loop {
compute the midpoint of each side of P
P = the polygon formed by connecting these midpoints in sequence;
}
Then P will converge toward a series of points that lie on an ellipse. Picture on the next page.
A. Assume that the polygon is represented by two vectors: Px, the array of x-coordinates and Py, the array
of y-coordinates. For example, the polygon with vertices at h0, 0i, h2, 8i, h4, 0i, – h−2, 6i, h6, 6i would be
represented as the arrays
Px = [0, 2, 4, -2, 6]
Py = [0, 8, 0, 6, 6]
Write a Matlab function [Qx,Qy]=ConnectMidpoints(P) that, given a polygon Px,Py constructs the coordinates of the midpoints of P in sequence. For instance if P is the matrix above then ConnectMidpoints(P)
would return
Qx = [1, 3, 1, 2, 3]
Qy = [4, 4, 3, 6, 3]
Each element of Qx is the average of two consecutive columns of Py, and likewise with Qy. For instance
Qx(1) = (Px(1)+Px(2))/2.
The last element of Qx is the average of the last and first element of Px e.g. in the above example Qx(5) =
(Px(5)+Px(1))/2.
Your code should of course work for polygons with any number of points, not just polygons with 5 points.
B. Write a Matlab function ConvergingPolygons(P,N) which takes as input a polygon P and a number
N and draws pictures of the first N polygons in this sequence, starting with P. As in the pictures on the
next page, it should alternate pictures that show the polygon with pictures that show the polygon and the
midpoints.
Let Matlab adjust the scale on each successive picture, or the picture will soon become too small to see.
Also, as always with geometric drawings in Matlab, call axis equal to make sure that the x and y axes
have the same scale.
Note: To make multiple plots on a single figure, use hold on and hold off. To make multiple figure, use
figure(). So the code inside the loop that generated the even-numbered pictures on the next page had the
form
In calling the plot function, be sure to repeat the first point at the so that the polygon closes.
2
Output of ConvergingPolygons(P,6) with x- and y- coordinate initialized by the following Matlab calls:
Px = 7+[1,3,5,7,2.5,4,6].*cos(10*pi*(1:7)/7)
Py = 7+[1,3,5,7,2.5,4,6].*sin(10*pi*(1:7)/7)
3
After 9 more iterations, it straightens itself out and then continues to get closer to a very long, thin ellipse.
4
