Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Josephus problem*:
circle=1,2,3,4,5,6,7,8,9,10. count=2. (Beginning at 1) The "last man standing" in this case=9.
Order of elimination or permutation (?): 2,4,6,8,10,3,7,1,9

For any size circle and any size count what is the math that produces the order of elimination? e.g. circle=1,2,3,4,5,6,7,8,9. count=10.
Order of elimination (starting at 1): 1,3,6,2,9,5,7,4,8

*(From wikipedia: http://en.wikipedia.org/wiki/Josephus_problem) The Josephus problem is a theoretical problem related to a certain counting-out game. There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

(Original post)

(please forgive me if this looks slightly familiar to anyone...)

Hello,

Does anybody know the math for a general case Josephus-like permutation (any size circle, any size count)?

e.g circle=9, count=10.
1,3,6,2,9,5,7,4,8

I only have access to what I can find on the web (Google) and what has previously been suggested doesn't cover this particular aspect (Concrete math; wikipedia....). The nearest I have found is http://mathworld.wolfram.com/JosephusProblem.html
Can anyone help?

TIA, Ian

share|improve this question
    
Thanks, but no that's not what I mean.. For these inputs e.g circle=9, count=10 this output 1,3,6,2,9,5,7,4,8. Or "dynamically" calculated from each elimination (first calculation produces 1, 2nd 3, 3rd 6,....) –  Ian May 19 '12 at 15:24
    
What do you mean, "does anybody know the math"? Why don't you formulate a precise question, and edit that into your post, and delete the stuff that doesn't actually tell us anything? –  Gerry Myerson May 20 '12 at 8:48
    
I think my question is clear (?) I don't know how to do this and I can't find this question answered anywhere. So, does anybody know? What's wrong with that? Why show your annoyance? Can you answer it? –  Ian May 20 '12 at 12:48
1  
Well, Ian, you posted the question 22 hours ago, and no one has had a go at it, and you might want to take that as a sign that I'm not the only person who doesn't think your question is clear. In my experience here, clear questions about elementary topics get answered within minutes of being posted. But, hey, suit yourself. If you're happy with the response you've gotten, don't change a thing. –  Gerry Myerson May 20 '12 at 13:07
    
What is TIA? @Ian –  Tomarinator May 20 '12 at 13:45

1 Answer 1

The math that produces the order of elimination is just counting repeatedly up to 10. Here's your circle: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, etc. Starting at 1, you count to 10, you land on 1, so you eliminate it. Now your circle is 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, etc. You count to 10, and you land on 3. You eliminate it, and your circle becomes 4, 5, 6, 7, 8, 9, 2, 4, 5, 6, 7, etc. You count to 10, land on 6, eliminate it, etc., etc., etc.

Now it's possible (but not at all clear from your question) that you already know all that, and what you really want is a formula that gives you the order of elimination without doing all the counting. I don't know if there is such a thing, but I know a good place to start looking: Gregory L. Wilson and Christopher L. Morgan, An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem, J. Number Theory 130 (2010) 815–827, MR 2600404.The paper gives many references to other papers on the Josephus problem.

share|improve this answer
    
Ah, formula! The missing word ;) "what you really want is a formula that gives you the order of elimination without doing all the counting" You are absolutely right, thank you. May I ask, additionally, (I'll risk be chastised again for being vague) would an iterative solution be easier? As in a function that takes as input the previous elimination to calculate the next elimination? I realise that I am out of my depth with this right now (the cause of my inarticulation?) I am a mathematical beginner and this is my "exploration". A little patience is appreciated.. Thanks again. –  Ian May 21 '12 at 11:10
    
I don't know whether an iterative solution would be easier; as I wrote, what I know is a good place to start looking. Have you started reading that paper yet? –  Gerry Myerson May 21 '12 at 11:19
    
That's going to have to wait until pay day I'm afraid. Thanks again. (Though saying that, I don't know what abelian groups are (or Fourier tansforms) so, I think I'd better start there :). Thanks –  Ian May 21 '12 at 11:34
    
You might have to understand abelian groups and Fourier transforms to understand that paper, but as I wrote the paper gives many other references to work on the Josephus problem, and some of those other works may be more accessible. Also, many papers have a non-technical introduction that summarizes what's known about the problem, and what's new in the paper at hand, so it's worth having a look at that. –  Gerry Myerson May 21 '12 at 13:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.