Date: Tue, 28 Aug 2007 16:15:08 -0500 (CDT) From: Mark Jacobson To: 810-080-02-FALL@uni.edu Subject: Josephus Problem formula -------------------------------------------------------------------------- You are NOT expected to understand the following material until early September, so don't worry if you don't understand it. It will be much clearer after Thursday's wrap up of the Josephus problem. -------------------------------------------------------------------------- Hi Discrete students, I will put this email note on the web page for your convenience. See: http://cns2.uni.edu/~jacobson/c080.html Recall that the floor of any number is the largest integer that is greater than or equal to it. 4 The log (16) = 4 since 2 = 16 2 5 The log (32) = 5 since 2 = 32 2 Here are the log to the base 2 values for the numbers 1 through 32. 1 0 2 1 3 1.584962501 Using Microsoft Excel to get the log2() values... 4 2 5 2.321928095 floor(2.321928095) = 2 6 2.584962501 7 2.807354922 8 3 integers 8 through 15 all have log2 = 3.something 9 3.169925001 10 3.321928095 11 3.459431619 12 3.584962501 13 3.700439718 floor(3.700439718) = 3 14 3.807354922 15 3.906890596 16 4 integers 16 through 31 all of log2 = 4.something 17 4.087462841 18 4.169925001 19 4.247927513 20 4.321928095 21 4.392317423 22 4.459431619 23 4.523561956 24 4.584962501 floor(4.584962501) = 4 25 4.64385619 26 4.700439718 27 4.754887502 28 4.807354922 29 4.857980995 30 4.906890596 31 4.95419631 32 5 ------------------------------------------------------------------------------ Here are solutions for the Josephus Problem from 2 person up to 40 persons. ------------------------------------------------------------------------------ without multiplied by add 1 n binary 1st digit 2 (doubled) to doubled number - ------ --------- -------------- ----- 2 10 0 00 0 1 3 11 1 10 2 3 4 100 00 000 0 1 5 101 01 010 2 3 6 110 10 100 4 5 The last column 7 111 11 110 6 7 is the solution, is 8 1000 000 0000 0 1 where to stand to be 9 1001 001 0010 2 3 the "winner" and the 10 1010 010 0100 4 5 last person standing 11 1011 011 0110 6 7 for the group of n 12 1100 100 1000 8 9 people where we 13 1101 101 1010 10 11 eliminate every 14 1110 110 1100 12 13 2nd person. 15 1111 111 1110 14 15 16 10000 0000 00000 0 1 Why the binary method 17 10001 0001 00010 2 3 works should be clear 18 10010 0010 00100 4 5 after Thursday's 19 10011 0011 00110 6 7 class. 20 10100 0100 01000 8 9 21 10101 0101 01010 10 11 Be sure to look at the 22 10110 0110 01100 12 13 log values of the numbers 23 10111 0111 01110 14 15 too. 24 11000 1000 10000 16 17 25 11001 1001 10010 18 19 26 11010 1010 10100 20 21 The log (110111) is 5.x 27 11011 1011 10110 22 23 2 28 11100 1100 11000 24 25 29 11101 1101 11010 26 27 110111 with digit positions 30 11110 1110 11100 28 29 numbered looks like 31 11111 1111 11110 30 31 this: 32 100000 00000 000000 0 1 33 100001 00001 000010 2 3 110111 34 100010 00010 000100 4 5 543210 35 100011 00011 000110 6 7 36 100100 00100 001000 8 9 log (110000111) is 8 37 100101 00101 001010 10 11 2 38 100110 00110 001100 12 13 110000111 39 100111 00111 001110 14 15 876543210 40 101000 01000 010000 16 17 8 - ------ --------- -------------- ----- 2 = 100000000 without multiplied by add 1 n binary 1st digit 2 (doubled) to doubled number - ------ --------- -------------- ----- See: http://cns2.uni.edu/~jacobson/c080.html You are NOT expected to understand the above material until early September, so don't worry if you don't understand it. It will be clearer after Thursday's wrap up of the Josephus problem. Mark