Josephus problem?

[Don Reble]

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