Introductory Programming in Java

Range of Type Values, References, use of API

The Problem

The bunch of non-negative integer numbers written in a shape of the triangle:

is called the Euler–Bernoulli triangle and can be constructed using the following algorithm:

1. the triangle is constructed row by row from the top down; the rows are indexed starting from zero (like elements in an array)
2. the zeroth (top-most) row consists of the only element 1
3. the first row comprises 0 and 1
4. the second row begins from the right — put 0 and move to the left; at every step, we take the sum of the preceding number in the same row and the preceding number in the row above, ie, the sum of the nearest right and upper right numbers
5. the third row starts at the left — put 0 and move to the right; at every step, we take the sum of the nearest left and upper left numbers
6. all rows are constructed in the same way — every even indexed row begins on the right with 0 and is built right-to-left, and every odd indexed row begins on the left with 0 and is built left-to-right

The importance of this construction lies in the fact, that all non-zero numbers on the left side of the triangle represent the so-called Euler numbers, while all non-zero numbers on the right side are the so-called Bernoulli numbers. Both are important sequences in mathematics, and the described triangle gives the simplest algorithm to calculate them.

Your task is to write a program which will calculate the first n rows of the Euler–Bernoulli triangle. You may use a two-dimensional integer array, and your program will assign its elements values according to the above algorithm. Do not write code which will print the triangle as it’s done above (there are formatting problems when the numbers become multi-digit). However, using the constructed array, make your code to print all Euler and Bernoulli numbers contained in the calculated triangle…

The solution, which uses a two-dimensional integer array of longs, is provided to you at the start: EulerBernoulliTriangle.java. Download it and study. Compile and run it. It should be done as follows:

% java EulerBernoulliTriangle 21

where the command line argument, 21 in the above example, must be an odd positive number greater than 2. The output will look as follows:

% java EulerBernoulliTriangle 21             
The height of the triangle is 21
The Euler numbers:
1
1
5
61
1385
50521
2702765
199360981
19391512145
2404879675441
That's 10 Euler numbers

The Bernoulli numbers:
1
1
2
16
272
7936
353792
22368256
1903757312
209865342976
That's 10 Bernoulli numbers

However, attempts to calculate larger Euler and Bernoulli (EB) numbers soon run into a problem: if you use the value of command line argument 27 and higher, you will see that the EB stop growing and even become negative (which shouldn’t happen – check the algorithm for their calculation). This is the consequence of the finite range of the long primitive type which is used in the program.

Your task is to modify the above program so it can calculate the EB numbers of arbitrary order. You should replace the long type onto a different one (which?!) and make appropriate changes in other places of the code.

Test the correctness of your output by comparing it with the Euler numbers from the picture:

Hint: look up the Java API docs, the package java.math.

Assessment

You will get up to two marks, if you present a solution to the Homework exercise during the next week lab.