Josephus problem?
Ralf Stephan
ralf at ark.in-berlin.de
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.
ralf
More information about the SeqFan
mailing list