The Short Circuit

Mike Morgan's technical journal

Archive for the 'Computer science' Category

Just some hack code I threw together for evalating the Josephus Problem.

The Josephus problem described in Concrete Mathematics can be stated in an equivalent yet family friendly form as follows: n players stand in a circle to play a game of “Josephus tag”. When the game starts, the first player tags the second player, and then the third person tags the fourth, and so on and so forth. When a player is tagged, he is out. After the first round, subsequent rounds ensue until the last survivor, who declares herself the winner.

For a game with n players, which position should one select to ensure survival and hence victory?

This program will spew the order of the players who are out in reverse order, allowing you to analyze the results in an effort to find patterns for the last survivor, the second to the last survivor, and so on. For exmaple, here are the rusults for the Josephus problem with 2 through 9 players. Looking at the n=9 case, player 3 is the winner, while player 7 was the last to be tagged.

Reverse Order Out    2:     1    2
Reverse Order Out    3:     3    1    2
Reverse Order Out    4:     1    3    4    2
Reverse Order Out    5:     3    5    1    4    2
Reverse Order Out    6:     5    1    3    6    4    2
Reverse Order Out    7:     7    3    5    1    6    4    2
Reverse Order Out    8:     1    5    7    3    8    6    4    2
Reverse Order Out    9:     3    7    9    5    1    8    6    4    2

Source code is below the fold. As always, for legal reasons, it is provided as is.

Continue Reading »

My 9 year old son Alexander came up with a couple of closed form solutions to the Joesphus problem.  Really.  If this helps you, please leave a comment, he will enjoy it.

 A discussion of his solution (conjectures) and an attempted proof by me of one of them can be found as the first link in the references.

His main conjecture is:

    J(n)=2(n-2^{\lfloor\log_2 n \rfloor})+1, \mbox{ for } {n} \ge {1}

where

    floor(x)=\lfloor{x}\rfloor

is the largest integer not greater than x.
Continue Reading »

© 2017 The Short Circuit | Entries (RSS) and Comments (RSS) |