COMP 210 Lab 4: Natural Numbers

Index: What is a natural number?, Template, Examples

What is a natural number?

Review: Among computer scientists, the natural numbers are 0,1,2,3,... (Among mathematicians, there's some disagreement between either 0,1,2,3,... or 1,2,3,... A history of Zero.) We can define these with the data definition 

     ; A natural number (nat) is one of
     ;    0                             i.e., zero, or
     ;    (add1 n), where n is a nat    i.e., the successor of a nat
We then consider, e.g., 4 only a convenient shorthand for the official way of writing the natural number (add1 (add1 (add1 (add1 0)))).

At the beginning of the course we wrote functions on numbers, so what's different now? With the previous functions, we had a nice simple closed form equation for our function. Many other functions on numbers are not so simple and, instead, take advantage of this recursive structure of natural numbers. One commonly seen in high school is factorial:

0! = 1
(n+1)! = n × (n!)

Template (Review)

The template is (mostly) straightforward, following the ideas we've seen with lists: 

     ; TEMPLATE
     ; f-nat : nat -> ...
     ; (define (f-nat n)
     ;    (cond
     ;        [(zero? n)      ...]
     ;        [(predicate? n) ...(f-nat (selector n))...]

But what should the predicate and selector be? If we had defined the non-zero natural numbers via our own structure, e.g., 

     (define-struct successor (n))
then we'd know how to answer this. But, we sort of cheated, instead using the built-in add1 function as a constructor and the built-in numbers are "shorthand". We did this solely as a matter of convenience, so that we could use other built-in math functions. So, we'll sort of cheat and use corresponding other built-in functions as the predicate and selector. The resulting template is 
     ; TEMPLATE
     ; f-nat : nat -> ...
     ; (define (f-nat n)
     ;    (cond
     ;        [(zero? n)     ...]
     ;        [(positive? n) ...(f-nat (sub1 n))...]

Examples

Now it's time for lots of examples. You probably won't have time for all of these during lab.

Natural number examples

As usual, follow the remaining four function-specific steps of the design recipe for each.

  1. Develop a function returning the sum of the numbers 0..n, given n as input.

  2. Develop a function returning the list of the numbers n..0 (left-to-right), given n as input.

  3. Develop a function returning the list of the numbers 0..n (left-to-right), given n as input.

    Note: This is surprisingly a bit tougher than the previous function. There are a couple main strategies for this. One follows the traditional "reverse accumulation" we've been using. Another follows the "forward accumulation" (or accumulator-style) just introduced in class.

  4. Develop a function returning the list of all the prime numbers in n..0, given n as input. To accomplish this, first create the following series of helper functions:

    1. Develop a function determining whether a given n is a factor of a given m. Use non-recursive mathematical functions for this.

    2. Develop a function determining whether a given n has any factors between 2 and a given m.

      Hint: This is a good example of one of the few times you want to alter the standard natural number template. We are only interested in this when m≥2, and so we really want to talk about the type natural-numbers-≥2, with an appropriate data definition and template.

    3. Develop a function determining whether a given n is prime. The numbers 0 and 1 are not prime.

      Note: What is an appropriate value of m to give to the previous function?

    Note: There are many other ways of breaking down this overall task into subparts. This way is inefficient, but fairly straightforward, and based upon what we've covered so far.