created 02/22/2018

# Chapter 86 Programming Exercises

Instructions: Write each of these programs as specified.

## Exercise 1 — Warm-up

Write a program that asks the user for N and adds up the integers between 1 and N. Print out the result. Do this in a loop.

Then, use the formula

```SUM (1 to N) = N*(N+1)/2
```

to compute the same thing. Print out that result. Hopefully your results are the same for both methods.

```? java Exercise01
N  : 1000
Series  Sum: 500500
Formula Sum: 500500

? java Exercise01
N  : 1000000000
Series  Sum: 500000000500000000
Formula Sum: 500000000500000000

? java Exercise01
N  : rats
```

## Exercise 2 — Add up Integers in a Range

Write a program that asks the user for N and M and adds up the integers between N and M (inclusive). Print out the result. Do this in a loop.

Then, use the formula

```SUM(N to M) = SUM( 1 to M ) - SUM( 1 to N-1 )
```

to compute the same thing. Print out that result. Hopefully your results are the same for both methods.

```? java Exercise02
M (start): 10
N (end)  : 100
Series  Sum: 5005
Formula Sum: 5005

? java Exercise02
M (start): 1000
N (end)  : 2000
Series  Sum: 1501500
Formula Sum: 1501500

? java Exercise02
M (start): 10000000
N (end)  : 23000000
Series  Sum: 214500016500000
Formula Sum: 214500016500000

? java Exercise02
M (start): -1000
N (end)  : 1000
Series  Sum: 0
Formula Sum: 0
```

## Exercise 3 — Sum of Odds

Write a program that asks the user for N and adds up the first N odd integers. Print out the result. Do this in a loop. Use the fact that the N'th odd number is `2*N + 1`

Then, write out `N2` and compare the two results.

## Exercise 4 — Factorial and Combinations

N factorial is the product of all integers 1 through N. Usually it is written `N!` Factorial of zero is one, by definition: `0! = 1`. Pseudo-code:

```set fact = 1
for j from 1 to N
fact = fact * j
```

`N!` quickly gets very big. A rule-of-thumb: never compute `N!`. Even if a formula is written with `N!` there is usually a way to avoid computing it directly.

Write a program that prompts the user for an N and then writes out `N!` computed with data type `long` and then computed with `BigInteger`s. Notice that the `long` overflows quickly and gives no indication that this has happened.

Write both factorial functions as static methods of your class. The `long` version should accept a `long` argument and return a `long` value. The `BigInteger` version should accept a reference to a `BigInteger` and an argument and return a `BigInteger` reference.

```? java Exercise04
N  : 10
Long Factorial: 3628800
Big  Factorial: 3628800

? java Exercise04
N  : 20
Long Factorial: 2432902008176640000
Big  Factorial: 2432902008176640000

? java Exercise04
N  : 21
Long Factorial: -4249290049419214848
Big  Factorial: 51090942171709440000
```

Once the above is working, modify the program so that it includes a static method that computes combinations of N things taken R at a time. The main method should prompt the user for N and R. Usually the formula is written

```NCR = N!/(R!*(N-R!))
```

The rule-of-thumb says to not compute the three factorials but to do cancellation between numerator and denominator to simplify the calculation. In the formula (as given) there are N integers in the numerator and N integers in the denominator. For example, with 10C6:

```10 9 8 7 6 5 4 3 2 1
--------------------
4 3 2 1 6 5 4 3 2 1
```

Find whichever of R or (N-R) is larger. Calculate the numerator in a loop that starts at max+1. Calculate the denominator in a loop that goes up to N-max.

```? java Exercise04
N  : 10
R  : 6
10 things taken 6 at a time = 210

? java Exercise04
N  : 37
R  : 10
37 things taken 10 at a time = 348330136

? java Exercise04
N  : 55
R  : 20
55 things taken 20 at a time = 505037289962205

? java Exercise04
N  : 789
R  : 1
789 things taken 1 at a time = 789
?
```

## Exercise 5 — Fibonacci

If factorial is here, can Fibonacci be far behind? Like factorial, the Fibonacci sequence grows rapidly. It is a sequence of integers that starts out as

```1, 1
```

The next term in the series is the sum of the previous two:

```1, 1, 2
```

This keeps going as long as you want:

```1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
```

The rule for the N'th term of the sequence is is:

```Fib( 1 ) = 1
Fib( 2 ) = 1
Fib( N ) = Fib( N-2 ) + Fib( N-1 )
```

Write a program that asks the user for N and prints out the N'th term of the series.

```? java Exercise05
N  : 10
Fibonacci = 55

? java Exercise05
N  : 20
Fibonacci = 6765

? java Exercise05
N  : 100
Fibonacci = 354224848179261915075
```

N can be a `long` and the counting loop that calculates the terms can be an ordinary `for` loop that counts up to N. It is unlikely that anyone will want to calculate Fibonacci for an N that takes a `BigInteger` to express. This is similar to the `pow()` method, that takes an `int` argument for the same reason.

If you compute this recursively, it will be very much slower and your program will likely run out of memory:

## Exercise 6 — Prime Improvement

Make the two improvements to the prime number detection method of the chapter:

```  public static Boolean isPrime( BigInteger N )
{
BigInteger trial;

trial = new BigInteger( "2" );
while ( trial.compareTo( N ) < 0 )
{
if ( N.mod(trial).equals( BigInteger.ZERO ) )
return false;
}
return true;
}
```

1. If `N` is even, immediately return false. Otherwise, there is no need to test if any multiple of two divides the number. So, after testing if the number is even, start the trial divisor at three and increment by two each iteration.

2. Trial divisors need not be any larger than the square root of the number, since if the number equals the product `N*M`, one of `N` or `M` must be equal or smaller than the square root.

To implement this, you don't need to calculate the square root of `N`. The loop generates a sequence of trial divisors. As soon as the square of the current trial divisor exceeds the suspected prime, end the loop.

## Exercise 7 — Greatest Common Divisor, GCD

Write a program that asks the user for `M` and `N` and computes their gcd. The integers might be very large, so use `BigInteger`

The greatest common divisor of two positive integers is the largest integer that divides them both with no remainder. For example,

```gcd( 25, 15 ) == 5, because 5 is the largest integer that divides both 25 and 15

gcd( 36, 24 ) == 12

gcd( 21, 10 ) == 1, because 1 is the only divisor 21 and 10 have in common

gcd( 28, 7 ) == 7

gcd( N, 0 ) == N, because  N divides N and N also divides 0 (with result 0)
```

To calculate the gcd( M, N ) do this:

```while M not equal N
{
if M > N
M = M - n
else
N = N - M
}
return M
```

For example, say M=36 and N=24

```M=36 not equal N=24
M = 26-24 = 12

M=12 not equal N=24
N = 24 - 12 = 12

M and N are equal, gcd = 12
```

Write a program that asks the user for `M` and `N` and computes their gcd. (There is a faster algorithm for computing the gcd.)

The class `BigInteger` has a `gcd( BigInteger N)` method. Use this in your program to see if your code is working.