Introduction

In this assignment you will work on recursion on numbers in racket. This assignment is closely related to the sum-factors exercise in lab 4

What to hand in, and how to hand it in, and when

• Make a directory ~/cs2613/assignments/A1 (i.e. in your git repo for this class).

• Use "#lang htdp/bsl" for this assignment

• Hand in all your work for this assignment in a file ~/cs2613/assignments/A1/sum-of-prime-factors.rkt

• Make sure you commit and push all your work using git before 16:30h on Thursday September 26.

Marking

• This assignment will be worth 5% of your final grade.
• You will be marked on the last version pushed to coursegit
• For a rubric (marking scheme), see racket-assignment

Question 1

Write a function next-factor that returns the smallest factor (divisor) of the first argument that is at least as big as the second argument. Use the structural recursion on natural numbers pattern. Your function should pass the following tests

(check-expect (next-factor 11 2) 11)
(check-expect (next-factor 18 10) 18)
(check-expect (next-factor 64 2) 2)

Question 2

Our overall goal is to sum up the prime factors of a given number. In general determining whether a number is prime is a bit tedious, but we can take advantage of the fact that the smallest non-trivial (bigger than 1) factor of a number must be prime (this follows from the fact that divisors of a number are no larger than it). Write a function smallest-factor that computes the smallest non-trivial factor of a number. Your function should pass the following tests. This function should not use recursion, and should call next-factor. Don’t overthink this, the answer is very simple.

(check-expect (smallest-factor 1024) 2)
(check-expect (smallest-factor 15) 3)
(check-expect (smallest-factor (* 17 19)) 17)

Question 3

Write a recursive function reduce that divides the first number by second as many times as evenly possible (i.e. working only with integers). This should use a similar pattern to Question 1. Your function should pass the following tests.

(check-expect (reduce 1024 2) 1)
(check-expect (reduce 7429 17) 437)
(check-expect (reduce 75 5) 3)

Question 4

Write a function sum-of-prime-factors that sums the prime factors of it’s argument. Your function should use recursion and call reduce and smallest-factor. Your function should pass the following tests. Note that the base case here is 1, rather than 0, as demonstrated by one the tests.

(check-expect (sum-of-prime-factors 1) 0)
(check-expect (sum-of-prime-factors 1024) 2)
(check-expect (sum-of-prime-factors 75) 8)
(check-expect (sum-of-prime-factors 7429) 59)