Results 1 to 11 of 11

Math Help - Josephus Problem

  1. #1
    Gui
    Gui is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    29

    Josephus Problem

    Hey,

    I'm trying to figure out how to put (the solution to) the Josephus Problem into either an equation of a function of some sort.
    I'm starting Algebra II/10th grade, so although I understand functions I lose track of everything when logs and floors become involved. I'd appreciate if you could please keep answers within my level of knowledge.

    I've read and re-read the wiki article. I undertsna everything up to and including the sentence "This suggests that f(n) is an increasing odd sequence that restarts with f(n) = 1 whenever the index n is a power of 2". When the variables m and l become involved - I no longer understand - what do they even stand for?

    Any help is welcome, please and thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Gui View Post
    Hey,

    I'm trying to figure out how to put (the solution to) the Josephus Problem into either an equation of a function of some sort.
    I'm starting Algebra II/10th grade, so although I understand functions I lose track of everything when logs and floors become involved. I'd appreciate if you could please keep answers within my level of knowledge.

    I've read and re-read the wiki article. I undertsna everything up to and including the sentence "This suggests that f(n) is an increasing odd sequence that restarts with f(n) = 1 whenever the index n is a power of 2". When the variables m and l become involved - I no longer understand - what do they even stand for?

    Any help is welcome, please and thank you!
    I'll use capital L since lowecase looks like a 1.

    m is introduced in order to specify the greatest power of 2 that is less than or equal to n. Then L is simply n - 2^m.

    Table of n and corresponding m

    Code:
    n m
    1 0
    2 1
    3 1
    4 2
    5 2
    6 2
    7 2
    8 3
    9 3
    ...
    All we really care about is L because that's what gives us the answer; m gets effectively discarded.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Gui
    Gui is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    29
    Oh, so f(n) = 2*(n-2^m)+1? Is that correct, for any possible n - including both odd and even numbers? If it is, how do we find that pesky m? I don't think the wiki shows that part, unfortunately.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Gui View Post
    Oh, so f(n) = 2*(n-2^m)+1? Is that correct, for any possible n - including both odd and even numbers?
    Correct.

    Quote Originally Posted by Gui View Post
    If it is, how do we find that pesky m? I don't think the wiki shows that part, unfortunately.
    You mentioned it in your original post... just take the floor of the log base 2 of n. Look up definition of logarithm... if you know what logarithm is then it's obvious.

    Note: If you haven't learned logarithms yet, you have some other options. For example, you can just calculate a bunch of powers of 2 and get m that way. If n is larger you can do things like

    2^10 = 1024

    so 2^20 = 1024^2 = 1048576

    etc.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Gui
    Gui is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    29
    Quote Originally Posted by undefined View Post
    You mentioned it in your original post... just take the floor of the log base 2 of n. Look up definition of logarithm... if you know what logarithm is then it's obvious.
    So would the final equation be (please bare with me, I'm just trying to understand everything and nto skip any steps or get them wrong): f(n) = 2*(n-2^floor(log(n)))+1

    I tried this with n=10 and with the default wolframalpha natural logarithm it returned 13 and on my ti-89 and on wolframalpha using the base 10 logarithm (I've got no idea what natural-vs-base-10 logs mean) it returned 17... so clearly something is wrong in my last equation, because the answer is 5.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Gui View Post
    So would the final equation be (please bare with me, I'm just trying to understand everything and nto skip any steps or get them wrong): f(n) = 2*(n-2^floor(log(n)))+1
    You need logarithm base 2. Change to

    2*(n-2^floor(log(n)/log(2)))+1

    Quote Originally Posted by Gui View Post
    I tried this with n=10 and with the default wolframalpha natural logarithm it returned 13 and on my ti-89 and on wolframalpha using the base 10 logarithm (I've got no idea what natural-vs-base-10 logs mean) it returned 17... so clearly something is wrong in my last equation, because the answer is 5.
    After the modification it will work as expected.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Gui
    Gui is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    29
    It does work as expected - it's perfect! Thank you very much for bearing with me undefined, your help was great!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Gui
    Gui is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    29
    Sorry for reviving this thread, but I'm in need of a bit more help if the interval, was another number instead of 2 (lets call this k), how would I modify the equation?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Gui View Post
    Sorry for reviving this thread, but I'm in need of a bit more help if the interval, was another number instead of 2 (lets call this k), how would I modify the equation?
    The answer is given as a recurrence in the Wikipedia article. Easiest implmenetation is with a recursive function in a programming language. However for large n this might exhaust the stack, so you could instead write the program iteratively. For many successive calculations you could use memoization. (Yes there is no "r", you can google memoization.)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Gui
    Gui is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    29
    Ah, ok. So now I'm trying to modify it so that instead of every 2nd person being killed (starting out with don't kill, kill, don't kill, kill), the first person is killed (starting out kill, don't kill, kill, don't kill).

    I've messed around with it and I'm getting correct results by simply taking out the "+1" at the end - it works correctly for any number except powers of 2 - which it gives 0. I think the pattern, though, is that for any power of 0 - 8, for example - the survivor is the very last one - in this case, number 8.

    Is this correct? Thanks!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Gui View Post
    Ah, ok. So now I'm trying to modify it so that instead of every 2nd person being killed (starting out with don't kill, kill, don't kill, kill), the first person is killed (starting out kill, don't kill, kill, don't kill).

    I've messed around with it and I'm getting correct results by simply taking out the "+1" at the end - it works correctly for any number except powers of 2 - which it gives 0. I think the pattern, though, is that for any power of 0 - 8, for example - the survivor is the very last one - in this case, number 8.

    Is this correct? Thanks!
    You are mapping

    2 -> 1
    3 -> 2
    ...
    n -> n-1
    1 -> n.

    So, yes, you are correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Josephus problem with varying k
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 14th 2012, 09:19 AM
  2. flavius-josephus sieve?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 22nd 2008, 07:41 AM

Search Tags


/mathhelpforum @mathhelpforum