Recently, I had thought of something about the Josephus Problem. How can we find the number(s) a survivor must stand at out of $n$ people when the executioner kills every $k th$ person when $n$ and $k$ assume very large values? For example, if there are $4171998$ people in a circle and every $417th$ person is killed, then at what number should the survivor(s) stand? Please give a non-CS solution which is not too long or hard to work out by hand. Thanks very much!

Note by Ishan Dasgupta Samarendra
4 years, 8 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Also It can be solved using Circular Linked List, do you want the solution using it?

- 4 years, 8 months ago

Happy belated B'day ! Sorry if I am late in wishing you !

- 4 years, 8 months ago

Thanks a lot..!! $\ddot\smile$ By the way you have got a pretty sharp observation.. cool...and you aint that late just 5 days.. :P and yeah where had you disappeared suddenly.. u even lost your streak..!!

- 4 years, 8 months ago

Haha yes , thanks :)

It seems the day I went away was your B'day ! Too bad on my part :(

Well, I was busy with some other things and btw streak doesn't matter right now , once JEE gets over , I'll extend my streak till the end of time :D

- 4 years, 8 months ago

Yeah its alright..!! Well thats the spirit..

- 4 years, 8 months ago

Now that you've mentioned about the streak , make sure that you guys congratulate @Kartik Sharma in a few days since he'll be completing a year long streak :)

- 4 years, 8 months ago

Sorry, but what if every 417th person was killed? I've modified the Note so that one example is there in the introduction itself. How would we solve the question in the Note? Would you change 4171998 (base 10) to something in base 417, perform your operation, and then convert it back to base 10 to get $j(n)$? Also, would we not have to change the operation since we are working in another base (perhaps 417)? Thanks a lot.

- 4 years, 8 months ago

Thanks a lot..!! $\ddot\smile$. By the way we are converting the number for decimal(base 10) to binary(base 2). So the rest procedure would be the same. Any further doubt then please ask..

- 4 years, 8 months ago

Happy belated birthday wishes!

- 4 years, 8 months ago

Thanks a lot..!! $\ddot\smile$

- 4 years, 8 months ago

Oh I am late! Still Belated Happy B'day!! Good luck for JEE!

- 4 years, 8 months ago

@Pranjal Jain Thanks a lot..!! $\ddot\smile$ and yeah I am sorry I am just having some problems with my phone.. So couldnt send you the program btw ca you just tell the question once again here...

- 4 years, 8 months ago

Its for displaying the smallest triangular number which has more than 500 divisors Triangular Numbers are 1,1+2,1+2+3,1+2+3+4,....

I end up using python then.

- 4 years, 8 months ago

Hint: If there are $2^n$ people left, who wins?

Staff - 4 years, 8 months ago

@Calvin Lin The first person out of the $2^n$ people, isn't it? For every 2nd person being killed out of $n$ persons, we can simply do this: the winner will be the person standing at $2k+1$ where $n = 2^m + k , k = n - \text{(largest value of }2^m \text{ below n),} \text{ and } 2^m \text{ is the largest value less than } n$ But what if every 10th or every 15th person is killed? And further on, for every 417th, and so on, how can we solve it manually?

- 4 years, 8 months ago

That's a good problem. I'll try to figure out a solution and post it as soon as I get some free time.

And I remember @Maryann Vellanikaran posted a similar problem. So, in the meantime, you may be interested in trying it out. Best of Luck.

Thanks.

Kishlaya Jaiswal

- 4 years, 8 months ago

So are you going to post a question inspired from the Josephus problem ?

- 4 years, 8 months ago

I want to, but the problem is that I don't know how to solve it myself. I can't use a program, and Harshvardhan's method did not work out for me here. I really don't know what to do.

- 4 years, 8 months ago

@Simran Malik I found a non CS solution on the net.. but just the problem is that it is a bit too lenthy and time consuming ot understand... anyways here is the link

- 4 years, 8 months ago

Thanks very much!

- 4 years, 8 months ago

It's tomorrow right ? Best of Luck !

- 4 years, 8 months ago

Best of Luck to both of you for tomorrow's exam $\ddot \smile$

- 4 years, 8 months ago

Thanks , it's not a Board's exam tomorrow (the next one's on the 27th) , btw I do have a test at my Coaching class .

- 4 years, 8 months ago

Yeah. Thanks very much and all the very best to you too!

- 4 years, 8 months ago

You are most welcome.. $\ddot \smile$ and yeah All the best for your exam..!! By the way why do you want a mathematical proof when you can solve it easily by a program..??

- 4 years, 8 months ago