A recursive approach to Josephus problem (OEIS 225381)

Question

Taking integer $x$ as input:

If $x$ is even, then return $x/2$ as series item, giving $x/2$ as input to continue the loop;

Else return ceiling($x/2$) as series item, terminate the loop;

Finally we sum over the produced series.

Assuming this function is $f(x)$.

f(1) = ceiling(1/2) = 1
f(2) = 2/2 + ceiling(1/2) = 2
f(3) = ceiling(3/2) = 2
f(4) = 4/2 + 2/2 + ceiling(1/2) = 4
f(5) = ceiling(5/2) = 3
f(6) = 6/2 + ceiling(3/2) = 5
f(7) = ceiling(7/2) = 4
f(8) = 8/2 + 4/2 + 2/2 + ceiling(1/2) = 8
f(9) = ceiling(9/2) = 5
f(10) = 10/2 + ceiling(5/2) = 8
f(11) = ceiling(11/2) = 6
f(12) = 12/2 + 6/2+ ceiling(3/2) = 11
f(13) = ceiling(13/2) = 7
f(14) = 14/2 + ceiling(7/2) = 11
f(15) = ceiling(15/2) = 8
f(16) = 16/2 + 8/2 + 4/2 + 2/2 + ceiling(1/2) = 16
f(17) = ceiling(17/2) = 9
f(18) = 18/2 + ceiling(9/2) = 14

Note that $f(x)$ is OEIS 225381:

1,2,2,4,3,5,4,8,5,8,6,11,7,11,8,16,9,14 

The question is, is there any simple rational formula to calculate the final summatory f(x) or to represent OEIS 225381?

Answer 1

Not sure if there is a formula, but you could optimize your algorithm, since you calculate $f(x)$ repeatedly with increasing numbers, and the recursive function calls itself with lower values.

It's called memoization. Practically, storing the results of calls of lower values given to $f(x)$.

Something like

define array A

function f( x )
    if A[ x ] exists, then return A[ x ]
    if x is odd, then return ( x + 1 ) / 2
    half = x / 2
    A[ x ] = half + f( half )
    return A[ x ]
end function

Explanation

• declaration of an array A used to store calculated results from calling $f(x)$
• if $f(x)$ has already been calculated (thus its result is in A), return that stored result
• if not, and if $x$ is odd, just return $\dfrac{x+1}2$
• and, finally, if $x$ is even, calculate $x_{half} = \dfrac x2$, $R=x_{half}+f(x_{half})$
• store $R$ in A[x] (array A at position x)
• return the result $R$

---

Non recursive algorithm

function iter( x )
    i = 1
    while i <= x
       if i is odd, then A[ i ] = ( i + 1 ) / 2
       else 
          half = i / 2
          A[ i ] = half + A[ half ]
       end if
       i = i + 1
    end while
    return A[ x ]
end function