CSE1729 – Principles of Programming
April 29, 2021
Review Problem
Activities
¡°Don¡¯t they teach recreational mathematics anymore?¡± – Doctor Who
1. Enjoy this clip of the BBC television show Doctor Who: http://www.youtube.com/watch?v= ee2If8jSxUo. Ok, now get to work. Your job, should you choose to accept it, is to write a function (and any helper functions necessary) to find the next happy prime in the sequence …,313,331,367,379,…. Then, write the necessary functions to define a Scheme object that produces a stream of happy primes through the function next.
Now, what did he say?
¡°Any number that reduces to one when you take the sum of the square of it¡¯s digits and continue iterating until it yields 1 is a happy number. Any number that doesn¡¯t, isn¡¯t. A happy prime is a number that¡¯s both happy and prime, now TYPE IT IN.¡±
(a) So, first off we need a function that converts an integer to a list. Define a Scheme function named num->list which converts any integer to a list of single-digit integers (¨ la the arbitrary precision integers from a previous problem set). For instance, the expression (num->list 12345) would return ‘(1 2 3 4 5).
(b) To compute the sum of the squares of the digits, define a Scheme function which takes a list of integers as a parameter and returns the sum of the squares of the integers in the list.
(c) If we ever sum the square of the digits of a number and it produces a number we¡¯ve already computed, we will always loop through the numbers we¡¯ve already tried. We¡¯ll need to keep track of the numbers we¡¯ve tried so that we can stop if we come to a number we¡¯ve already seen before. Define Scheme functions insert and element? which implement a set data-structure with a binary search tree.
(d) Use all of these helper functions to define a Scheme function named is-happy? which, given a positive integer as a parameter, returns true if the number is a happy number and false otherwise. It might be useful to define a helper function that also takes the set, s, as a parameter and adds the sum of the squares of the digits of a number to that set if it isn¡¯t there already.
(e) Use your new is-happy? function and a function that tests for primality to define a Scheme function named happy-prime? which, given a positive integer as a parameter, returns true if the number is a prime number that is also a happy number and false otherwise.
(f) Define a Scheme function named happy-primes which takes an integer n as a parameter and returns a list of the first n happy primes. You should see that the happy primes mentioned in the clip are the 18th, 19th and 20th. What is the 21st?
(g) Finally, package all the previous functions into an object that represents a stream of happy primes. Your object should expose the functions empty?, head and rest.
1