Hello, everyone. I have a group project where we have to explain the Josephus problem and use Maple to solve the problem. I am trying to solve the problem in multiple ways (because why not), but I am struggling with my third procedure. I understand the logic behind it and how its supposed to achieve O(k*logn), but the code that I wrote for it doesn't seem to produce the correct result.
JosephusImproved := proc (n, k)
local count, result:
if n = 1 then
elif 1 < n < k then
return JosephusImproved(n - 1, k) + k + 1 mod n:
count := floor(n / k):
result := JosephusImproved(n - count, k):
result := result - n mod k:
if result < 0 then
result := result + n
result := floor(result /(k - 1)):
Note: The regular recursive expression [Josephus(n - 1, k) + k + 1 mod n] has a "+ 1" since that was the only way I could make Maple do the calculation correctly. Proven with a Cyclic procedure I already made.
Note 2: I am using Maple 2016 and 2D Math.
I would like some insight as to how I could fix this so that it works, just like the regular recursive procedure and cyclic list that I have.