Introductory Programming In Java

HW 1

HW 2

HW 3

Homework 2

Big numbers
2D Arrays, classes and API documentation

The problem

This problem was a part of the year 2007 final examination paper.

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

Euler bernoulli Triangle

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

the triangle is constructed row by row from the top down; the rows are indexed starting from zero (like elements in an array)
the zeroth (top-most) row consists of the only element 1
the first row comprises 0 and 1
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
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
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...

Perhaps, this problem was a bit too complex for the exam (so I will not try something equally daunting this time), but this is not what you have to do in this Homework. The thing is that I had not been careful and had given one student a code with my solution. So you can all have it, 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

But 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 long primitive type which I used in my 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:

Euler numbers