4.3. Josephus Problenm Let e people numbered 1 to stand in a cirele. Starting with person number 1, eliminate every second person untl oaly obe survivor remains? Who would that be? Let J) be that person's mber Jn)s called the Josephus nber. Thus the Josephus problem is the following. Problem: Given a positive integer n oompute the Josephus number Try with a few small integers to observe for instance, that J6)5 and "I(7) 7. The problem of 4xicnputing J(n) can be reduiwd to smaller lBtances of the Silne pn.bletn by 4MM1Ndering whether n is even ot, odd. If n is even, say n = 24, then after the first pa88, exactly half the persons remain, thus reducing the problen input size by hal Hover, notice that tbe itM person in the reduoed problem is really (2i-1)b person in the original problem. Thus we have J(2k)-2J) If n is odd, say2k+1, then the tirst pass eliminates all the people at even positions. Then person 1 is also eliminated leaving k persons. Once again the proble input size is reduced by more than half. And thet person in this reduoed problem with k persons is(21) person in the original problem. Hence we hve, 2k+1)-2) We dewrilb no algorithm for this problem at this point but notice that the approach we suggested bere lis reduce and conquer Test .Compute J(n) for 1,215, using the reductions we obtained isbove when is even and odd. Discern a pattern in the sohutions for the first 15 values of n and prove