select the integers that will left if n integers are arranged in a circle, and integers are struck off the list in skips of m until r remain.
merlyn stirs his dry martini on the latest linux geek cruise, unaware that the right. rev lars marius garshol has just arrived, late, and *someone* is going to have to double-up rooms.

rev. garshol is going to be preparing a sermon on the seven deadly (programming) sins, foremost of which is, naturally, > 4 operators in any script.

the cruise masters decree that to solve the problem, all cruise members are to be arranged in a circle, and every nth member is to be struck off until one remains, that one to get garshol.

ie: with 10 geeks, and a skip number of 1, the geeks will be relieved of lars in the following manner:

{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"},# start

{"3", "4", "5", "6", "7", "8", "9", "10", "1"},# 2 saved

{"5", "6", "7", "8", "9", "10", "1", "3"},# 4 saved

{"7", "8", "9", "10", "1", "3", "5"},# 6 saved

{"9", "10", "1", "3", "5", "7"},# 8 saved

{"1", "3", "5", "7", "9" },# 10 saved

{"5", "7", "9", "1"},# 3 saved

{"9", "1", "5" },# 7 saved

{"5", "9"},# 1 saved

{"5"}# 5 spends the night with garshol



of course things get more complex with n = any integer, and any number of geeks to be saved.

undeterred, our hero gathers the enlightened on the cruise, and instructs them all, using a simple script, on which places *not* to stand at.

here is what he might have coded:

for (($m,$n,$r)=@ARGV, $jl=[1..$n]; @$jl>$r; shift @$jl){
push(@$jl,shift @$jl) for (1 .. $m) 
}
print "avoid positions " , join(" ", @$jl) . "\n";

[download]
m, n and r are the skip number, the total number of geeks, and the number of (perl) enlightened to be saved from lars. so we get:

avoid positions 3222783

if we use m = 1, n = 9999999, r = 1

admittedly this is a large number of geeks and it takes time. admittedly, there is a low probability of having to share with the reverend. but there is also sod's law...

if a larger number of geeks appear on the cruise, and every other person is skipped, then for merlyn alone we can find out the position faster, in less memory, via: 
sub joe {$n=$_[0];($n==1)? 1:(($n % 2)? 2*joe(($n - 1)/2)+1:2*joe($n/2
+)- 1)}
print "v2: use position " . joe($n) . "\n";

[download]
speedy and non-memory-exhaustive solutions ensue. the recursion is loads faster than the previous, but then it is not as generalizable. select your favourite, take it with you wherever you go, just in case ;-)

wufnik

-- in the world of the mules there are no rules --

In reply to save the saint (Josephus Problems in Perl) by wufnik

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.