# Section 11Natural Numbers

The only self-referential data definitions we have seen thus far involved `cons` and lists of arbitrary length. We needed such data definitions because the classes of lists that we wanted to process were of arbitrary size. Natural numbers are another class of data whose elements are of arbitrary size; after all, there is no limit on how large a natural number can be, and, at least in principle, a function should be able to process them all.

In this section, we study how to describe natural numbers with self-referential data definitions and how to develop functions that process natural numbers in a systematic fashion. Since such functions come in many flavors, we study several different flavors of definitions.

## 11.1  Defining Natural Numbers

People normally introduce natural numbers via enumeration: `0`, `1`, `2`, etc.34 The abbreviation ``etc.'' at the end says that the series continues in this manner. Mathematicians and mathematics teachers often use dots for the same purpose. For us, however, neither the ``etc.'' nor the dots is good enough, if we wish to design functions on natural numbers systematically. So, the question is what it means to write down ``etc.,'' or put differently, what a complete, self-contained description of the natural numbers is.

The only way to remove the informal ``etc.'' from the enumeration is to describe the collection of numbers with a self-referential description. Here is a first attempt:

0 is a natural number.
If n is a natural number, then one more than n is one, too.
While this description is still not quite rigorous,35 it is a good starting point for a Scheme-style data description:

A natural-number is either

1. `0` or

2. `(add1 n)` if `n` is a natural number.

The operation `add1` adds `1` to a natural number. Of course, we could use `(+ ... 1)` but `add1` stands out and signals ``natural number,'' as opposed to arbitrary number, to the reader of a data definition and a function.

Although we are familiar with natural numbers from school, it is instructive to construct examples from the data definition. Clearly,

```0
```

is the first natural number, so

```(add1 0)
```

is the next one. From here, it is easy to see the pattern:

```(add1 (add1 0))
```

The examples should remind us of the lists construction process. We built lists by starting with `empty` and by `cons`tructing on more items. Now we build natural natural numbers by starting with `0` and by `add`ing on `1`. In addition, natural numbers come with century-old abbreviations. For example, `(add1 0)` is abbreviated as `1`, `(add1 (add1 0))` as `2`, and so on.

A function on natural numbers must extract the number that went into the construction of a positive natural number just like a function on lists must extract the list that went into a `cons`tructed list. The operation that performs this ``extraction'' is called `sub1`. It satisfies the law

```(sub1 (add1 n)) = n
```

just as the `rest` operation satisfies the law

```(rest (cons a-value a-list)) = a-list
```

Of course, `(- n 1)` would also work, but `sub1` stands out and signals that the function processes natural numbers.

## 11.2  Processing Natural Numbers of Arbitrary Size

Let us develop the function `hellos`. It consumes a natural number `n` and produces a list of `n` copies of `'hello`. We can write the contract for this function:

```;; `hellos : N  ->  list-of-symbols`
;; to create a list of `n` copies of `'hello`
(define (hellos n) ...)
```

And we can make up examples:

```(hellos 0)
;; expected value:
empty
```

```(hellos 2)
;; expected value:
(cons 'hello (cons 'hello empty))
```

The design of a template for `hellos` follows the design recipe for self-referential data definitions. We immediately see that `hellos` is a conditional function, that its cond-expression has two clauses, and that the first clause must distinguish `0` from other possible inputs:

```(define (hellos n)
(cond
[(zero? n) ...]
[else ...]))
```

Furthermore, the data definition says that `0` is an atomic value, and every other natural number is a compound value that ``contains'' the predecessor to which `1` was added. Hence, if `n` is not `0`, we subtract `1` from `n`. The result is also a natural number, so according to the design recipe we wrap the expression with `(hellos ...)`:

```(define (hellos n)
(cond
[(zero? n) ...]
[else ... (hellos (sub1 n)) ... ]))
```

Now we have exploited every hint in the data definition and are ready to proceed with the definition.

Assume `(zero? n)` evaluates to true. Then the answer must be `empty`, as the examples illustrate. So assume the input is greater than `0`. For concreteness, let us say it is `2`. According to the suggestion in the template, `hellos` should use `(hellos 1)` to compute a part of the answer. The purpose statement specifies that `(hellos 1)` produces `(cons 'hello empty)`, a list with one `'hello`. In general, `(hellos (sub1 n))` produces a list that contains n - 1 occurrences of `'hello`. Clearly, to produce a list with `n` occurrences, we must `cons` another `'hello` onto this list:

```(define (hellos n)
(cond
[(zero? n) empty]
[else (cons 'hello (hellos (sub1 n)))]))
```

As usual, the final definition is just the template with a few extras.

Let's test `hellos` with some hand-evaluations:

```  (hellos 0)

= (cond
[(zero? 0) empty]
[else (cons 'hello (hellos (sub1 0)))])

= (cond
[true empty]
[else (cons 'hello (hellos (sub1 0)))])

= empty
```

It confirms that `hellos` works properly for the first example.

Here is another example:

```  (hellos 1)

= (cond
[(zero? 1) empty]
[else (cons 'hello (hellos (sub1 1)))])

= (cond
[false empty]
[else (cons 'hello (hellos (sub1 1)))])

= (cons 'hello (hellos (sub1 1)))

= (cons 'hello `(hellos 0)`)

= (cons 'hello empty)
```

For the last step in the calculation, we can exploit that we already know that `(hellos 0)` evaluates to `empty` and replace the (underlined) expression with its result.

The last hand-evaluation shows that the function works for the second example:

```  (hellos 2)

= (cond
[(zero? 2) empty]
[else (cons 'hello (hellos (sub1 2)))])

= (cond
[false empty]
[else (cons 'hello (hellos (sub1 2)))])

= (cons 'hello (hellos (sub1 2)))

= (cons 'hello `(hellos 1)`)

= (cons 'hello (cons 'hello empty))
```

We can again exploit what we know about `(hellos 1)`, which greatly shortens the hand-evaluation.

Exercise 11.2.1.   Generalize `hellos` to `repeat`, which consumes a natural number `n` and a symbol and produces a list with `n` occurrences of the symbol. Solution

Exercise 11.2.2.   Develop the function `tabulate-f`, which tabulates the values of

```;; `f : number  ->  number`
(define (f x)
(+ (* 3 (* x x))
(+ (* -6 x)
-1)))
```

for some natural numbers. Specifically, it consumes a natural number `n` and produces a list of `n` `posn`s. The first one combines `n` with `(f n)`, the second one `n-1` with `(f n-1)`, etc. Solution

Exercise 11.2.3.   Develop `apply-n`. The function consumes a natural number, `n`. It applies the function `move` from exercise 10.3.6 `n` times to `FACE`, the list of shapes from exercise 10.3.1. Each application should translate the shape by one pixel. The purpose of the function is to simulate a continuously moving shape on a canvas, the last missing piece of the extended exercise 10.3. Solution

Exercise 11.2.4.   Lists may contain lists that contain lists and so on. Here is a data definition that takes this idea to an extreme:

A deep-list is either

1. `s` where `s` is some symbol or

2. `(cons dl empty)`, where `dl` is a deep list.

Develop the function `depth`, which consumes a deep list and determines how many times `cons` was used to construct it.

Develop the function `make-deep`, which consumes a symbol `s` and a natural number and produces a deep list containing `s` and `cons`tructed with `n` `cons`es. Solution

## 11.3  Extended Exercise: Creating Lists, Testing Functions

We often encounter situations where we would like to create lists of data that involve numbers. For example, we may wish to create large lists of numbers to test a function like `extract1` in section 10.2 on large lists instead of hand-coded small ones. Sometimes we would like to visualize randomly picked data. We can create such functions using recursion on natural numbers and a random number generator.

Exercise 11.3.1.   Scheme provides the operation `random`. It consumes a natural number `n` greater than 1, and produces a random integer between `0` and `n - 1`:

```;; `random :  N  ->  N`
;; to compute a natural number between `0` and `n-1`
(define (random n) ...)
```

Two successive uses of `(random n)` may produce two distinct results.

Now consider the following definition:

```;; `random-n-m : integer integer  ->  integer`
;; ...
;; Assume: n < m
(define (random-n-m n m)
(+ (random (- m n)) n))
```

Formulate a succinct and precise purpose statement for `random-n-m`. Use a number line with an interval to explain the result of ```(random n)```. Use a symbolic evaluation to support your explanation. Solution

Exercise 11.3.2.   Develop the function `tie-dyed`. It consumes a natural number and produces a list of that many numbers, each randomly chosen in the range from `20` and `120`. Use `tie-dyed` to apply `draw-circles` from exercise 9.5.8. Solution

Exercise 11.3.3.   Develop the function `create-temps`. It consumes a natural number `n` and two integers, called `low` and `high`. It produces a list of `n` integers that are between `low` and `high`.

Use `create-temps` to test `check-range` from exercise 9.5.4.

Finally, discuss the following questions. Can we simply feed the result of `create-temps` into `check-range` or do we need to know the list that `create-temps` produced? Are there values for `low` and `high` such that we don't need to know the result of `create-temps` and yet we can predict the result of the test? Which function tests which? What does this tell us about testing with automatically generated test data? Solution

Exercise 11.3.4.   Develop the function `create-prices`, which consumes a natural number and produces a list with a corresponding number of prices between \$.10 and \$10.00 with increments of a dime. Use `create-prices` to test `dollar-store?` from exercise 9.5.3.

Hint: How many dimes are there between \$.10 and \$10.00? Solution

Exercise 11.3.5.   Develop a program that visualizes a student riot. In preparation of a student riot, a small group of students meets to make paint-filled balloons. The typical riot uses `'red` only. Then, on the evening of the riot, the students enter a university's progressive theater with the balloons and throw them all over the seats.

The program's only input should be a natural number, which represents the number of balloons thrown. The visualization should use a canvas that contains a black grid and the positions of the balls: Assume a random distribution of the balls over the theater's seats. Each box in the grid represents a seat. Configure the program so the change of one variable definition changes the number of columns in the grid and a change to another changes the number of rows.

Hint: Develop auxiliary functions that draw some given number of lines in the vertical and the horizontal direction. Solution

## 11.4  Alternative Data Definitions for Natural Numbers

Using the above, standard data definition for natural numbers makes it easy to develop all kinds of functions on numbers. Consider, for example, a function that multiplies the first `n` numbers. Put differently, it consumes a natural number `n` and multiplies all numbers between `0` (exclusive) and `n` (inclusive). The function is called factorial and has the mathematical notation `!`. Its contract is easy to formulate:

```;; `! : N  ->  N`
;; to compute n  ·  (n - 1)  ·  ...  ·  2  ·  1
(define (! n) ...)
```

It consumes a natural number and produces one.

Specifying its input-output relationship is a bit more tricky. We know, of course, what the product of `1`, `2`, and `3` is, so we should have

```(= (! 3)
6)
and, similarly,
(= (! 10)
3628800)
```

The real question is what to do with the input `0`. According to the informal description of the task, `!` is supposed to produce the product of all numbers between `0` (exclusive) and `n` (inclusive), the argument. Since `n` is `0`, this request is rather strange because there are no numbers between `0` (exclusive) and `0` (inclusive). We solve the problem by following mathematical convention and set that `(! 0)` evaluates to `1`.

From here, the rest is straightforward. The template for `!` is clearly that of a natural number processing function:

```(define (! n)
(cond
[(zero? n) ...]
[else ... (! (sub1 n)) ...]))
```

The answer in the first `cond`-clause is given: `1`. In the second clause, the recursion produces the product of the first ```n - 1``` numbers. To get the product of the first `n` numbers, we just need to multiply the (value of the) recursion by `n`. Figure 31 contains the complete definition of `!`.

Exercise 11.4.1.   Determine the value of `(! 2)` by hand and with DrScheme. Also test `!` with `10`, `100`, and `1000`.

Note: The results of these expressions are large numbers, well beyond the native capacities of many other programming languages. Solution

Now suppose we wish to design the function `product-from-20`, which computes the product from `20` (exclusive) to some number `n` (inclusive) that is greater or equal to `20`. We have several choices here. First, we could define a function that computes `(! n)` and `(! 20)` and divides the former by the latter. A simple mathematical argument shows that this approach indeed yields the product of all numbers between `20` (exclusive) and `n` (inclusive): Exercise 11.4.2.   Use the idea to define `product`, a function that consumes two natural numbers, `n` and `m`, with `m > n`, and that produces the product of the numbers between `n` (exclusive) and `m` (inclusive). Solution

Second, we can follow our design recipe, starting with a precise characterization of the function's input. Obviously, the inputs belong to the natural numbers, but we know more than that. It belongs to the following collection of numbers: `20`, `21`, `22`, .... By now we know how to describe such a set precisely with a data definition:

A natural number `[>= 20]` is either

1. `20` or

2. `(add1 n)` if `n` is a natural number `[>= 20]`.

Notation: In contracts, we use `N [>= 20]` instead of ``natural numbers `[>= 20]`.''

Using the new data definition, we can formulate a contract for `product-from-20`:

```;; `product-from-20: N [>= 20]  ->  N`
;; to compute n  ·  (n - 1)  ·  ...  ·  21  ·  1
(define (product-from-20 n-above-20) ...)
```

Here is a first example for `product-from-20`'s input-output specification:

```(= (product-from-20 21)
21)
```

Since the function multiplies all numbers between `20` (exclusively) and its input, `(product-from-20 21)` must produce `21`, which is the only number in the interval. Similarly,

```(= (product-from-20 22)
462)
```

for the same reason. Finally, we again follow mathematical convention and agree that

```(= (product-from-20 20)
1)
```

The template for `product-from-20` is a straightforward adaptation of the template for `!`, or any natural number-processing function:

```(define (product-from-20 n-above-20)
(cond
[(= n-above-20 20) ...]
[else ... (product-from-20 (sub1 n-above-20)) ...]))
```

The input `n-above-20` is either `20` or larger. If it is `20`, it does not have any components according to the data definition. Otherwise, it is the result of adding `1` to a natural number `[>= 20]`, and we can recover this ``component'' by subtracting `1`. The value of this selector expression belongs to the same class of data as the input and is thus a candidate for natural recursion.

Completing the template is equally straightforward. As specified, the result of `(product-from-20 20)` is `1`, which determines the answer for the first `cond`-clause. Otherwise, `(product-from-20 (sub1 n-above-20))` already produces the product of all the numbers between `20` (exclusive) and ```n-above-20 - 1```. The only number not included in this range is `n-above-20`. Hence ```(* n-above-20 (product-from-20 (sub1 n-above-20)))``` is the correct answer in the second clause. Figure 31 contains the complete definition of `product-from-20`.

Exercise 11.4.3.   Develop `product-from-minus-11`. The function consumes an integer `n` greater or equal to `-11` and produces the product of all the integers between `-11` (exclusive) and `n` (inclusive). Solution

Exercise 11.4.4.   In exercise 11.2.2, we developed a function that tabulates some mathematical function `f` for an interval of the shape (0,n].

Develop the function `tabulate-f20`, which tabulates the values of `f` for natural numbers greater than `20`. Specifically, the function consumes a natural number `n` greater or equal to `20` and produces a list of `posn`s, each of which has the shape `(make-posn n (f n))` for some `n` between `20` (exclusive) and `n` (inclusive). Solution

 ```;; `! : N  ->  N` ;; to compute n · (n - 1) · ... · 2 · 1 (define (! n) (cond [(zero? n) 1] [else (* n (! (sub1 n)))])) ;; `product-from-20: N [>= 20]  ->  N` ;; to compute n · (n - 1) · ... · 21 · 1 (define (product-from-20 n-above-20) (cond [(= n-above-20 20) 1] [else (* n-above-20 (product-from-20 (sub1 n-above-20)))])) ;; `product: N[limit] N[>= limit]  ->  N` ;; to compute n · (n - 1) · ... · (limit + 1) · 1 (define (product limit n) (cond [(= n limit) 1] [else (* n (product limit (sub1 n)))])) ``` Figure 31:  Computing factorial, product-from-20, and product

A comparison of `!` and `product-from-20` suggests the natural question of how to design a function that multiplies all natural numbers in some range. Roughly speaking, `product` is like `product-from-20` except that the limit is not a part of the function definition. Instead, it is another input, which suggests the following contract:

```;; `product: N N  ->  N`
;;  to compute n  ·  (n - 1)  ·  ...  ·  (limit + 1)  ·  1
(define (product limit n) ...)
```

The intention is that `product`, like `product-from-20`, computes the product from `limit` (exclusive) to some number `n` (inclusive) that is greater or equal to `limit`.

Unfortunately, `product`'s contract, in contrast with `product-from-20`'s, is rather imprecise. In particular, it does not describe the collection of numbers that `product` consumes as the second input. Given its first input, `limit`, we know that the second input belongs to `limit`, `(add1 limit)`, `(add1 (add1 limit))`, etc. While it is easy to enumerate the possible second inputs, it also shows that the description of the collection depends on the first input -- an unusal situation that we have not encountered before.

Still, if we assume limit is some number, the data description for the second input is nearly obvious:

Let `limit` be a natural number. A natural number `[>= limit]` (`N[>=limit]`) is either

1. `limit` or

2. `(add1 n)` if `n` is a natural number `[>= limit]`.

In other words, the data definition is like that for natural numbers `[>= limit]` with `20` replaced by a variable `limit`. Of course, in high school, we refer to `N[>=0]` as the natural numbers, and `N[>=1]` as the positive integers.

With this new data definition, we specify the contract for `product` as follows:

```;; `product: N[limit] N [>= limit]  ->  N`
;;  to compute n  ·  (n - 1)  ·  ...  ·  (limit + 1)  ·  1
(define (product limit n) ...)
```

That is, we name the first input, a natural number, with the notation `[limit]` and specify the second input using the name for the first one.

The rest of the program development is straightforward. It is basically the same as that for `product-from-20` with `20` replaced by `limit` throughout. The only modification concerns the natural recusion in the function template. Since the function consumes a `limit` and a `N [>= limit]`, the template must contain an application of `product` to `limit` and `(sub1 n)`:

```(define (product limit n)
(cond
[(= n limit) ...]
[else ... (product limit (sub1 n)) ...]))
```

Otherwise things remain the same. The full function definition is contained in figure 31.

Exercise 11.4.5.   In exercises 11.2.2 and 11.4.4, we developed functions that tabulate `f` from some natural number or natural number `[>= 20]` down to `0` or `20` (exclusive), respectively.

Develop the function `tabulate-f-lim`, which tabulates the values of `f` in an analogous manner from some natural number `n` down to some other natural number `limit`. Solution

Exercise 11.4.6.   In exercises 11.2.2, 11.4.4, and 11.4.5, we developed functions that tabulate the mathematical function `f` in various ranges. In both cases, the final function produced a list of `posn`s that was ordered in descending order. That is, an expression like `(tabulate-f 3)` yields the list

```(cons (make-posn 3 2.4)
(cons (make-posn 2 3.4)
(cons (make-posn 1 3.6)
(cons (make-posn 0 3.0)
empty))))
```

If we prefer a list of `posn`s in ascending order, we must look at a different data collection, natural numbers up to a certain point in the chain:

A natural number `[<= 20]` (`N[<=20]`) is either

1. `20` or

2. `(sub1 n)` if `n` is a natural number `[<= 20]`.

Of course, in high school, we refer to `N[<=-1]` as the negative integers.

Develop the function

```;; `tabulate-f-up-to-20 : N [<= 20]  ->  N`
(define (tabulate-f-up-to-20 n-below-20) ...)
```

which tabulates the values of `f` for natural numbers less than `20`. Specifically, it consumes a natural number `n` less than or equal to `20` and produces a list of `posn`s, each of which has the shape `(make-posn n (f n))` for some `n` between `0` and `n` (inclusively). Solution

Exercise 11.4.7.   Develop the function `is-not-divisible-by<=i`. It consumes a natural number `[>= 1]`, `i`, and a natural number `m`, with `i < m`. If `m` is not divisible by any number between `1` (exclusive) and `i` (inclusive), the function produces `true`; otherwise, its output is `false`.

Use `is-not-divisible-by<=i` to define `prime?`, which consumes a natural number and determines whether or not it is prime. Solution

## 11.5  More on the Nature of Natural Numbers

The natural numbers are a small subset of Scheme's numbers, not all of them. Hence the function template above cannot be used for processing arbitrary numbers, in particular, inexact numbers. Still, the template is a good starting point for functions whose definitions involve both natural numbers and other Scheme numbers. To illustrate this point, let us design the function `add-to-pi`, which consumes a natural number `n` and produces `n + 3.14` without using `+`.

```;; `add-to-pi : N  ->  number`
;; to compute n + 3.14 without using `+`
```

Another easy step is to determine the output for a few sample inputs:

```(= (add-to-pi 0) 3.14)
```

The difference between `hellos`'s contract (see exercise 11.2.1) and that of `add-to-pi` is the output, but as we have seen this does not affect the template design. We obtain the template for `add-to-pi` by renaming `hellos` appropriately:

```(define (add-to-pi n)
(cond
[(zero? n) ...]
[else ... (add-to-pi (sub1 n)) ... ])))
```

In combination with the examples, the template immediately suggests how to complete the function. If the input is `0`, `add-to-pi`'s answer is `3.14`. Otherwise, `(add-to-pi (sub1 n))` produces `(- n 1) + 3.14`; since the correct answer is `1` more than this value, the answer expression in the second `cond`-line is `(add1 (add-to-pi (sub1 n)))`. Figure 32 contains the complete function definition.

Exercise 11.5.1.   Define `add`, which consumes two natural numbers, `n` and `x`, and produces `n + x` without using Scheme's `+`. Solution

Exercise 11.5.2.   Develop the function `multiply-by-pi`, which consumes a natural number and multiplies it by `3.14` without using `*`. For example,

```(= (multiply-by-pi 0) 0)
(= (multiply-by-pi 2) 6.28)
(= (multiply-by-pi 3) 9.42)
```

Define `multiply`, which consumes two natural numbers, `n` and `x`, and produces `n * x` without using Scheme's `*`. Eliminate `+` from this definition, too.

Hint: Recall that multiplying `x` by `n` means adding `x` to itself `n` times. Solution

Exercise 11.5.3.   Develop the function `exponent`, which consumes a natural number `n` and a number `x` and computes Eliminate `*` from this definition, too.

Hint: Recall that exponentiating `x` by `n` means multiplying `x` with itself `n` times. Solution

Exercise 11.5.4.   Deep lists (see exercise 11.2.4) are another representation for natural numbers. Show how to represent `0`, `3`, and `8`.

Develop the function `addDL`, which consumes two deep lists, representing the natural numbers `n` and `m`, and produces a deep list representing `n + m`. Solution

 ```;; `add-to-pi : N  ->  number` ;; to compute n + 3.14 without using `+` (define (add-to-pi n) (cond [(zero? n) 3.14] [else (add1 (add-to-pi (sub1 n)))])) ``` Figure 32:  Adding a natural number to pi

34 It is important to start counting at 0 so that we can use the natural numbers for counting the number of items on a list or the members of a family tree.

35 For that, we need to defer to a course on mathematical sets.