Josephus problem

Ralf Stephan ralf at
Thu Apr 24 17:50:46 CEST 2003


>   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.


More information about the SeqFan mailing list