Josephus problem with an infinite sum

Number Theory Level 4

This problem's question: What is a sufficiently accurate approximation to satisfy Brilliant's requirements of the infinite sum of the reciprocals of the size of circles,where circle sizes start at 3, where the survivor is the person is the person originally to the starters left? Only four digits were supplied in the official answer.

Brilliant seems to require three or four significant digit accuracy only.

A circle is formed of n n people, facing inward so the a person's left and right are defined. A person is picked to be the starter. You may consider them to be numbered from 1 1 to n n . Then the process of removal from the circle begins. Every other person is removed from the circle going to the right. The first person removed is the person to the starter's right. In the case of a size 3 circle and using the proposed numbering: first person 2 is removed, then person 1 is removed and person 3 becomes the sole survivor. Therefore, the first approximation to the infinite sum of reciprocals is 1 3 \frac13 .

In the solution, I will provide the first twenty approximations and the infinite sum. You will not need to go that far.


The answer is 0.6066.

A Former Brilliant Member by A Former Brilliant Member

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The sizes of circles where the sole survivor is the person originally to the starter's left are 2 n − 1 2^n-1 . This can be proved by induction.

Table [ { i − 1 , N [ ∑ n = 2 i 1 2 n − 1 ] } , { i , 2 , 21 } ] ⇒ 1 0.333333 2 0.47619 3 0.542857 4 0.575115 5 0.590988 6 0.598862 7 0.602784 8 0.604741 9 0.605718 10 0.606207 11 0.606451 12 0.606573 13 0.606634 14 0.606665 15 0.60668 16 0.606688 17 0.606691 18 0.606693 19 0.606694 20 0.606695 \text{Table}\left[\left\{i-1,N\left[\sum _{n=2}^i \frac{1}{2^n-1}\right]\right\},\{i,2,21\}\right] \Rightarrow \\ \begin{array}{rl} 1 & 0.333333 \\ 2 & 0.47619 \\ 3 & 0.542857 \\ 4 & 0.575115 \\ 5 & 0.590988 \\ 6 & 0.598862 \\ 7 & 0.602784 \\ 8 & 0.604741 \\ 9 & 0.605718 \\ 10 & 0.606207 \\ 11 & 0.606451 \\ 12 & 0.606573 \\ 13 & 0.606634 \\ 14 & 0.606665 \\ 15 & 0.60668 \\ 16 & 0.606688 \\ 17 & 0.606691 \\ 18 & 0.606693 \\ 19 & 0.606694 \\ 20 & 0.606695 \\ \end{array}

∑ n = 2 ∞ 1 2 n − 1 ⇒ log ⁡ ( 2 ) − ψ 1 2 ( 0 ) ( 2 ) log ⁡ ( 2 ) ≈ 0.60669515241529176378 \sum _{n=2}^{\infty } \frac{1}{2^n-1}\Rightarrow \frac{\log (2)-\psi _{\frac{1}{2}}^{(0)}(2)}{\log (2)} \approx 0.60669515241529176378

1 Helpful 1 Interesting 1 Brilliant 2 Confused

I got the question,but i seriously think you should change the wording,it makes the question unnecessarily confusing with same sentence repeated twice

Shauryam Akhoury - 2 years ago

Log in to reply

I have reread the problem several times. I do not see a duplicate sentence. Perhaps, you would quote them in your reply with some context.

A Former Brilliant Member - 2 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...