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