"It seems to me that Josephus could be a sort of Fibonacci event, if only I could write it."
I coded the faster analytic version of Josephus with O(n) running time, Josephus=. (0:`(] | [ + [ $: (_1 + ])))@.(1 < ]) because I was wondering if the Josephus rule was fair in the following sense: if the left argument is "chosen at random" then for every value of the right argument (n) does each position in the line has equal probability (1%n) of surviving? ( There is also a very fast concise version for k=2 ; see http://www.jsoftware.com/papers/play184.htm ) I plotted a modified version of the Josephus table to try to see a structure, viewmat @: ([ load @:('viewmat'"_)) @: ((Josephus % <:y)"0/~) @: >: @: i. 12 If you are patient enough the picture will eventually appear; if you are not but still want to see the picture, you could code the O(k log n) version (see, http://en.wikipedia.org/wiki/Josephus_problem ) for small k and large n and maybe use memoization. Regarding fairness, it seems to me that the rule is indeed fair and the question is connected to the, so called, Feline Josephus Problem and the sequence OEIS A003418. However, what really impresses me is the ability of our visual cortex to recognize patterns almost instantly! On Sat, Apr 20, 2013 at 3:46 AM, Linda Alvord <[email protected]>wrote: > It seems to me that Josephus could be a sort of Fibonacci event, if only I > could write it. > > K=3, n=17 > > ]A=:((17)$ 0 0 1)#i.17 > 2 5 8 11 14 > ]AA=:(-3|17)|.(17$1 1 0)#i.17 > 15 16 0 1 3 4 6 7 9 10 12 13 > > ]B=:A,(($AA)$ 0 0 1)#AA > 2 5 8 11 14 0 4 9 13 > ]BB=:(-3|$AA)|.(($AA)$1 1 0)#AA > 15 16 1 3 6 7 10 12 > > ]C=:B,(($BB)$ 0 0 1)#BB > 2 5 8 11 14 0 4 9 13 1 7 > ]CC=:(-3|$BB)|.(($BB)$1 1 0)#BB > 10 12 15 16 3 6 > > ]D=:C,(($CC)$ 0 0 1)#CC > 2 5 8 11 14 0 4 9 13 1 7 15 6 > ]DD=:(-3|$CC)|.(($CC)$1 1 0)#CC > 10 12 16 3 > > ]E=:D,(($DD)$ 0 0 1)#DD > 2 5 8 11 14 0 4 9 13 1 7 15 6 16 > ]EE=:(-3|$DD)|.(($DD)$1 1 0)#DD > 3 10 12 > > ]F=:E,(($EE)$ 0 0 1)#EE > 2 5 8 11 14 0 4 9 13 1 7 15 6 16 12 > ]FF=:(-3|$EE)|.(($EE)$1 1 0)#EE > 3 10 > > Only two left, so the next sequence would be 3 10 3 so 3 is killed and 10 > lives. > > [G=:F,(($3$FF)$ 0 0 1)#3$FF > 2 5 8 11 14 0 4 9 13 1 7 15 6 16 12 3 > ]GG=:(-3|$FF)|.(($FF)$1 1 0)#FF > 3 10 > > (-.(i.17) e. G)#i.17d > 10 > > Linda > > -----Original Message----- > From: [email protected] > [mailto:[email protected]] On Behalf Of David Ward > Lambert > Sent: Thursday, April 18, 2013 11:20 PM > To: programming > Subject: [Jprogramming] rosettacode > > Please modify these new entries as you please: > http://rosettacode.org/wiki/Josephus_problem#J > > http://rosettacode.org/wiki/Continued_fraction/Arithmetic/Construct_from_rat > ional_number#J<http://rosettacode.org/wiki/Continued_fraction/Arithmetic/Construct_from_rational_number#J> > The continued fraction solution has some oddities. Returning _ to signal > "finished" converts the output vector to floating point. That's why I > excluded the 314285714 100000000x example. The `y is 8' input to r2cf__CF > is arbitrary and I have to strip it with _ from the output vector. > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
