A005428 (was: Sequence A112088 Motivation and Example?)

[Max]

On 6/9/06, Max <maxale at gmail.com> wrote:

> On 6/9/06, Graeme McRae <g_m at mcraefamily.com> wrote:
>
> > It took me quite some time to understand how Ranier Rosenthal is counting
> > rounds, before I obtained A112088 as the number of rounds necessary to kill
> > all but one of n players of the Josephus Game with every third man out.  I
> > first tried using Hugo Pfoertner's idea where the final survivor counts the
> > times he was passed by the executioner including the final rendezvous.  But
> > that method gives an entirely different sequence (A005428:
> > 1,2,3,4,6,9,14,21,31,47,70,105,158,...).
>
> I've also ended up with this exactly sequence in my computations.

Actually, I came to A005428 with somewhat simpler iterations:

a(1) = 1
s(1) = 2
a(n) = floor( (3*a(n-1) + s(n-1) - 1) / 2 )
s(n) = (s(n-1) + a(n)) mod 3

In PARI/GP they give:

? x=1;s=2;for(k=1,50,print1(x,", ");x=(3*x+s-1)\2;s=(s+x)%3)
1, 2, 3, 4, 6, 9, 14, 21, 31, 47, 70, 105, 158, 237, 355, 533, 799,
1199, 1798, 2697, 4046, 6069, 9103, 13655, 20482, 30723, 46085, 69127,
103691, 155536, 233304, 349956, 524934, 787401, 1181102, 1771653,
2657479, 3986219, 5979328, 8968992, 13453488, 20180232, 30270348,
45405522, 68108283, 102162425, 153243637, 229865456, 344798184,
517197276,

The sister sequence s(n) is missing in OEIS:

? x=1;s=2;for(k=1,50,print1(s,", ");x=(3*x+s-1)\2;s=(s+x)%3)
2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2,
1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 2, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1,
2, 1, 1, 1,

Max