Assignment_example
November 23, 2024
This is an example notebook to model how you should structure your assignment (it
contains the examples we discussed in class on Friday November 22nd).
1 Math 2110, Homework 9, Your Name, B00000000
1.1 Project Euler, Problem 1
1.1.1 Problem statement
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The
sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
1.1.2 Python code
[2]: sum = 0
for i in range(1,1000):
if i % 3 == 0 or i % 5 == 0:
sum = sum + i
print(sum)
233168
1.1.3 Brief explanation
My program checks every number i in the range from 1 (inclusive) to 1000 (exclusive). It checks
whether i is divisible by 3 or by 5, using the modulo operation. The relevant values of i are added
to the sum.
1.1.4 Testing
I tested my program by adding a “print” statement which printed out each value of i that is added
to the sum. I checked that these were indeed the numbers below 1000 that were divisible by 3 or
5 (for example, 3, 5, 6, 9, 10, 12, 15, …, 995, 996, 999). Thus, I am convinced that my program is
correct.
1.1.5 Answer
The sum of all the multiples of 3 or 5 below 1000 is 233168.
1
1.2 Project Euler, Problem 2
1.2.1 Problem statement
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By
starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find
the sum of the even-valued terms.
1.2.2 Python code
[3]: sum = 0
(a,b) = (1,2) # The first two Fibonacci numbers
while a <= 4000000:
if a % 2 == 0:
sum += a
(a,b) = (b,a+b) # Calculate the next Fibonacci number a+b, and also store␣
↪the "old" value of b in a.
print(sum)
4613732
1.2.3 Brief explanation
My program enumerates the Fibonacci sequence by using 2 variables a and b, which hold the
“current” and “next” Fibonacci number. In the beginning, we start with the first two Fibonacci
numbers, (a,b) = (1,2). After each iteration, we update this with (a,b) = (b,a+b), which means
that b becomes the new “current” number and a+b becomes the new “next” number. As required
in the problem statement, we repeat this as long as a does not exceed 4000000.
For each Fibonacci number a thus found, we check whether a is even (using the modulo operation),
and if it is even, we add it to the sum (which is initially zero). Finally, we output the result of the
summation.
1.2.4 Testing
I tested my program by adding a print statement to the while-loop, printing out each value of a. I
checked the first few terms, to ensure that they were indeed the terms of the Fibonacci sequence
1, 2, 3, 5, 8, … . I also checked the last term, to make sure it was the last one below 4 million.
Checking for evenness and summing are pretty straightforward, so I am convinced that my program
is correct.
1.2.5 Answer
The sum of the even-valued terms in the Fibonacci sequence up to 4 million is 4613732.
2
1.3 Project Euler, Problem 3
1.3.1 Problem statement
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
1.3.2 Python Code
[4]: n = 600851475143
d = 2
while n > 1:
if n % d == 0:
print(d, "is a factor")
n = n // d
else:
d = d + 1
71 is a factor
839 is a factor
1471 is a factor
6857 is a factor
1.3.3 Brief explanation
My program starts with the number n that we need to compute the prime factors of. It tests every
possible divisor d, starting from d. If n is divisible by d, we print a message, and divide n by d. This
way, n gets smaller. (When n reaches 1, the program stops, as there are no more divisors). In case
d does not divide n, we try the next d, and so on.
1.3.4 Testing
I tested my program by multiplying the computed factors. Their product is indeed equal to n:
[5]: 71 * 839 * 1471 * 6857
[5]: 600851475143
In addition, I also tested my program by factoring several other (simpler) numbers, such as n =
3000, n = 5555. It got the correct answer for these test numbers, so I am convinced that my
program is correct.
1.3.5 Answer
The largest divisor of 600851475143 is 6857.