Josephus problem

[benoit]

Precisions are also needed for this one in order to prove also Ralf  
Stephan's claim :

%I A005427 M3759
%S A005427  
5,7,9,12,16,22,29,39,52,69,92,123,164,218,291,388,517,690,920,1226,1635,
%T A005427  
2180,2907,3876,5168,6890,9187,12249,16332,21776,29035,38713,51618,68824, 
91765
%N A005427 Josephus problem.
%C A005427 Is this the same as A072493 with its first 8 terms removed?  
See also the similar conjecture with A005428/A073941.


%S A072493  
1,1,1,1,2,2,3,4,5,7,9,12,16,22,29,39,52,69,92,123,164,218,291,388,517,
%T A072493  
690,920,1226,1635,2180,2907,3876,5168,6890,9187,12249,16332,21776,
%U A072493  
29035,38713,51618,68824,91765,122353,163138,217517,290023,386697
%N A072493 a(1)=1, a(n)=ceiling((sum_{k=1..n-1} a(k))/3).


Benoit Cloitre




>
> Benoit Cloitre asks twice, are A005428 and A073941 the same?
>
> %I A005428 M0572
> %S A005428 1,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
> %N A005428 a(0) = 1, state(0) = 2; for n >= 1,
>     if a(n-1) is even
>         then a(n) = floor(3*a(n-1)/2) and state(n) = state(n-1),
>     if a(n-1) is odd and state(n-1)=1
>         then a(n) = ceiling(3*a(n-1)/2) and state(n) = 3 - state(n-1),  
> and
>     if a(n-1) is odd and state(n-1)=2
>         then a(n) = floor(3*a(n-1)/2) and state(n) = 3 - state(n-1).
>
> %I A073941
> %S A073941 1,1,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
> %N A073941 a(n) = ceiling(sum{a(k): 1<=k<n} / 2); a(1)=1.
>
> They are plainly different: A073941 has an extra "1" at the start; and
> its index starts at one instead of zero. Aside from those, they are
> identical. A proof goes by induction: the above %S's are the induction
> basis.
>
>
> Observe that the state of A005428 changes just when A(n) is odd: it
> therefore indicates whether the sum of A(0) to A(n) is odd. (1 means  
> no,
> 2 means yes.)
>
> For k >= 2,
> let S1(k) = sum { A005428(0) to A005428(k-2) },
> and S2(k) = sum { A073941(1) to A073941(k) },
> so that S2(k) = S1(k)+1 (the extra "1"), in the induction hypothesis.
> The A005428 state also indicates whether S2(n) is even.
>
> In A073941, for n >= 2:
> - If S2(n-2) is 0 mod 4, then A(n-1) = S2(n-2)/2 and is even;
>   so S2(n-1) is even; and
>   A(n) = S2(n-1)/2 = [S2(n-2)+A(n-1)]/2 = [3*A(n-1)]/2
>        = floor(3*A(n-1)/2).
> - If S2(n-2) is 1 mod 4, then A(n-1) = [S2(n-2)+1]/2 and is odd;
>   so S2(n-1) is even; and
>   A(n) = S2(n-1)/2 = [S2(n-2)+A(n-1)]/2 = [3*A(n-1)-1]/2
>        = floor(3*A(n-1)/2).
> - If S2(n-2) is 2 mod 4, then A(n-1) = S2(n-2)/2 and is odd;
>   so S2(n-1) is odd; and
>   A(n) = [S2(n-1)+1]/2 = [S2(n-2)+A(n-1)+1]/2 = [3*A(n-1)+1]/2
>        = ceiling(3*A(n-1)/2).
> - If S2(n-2) is 3 mod 4, then A(n-1) = [S2(n-2)+1]/2 and is even;
>   so S2(n-1) is odd; and
>   A(n) = [S2(n-1)+1]/2 = [S2(n-2)+A(n-1)+1]/2 = [3*A(n-1)]/2
>        = floor(3*A(n-1)/2).
>
> The (3*A(n-1)/2) bit is the same as A005428.
> ceiling() is applied only
> - when A(n-1) is odd and S2(n-1) is odd; that is,
> - when A(n-1) is odd and S1(n-1) is even; that is,
> - when A(n-1) is odd and state(n-1)=1.
> That agrees completely with A005428's definition, and proves the
> induction step.
>
> --
> Don Reble       djr at nk.ca
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 3634 bytes
Desc: not available
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20030424/300854a2/attachment-0001.bin>