Sequence A112088 without example

[Max]

On 6/6/06, Hugo Pfoertner <all at abouthugo.de> wrote:

> AFAIK, Rainer is talking about the Josephus Problem in its classical
> form, where n people are arranged around the circumference of a circle.
> An executioner walks around the circle without changing his direction
> and without making shortcuts. Starting at the first person, every third
> (of the remaining) persons on the circumference of the circle is
> eliminated until only one person remains. The surviving persons remain
> at their original positions in the circle. Therefore the executioner
> needs to walk a certain amount of rounds until his job is done. Rainers
> observation is that A112088(n) is the minimum number of people required
> such that the executioner needs n rounds until only one survivor
> remains.

Thanks for the explanation! Now this sequence makes a perfect sense to me.

> It might be necessary to adjust the offset dependent on how exactly
> "rounds" are counted. I prefer a rounds count, where the final survivor
> counts the times he was passed by the executioner including the final
> rendezvous.

Counting the final rendezvous will make the offset equal 2 in Rainer's sequence.
I would vote for not counting the final rendezvous implying the offset
equal 1. In other words, a round is counted as soon as the executioner
pass from the current highest number holder to the current smallest
number holder.

> Forgot to mention: If you don't have a copy of Graham/Knuth/Patashnik's
> "Concrete Mathematics", which has a lot of material on the Josephus
> problem in chapters 1.3 and 3.3, another good place to start is the
> Odlyzko/Wilf article "Functional iteration and the Josephus problem" at
> http://citeseer.ist.psu.edu/odlyzko91functional.html

For those who can read in Russian I can also suggest my old paper on
Josephus problem:
http://www-cse.ucsd.edu/users/maxal/josephus.pdf

Max

> > On 6/5/06, Rainer Rosenthal <r.rosenthal at web.de> wrote:
> > > To SeqFan and to author Simon Strandgaard:
> > >
> > > Playing the "Josephus problem" with "every third out"
> > > and denoting the minimum numbers in this game, I found
> > >
> > >      2, 3, 5, 7, 11, 16, 24, 36, 54, 81, ...
> > >
> > > I was happy to find them in this sequence:
> > > http://www.research.att.com/~njas/sequences/A112088.
> > >
> > > My computed values are the same up to a(18) = 2082, so
> > > that my Josephus game is likely to generate exactly
> > > this sequence.
> [...]