|
![](/i/fill.gif) |
Warp wrote:
> Kevin Wampler <wam### [at] u washington edu> wrote:
>> nor is #4, as I don't think it's possible).
>
> AFAIK the simplest recursive solution to the problem is (as I mentioned in
> another post) this:
>
> f(0) = 0
> f(n) = floor(n/5) + f(floor(n/5))
>
> One could try to prove that the above cannot be expressed in closed form.
> But AFAIK that wouldn't be a proof that there is no closed form solution at
> all, just that the above method cannot be expressed in that form.
I'm not sure quite what you mean here, wouldn't any closed form solution
to the original problem also by definition be a closed form solution to
the above recursion?
In any case, I'm relatively confident that the answer can't be
represented in closed form under the standard definition of closed form
since the sequence has a sort of fractal structure to it.
I do agree that it's a neat problem if you remove the closed form
restriction, and seems about the right difficulty to fit with the others.
Post a reply to this message
|
![](/i/fill.gif) |