Josephus problem?

Ralf Stephan ralf at
Thu Apr 24 16:25:57 CEST 2003

Is it now okay to assume the identity of
- A073941 as named,
- A005428 as named,
- first differences of A061419 (D3)?

I would like to add log2(A082125(n>2)) but I'm not quite satisfied
with the following. Can someone improve or shorten?  Thanks.

%S A082125 4,3,4,2,4,8,16,64,512,16384,2097152,2147483648,140737488355328,
%N A082125 Smallest difference>1 between d and p/d for any divisors d of the partial product p of the sequence, starting with 4.

To prove
- members with n>2 are powers of two,
- a(n>2) = 2^A005428(n-3).

First, A082125(n>2) is identical to A(n-2) where
A(0)=4*3*4=48, A(n+1)={Smallest difference>1 between d and p/d for 
                 any divisor d of the partial product p of the sequence}
Example: A(1)=8-6=2, as A(0)=48=6*8; A(2)=12-8=4, as A(0)*A(1)=96=8*12.

To prove: for n>0, A(n)=2^i, with i>0 integer.
  Contemplate (sorted) numbers of the form 2^i or 3*2^i (=A029744).
  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.
  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).
  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). 

  [waving hands here]

  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),
  which is recognized as D3(n) from the Josephus problem.


More information about the SeqFan mailing list