Thread: 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!

Originally Posted by Gui

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.

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.

Originally Posted by Gui

Oh, so f(n) = 2*(n-2^m)+1? Is that correct, for any possible n - including both odd and even numbers?

Correct.

Originally Posted by Gui

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.

Originally Posted by undefined

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.

Originally Posted by Gui

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

Originally Posted by Gui

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.

It does work as expected - it's perfect! Thank you very much for bearing with me undefined, your help was great!

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?

Originally Posted by Gui

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.)

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!

Originally Posted by Gui

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.