Elementary Number Theory with Programming

3PASCAL’S TRIANGLE

In this chapter, we discuss Pascal’s triangle and explain the relevance of its entries to number theory.

FACTORIALS

As you are probably aware, n!, or n factorial, is the product of the first n positive integers, that is,

We define 0! to be 1. There are n! permutations of n distinct objects.

There are two ways (at least) of programming factorial. One uses the definition: factorial of n is the product of the first n integers. This is called the iterative way. It is not too unsurprising that this is coded using a for-loop, going from 1 to n. The exact coding is

var ans = 1;
  for (var j=1;j<(n+1);j++){
 ans *= j;
 }

The second way uses recursion. The informal definition of a recursion function is one that calls itself. (A critical concept in theoretical computer science is that the recursive functions are the set of functions obtained when starting with a small set of functions and allowing certain function making procedures including composition and finding the inverse. One of the function making procedures is termed primitive recursion.) Using recursion, factorial is

• If n ≤ 1, factorial(n) is 1
• Otherwise, factorial(n) is n*factorial(n − 1)

(This definition is written in what is termed pseudocode, a combination of coding and English.)

This definition can be used as the basis of a program. This may be surprising and the technique can be misused. The ...