Module 5: Integers

Next, we'll look at some well-known patterns in numbers, which will give us practice with problem-solving.

The first one is Fibonacci numbers.

• The Fibonacci sequence is this:
         0, 1, 1, 2, 3, 5, 8, 13, ...

• Thus, the next Fibonacci number is the sum of the previous two.

• Fibonacci numbers have proven useful in modeling biological growth, and have interesting mathematical properties.

  5.25 Exercise: Take a short browser break to read about Fibonacci, to appreciate his seminal contributions to mathematics.

• Let's now write a program to print Fibonacci numbers.

• Observe: to compute a single Fibonacci number
         ⇒ We'll need a variable for it.

  

• To compute this, we'll need variables for the previous two:

  

• Let's start with some pseudocode:

         N = 10                 // We'll go up the N-th Fibonacci #
         p = 1                  // Initial value of p
         q = 0                  // Initial value of q
         for i=3 to N {
            Make the i-th Fibonacci number
            Print it
            Update p and q
         }
      

• We're going to resist the temptation to code, and instead refine the pseudocode:

         N = 10                 // We'll go up the N-th Fibonacci #
         p = 1                  // Initial value of p
         q = 0                  // Initial value of q
         for i=3 to N {
            f = p + q
            Print f
            q = p
            p = f
         }
      

• Now, finally, let's write this up as a Java program:

  

5.26 Exercise: Trace the changing values of q, p, and f in the above program using a table.

5.27 Video:

The second "number" idea we'll explore: a program to explore a famous mathematical proof

• This is a well-known formula:

       1 + 2 + ... + n   =   n(n+1)/2
      

• There is a rather simple proof of this, attributed to the mathematician Carl Gauss.

• What's interesting: Gauss was reportedly 10 years old when he discovered this proof.

• The main idea:
  • First, write the numbers 1 to n:

    

  • Then, reverse the order and line up the reversed order underneath:

    

  • Then, add:

    

  • Since the original sum is double-counted here, it must be true that

         1 + 2 + ... + n   =   n(n+1)/2
        

• Now, let's explore this in a program:
  • We'll compute the sum in two different ways:
    1. The sum as we've already computed before:
              ⇒ Remember s = s + i?
    2. Gauss' method.

  • We'll use the variable s for the first approach.

  • And d for the second approach.

  • Recall: d will have twice the sum.

  public class Gauss {
  
      public static void main (String[] argv)
      {
  	int n = 10;
  	int s = 0;                  // Use this to accumulate the sum.
  	int d = 0;                  // Use this to accumulate the double-sum.
  
  	for (int i=1; i<=n; i++) {
  	    int a = i;              // The number in the row above.
  	    int b = n-i+1;          // The number in the row below.
  	    d = d + (a + b);        // Accumulate the two terms: (n+1)
  
  	    s = s + i;              // Accumulate the sum in the usual (first) way.
  	}
  
  	System.out.println (s);     // Print the sum.
  	System.out.println (d/2);  // Print the double-sum divded by 2.
  
  	int f = n*(n+1)/2;
  	System.out.println (f);     // To verify, print the formula.
      }
  
  }
      

5.28 Exercise: Write the above program in Gauss.java and verify.

5.29 Exercise: Take a short browser break to read about Gauss, considered one of the greatest mathematicians of all time.

A problem with variables and nested for-loops

      sum = sum + i;
    

      sum += i;
    

       s -= i;         // Same as s = s - i;
       p *= 2;         // Same as p = p * 2;
       d /= 2;         // Same as d = d / 2;