On 8/19/07, David Wilson <davidwwilson@comcast.net> wrote:
Here's the best I could do:
Let b(n) be the distance between the first and last 1 in the binary expression of n. For example, b(1) = 0, b(3) = 1, b(5) = 2, b(6) = 1.
Then your sequence is
f(n) = 0 if n = 0, else b(n) if n even, else b(n)+b(n+1).
Yeah, ugly.
Maybe so, but (although they're easily seen to be equivalent) this formulation is a worthwhile improvement on my own solution. The sequence posed was associated with p = 2, which behaves atypically: instead of the explicit formula depending on the residue n mod 2, for general p it depends on n mod(p-1). These sequences arise as the residual between the exact value of ord_p s(m, n) and the sharp monotonic lower bound for 0 <= n <= m SMLB(m, n) = \sum_{j > 0} \max(0, -[n - m/p^j]) --- which I earlier tried (and failed) hard (I really did) to announce without any misprints. In the case that m = p^k it's possible to conjecture the explicit form of this residual for all n, thus giving the exact order. Proving these formulae, or extending them to general m, still looks a fairly distant prospect. It's nice that these sequences of residuals are independent of k. And David's expression unexpectedly depends on n, n+1; whereas the basic Stirling number recursion depends on n, n-1. I've now recast my solution for general p along the lines suggested --- thanks for the input. Fred Lunnon [19/08/07]