Exercises - Review of Java Basics

Let $f(x)$ be defined for a given integer $x$ as the number resulting from removing any right-most even digits $x$ might have until either an odd digit is encountered or only a single digit remains. For a given sequence of integers $\{ x_0, x_1, x_2, \ldots, x_n \}$, we wish to find the sum $$\sum_{i=0}^n f(x_{n-i})$$ Towards this end, write a class StrangeSum that when run, prompts the user to enter some sequence of integers separated by spaces, and then prints the summation sought, first as an expanded sum of the corresponding $f$ values, and then as the simplified total. These two expressions should be separated by an equals sign, as shown in the sample run below.

Importantly, note that the subscript of $(n-i)$ in the summation above means that the order in which the $f$ values should be shown in the first expression should agree with applying $f$ to the numbers entered in reverse order.

Here's a sample run:

$ java StrangeSum↵
Enter two or more integers to add, separated by spaces
2 3 40 52 682 794 900↵
9+79+6+5+4+3+2=108

In 1963, mathematician Stanislaw Ulam (who notably solved the problem of how to initiate fusion in a hydrogen bomb and also devised the "Monte-Carlo" method which is often used to solve problems in statistics) noticed that when writing consecutive positive integers in a spiral arrangement on a rectangular grid, primes appeared to congregate along clearly visible diagonal lines.

Strikingly, when one starts with $41$ at the center, an unbroken string of $40$ primes fall on the main diagonal (from the position of $1523$, through that of $41$, and extending to the position of $1601$). This is the longest known unbroken string of primes on a diagonal of such a spiral.

Create a tool to investigate what Ulam discovered. Write a class PrimeSpiral that when run, prompts the user to enter a positive integer $n$ and an odd number $m$. Then, the class should print an $m \times m$ grid of tab-delimited values from $n$ to $m^2+n-1$ that follow a rectangular spiral starting with $n$ in the center-most position of the grid, with $(n+1)$ is to the immediate right of this value, and with subsequent consecutive values spiraling counterclockwise, as suggested by the sample run below.

For easy identification, print an asterisk immediately following every prime number in the grid. For those that might have forgotten, the value $1$ is not prime.

Here's a sample run that allows us to see a portion of the primes on Ulam's spiral (starting at $41$):

$ java PrimeSpiral↵
Enter a positive starting number and an odd number of rows/columns, separated by a space:
41 11↵
141	140	139*	138	137*	136	135	134	133	132	131*	
142	105	104	103*	102	101*	100	99	98	97*	130	
143	106	77	76	75	74	73*	72	71*	96	129	
144	107*	78	57	56	55	54	53*	70	95	128	
145	108	79*	58	45	44	43*	52	69	94	127*	
146	109*	80	59*	46	41*	42	51	68	93	126	
147	110	81	60	47*	48	49	50	67*	92	125	
148	111	82	61*	62	63	64	65	66	91	124	
149*	112	83*	84	85	86	87	88	89*	90	123	
150	113*	114	115	116	117	118	119	120	121	122	
151*	152	153	154	155	156	157*	158	159	160	161

You must include (and use) two methods in the PrimeSpiral class:

isPrime(int num) which returns true when num is prime, and false when it is not.
numAt(int row, int col, int n, int m) which returns the number that should be displayed in the specified row and column for a spiral that starts at $n$ and consists of $m^2$ values arranged as indicated earlier.

Traditionally, we write integer values using the decimal system, where each digit stands for a multiple of a power of $10$, which is the number of different digit symbols available to us (i.e., $0$ through $9$). We generally call this number of digits available to us the "base", or sometimes the "radix" (the Latin word for "root", and thus a synonym in this sense). As the power of the base $10$ associated with a given digit depends upon the position of the digit in the number in question, we say the decimal system a positional numeral system.

The choice of $10$ as our base and number of digits clearly stems from our having ten fingers and ten toes ("finger or toe" translates to the Latin digitus, after all). Had spiders developed mathematics instead of humans and given the number of legs they have, they might have adopted a "base $8$" system instead (using only digits $0$ to $7$, and powers of $8$) -- and everything would have still worked out just fine. In fact, the base can be chosen to be any integer from $2$ to infinity -- each will lead to an effective way to denote integers. In computer science, base $2$ (binary) and base $16$ (hexadecimal) are particularly important. Indeed, one might find it valuable to know that Java has built-in support for converting from one base to another. The interested reader can consult the Java API regarding the methods parseInt(String s, int radix) and toString(int i, int radix) in the Integer class to learn more.

There are other less familiar systems for denoting integers, however -- many of which are not supported in any standard Java libraries. One of these is called factoradic notation. The name here merges the words "factorial" and "radix", given that it is a positional numeral system where we add multiplies of factorials (instead of powers), with the coefficients on these factorials written in base/radix $10$.

More specifically, a number written in factoradic form typically appears as a sequence of base $10$ values separated by colons, such as $$3\!:\!4\!:\!1\!:\!0\!:\!1\!:\!0$$ To find the integer value associated with the factoradic form, we multiply each value between colons from left to right by decreasing factorials, down to $0!$ (much like in base $10$ we multiply the digits left to right by decreasing powers of $10$, down to $10^0$) and then sum the resulting products together, as the example below demonstrates: $$\begin{array}{rcl} 3\!:\!4\!:\!1\!:\!0\!:\!1\!:\!0 &=& 3 \cdot 5! + 4 \cdot 4! + 1 \cdot 3! + 0 \cdot 2! + 1 \cdot 1! + 0 \cdot 0!\\ &=& ((((3 \cdot 5 + 4)\cdot 4 + 1)\cdot 3 + 0)\cdot 2 + 1)\cdot 1 + 0\\ &=& 463 \end{array}$$ (Note, the calculation of the equivalent expression seen in the second line above avoids redundant multiplications present in the first, and is thus much more efficient. Make sure to take advantage of this observation in the class you are about to be asked to write.)

Converting from base $10$ back to factoradic form is essentially a reversal of the calculations found in the second line above, as we can see below: $$\begin{array}{rcl} 463 \div 1 &=& 463 \textrm{, remainder } 0\\ 463 \div 2 &=& 231 \textrm{, remainder } 1\\ 231 \div 3 &=& 77 \textrm{, remainder } 0\\ 77 \div 4 &=& 19 \textrm{, remainder } 1\\ 19 \div 5 &=& 3 \textrm{, remainder } 4\\ 3 \div 6 &=& 0 \textrm{, remainder } 3\\ \end{array}$$ One should stop dividing when the quotient found is $0$, and then read the remainders backwards to find the factoradic form. Interestingly, note that the first remainder (upon dividing by $1$) must always be zero -- so all factoradic numbers end in $0$.

In keeping with our earlier remark about the coefficients on the factorials, one should note that as the number we divide by at each step grows without bound. As such, it is possible that some of the remainders encountered will require more than one digit when expressed in base/radix $10$. Placing colons between the remainder values keeps the value of each coefficient/remainder clear.

With all of the above as preface, suppose we seek to build some support for factoradic numbers in Java. Towards this end, write a class Factoradic that will let users of this class perform basic arithmetic on values in factoradic form with ease. To be more precise, construct the Factoradic class so that it has all of the following features:

There should be two constructors -- one that takes an int which is interpreted as the base $10$ value equivalent to the factoriadic to be constructed, and another that takes a String corresponding to its factoradic form (e.g., "3:4:1:0:1:0" in our earlier example).
The class should override the following methods of the Object class:
- toString() : This method should return the factoradic form as a String
- equals(Object o) : This method should return true if and only if the objects in question are both instances of the Factoradic class and their values agree.
Also include the following instance methods:
- base10Value(), which returns an int equal to the value of the Factoradic object in question
- plus(Factoradic f), which returns a Factoradic object whose value is the sum of invoking Factoradic object's value and the value of f
- times(Factoradic f), which similarly returns a Factoradic object whose value is the product of the invoking Factoradic object's value and the value of f

While it causes some duplication of information stored, an efficient strategy from a calculation standpoint will be to keep two instance variables -- one for the value of the Factoradic object, another for the string that represents its factoradic form.

Do not include a main() method in the Factoradic class. Instead, use the class FactoradicTest.java to ensure your Factoradic class is functioning properly.

A sample run of the FactoradicTest class when everything is functioning properly is shown below:

$ java FactoradicTest↵
Testing the Factoradic class...

f1 = 3:4:1:0:1:0 = 463
f2 = 1:4:1:1:2:0:0 = 1234
f1 + f2 = 2:2:0:2:2:1:0 = 1697
f1 * f2 = 1:5:1:2:3:0:3:2:0:0 = 571342
f1 == f2
f2 != 2:1:2:0
f1 != "463"

Now enter two positive integers a and b separated by a space, 
and with b>a. After which the values from a to b inclusive 
will be listed in both base 10 and factoradic form:
100 105↵
100 = 4:0:2:0:0
101 = 4:0:2:1:0
102 = 4:1:0:0:0
103 = 4:1:0:1:0
104 = 4:1:1:0:0
105 = 4:1:1:1:0