Josephus problem
Ralf Stephan
ralf at ark.in-berlin.de
Thu Apr 24 17:50:46 CEST 2003
Corrections,
> See that A029744 (=B(n)) consists of the divisors of 3*2^inf, i.e.,
> B(0) to B(2n) contains all divisors of B(2n)=3*2^n, sorted.
except B(2n-1)
> The first differences have the ogf (1-x)/(1-2x^2), = A016116(n-1) =
> = 2^floor((n-1)/2).
>
> This means also that the partial product in A always has the form
> P(n>0) = 3*2^i, with P(1)=3*2^4.
>
> To prove: A(n)=2^A005428(n-1), see that
> B(0)=1, B(2i-1)=2^i, B(2i)=3*2^(i-1), and also one can form
> products B(2n) = B(1)*B(2n-2) = B(2)*B(2n-3)...= B(n-1)*B(n).
> So, 3*2^n = B(n-1)*B(n), and B(n)-B(n-1)=2^floor(n/2-1).
So, 3*2^(n-1) = B(n-1)*B(n), and B(n)-B(n-1)=2^floor(n/2-1).
> start with A(0)=48=3*2^s, s=4, then A(1)=2^floor(s/2-1),
> so P(n)=3*2^(s(n)), with s(0)=4 and s(n)=
> [s(n-1) even] (3/2*s(n)-1) + [s(n-1) odd] (3/2*s(n)-3/2).
so P(n)=3*2^(s(n)), with s(0)=4 and s(n+1)=
[s(n) even] (3/2*s(n)-1) + [s(n) odd] (3/2*s(n)-3/2).
> So P(n)=3*2^(3+s(n)), with s(0)=1 and s(n+1)=
> [s(n-1) even] (3/2*s(n)) + [s(n-1) odd] (3/2*s(n)+1/2),
[s(n) even] (3/2*s(n)) + [s(n) odd] (3/2*s(n)+1/2),
> which is recognized as D3(n) from the Josephus problem.
And, of course, as A(n)=P(n)/P(n-1) = 2^(s(n)-s(n-1)), the
assertion should follow.
But you see, the line is not complete, but I'm really drawn out,
I have never studied math, and I like to think it's clear for you.
ralf
More information about the SeqFan
mailing list