Q: Lobb number — Calculate the Lobb number for particular values of $m$ and $n$:
$$L_{m,n} = \frac{2m + 1}{m + n + 1}{2n \choose m + n}$$The left term is a constant time operation, whilst the right term is a factorial. Similar to Fibbonacci, we could solve the right term using a brute-force recursive algorithm. But it's much more efficient to reuse computations from one factorial chunk for the other chunks.
The factorial form of the combination calculation is:
$$\frac{2n!}{(m + n)! \times (n - m)!}$$The key insight: if $m \geq n$, $(m + n)!$ has the most factorial terms. Otherwise $2n!$ does. We only need to calculate one of these factorials, the rest of the factorial values will follow.
assert = require('assert');
// TODO
{ [Function: ok] fail: [Function: fail], AssertionError: [Function: AssertionError], ok: [Circular], equal: [Function: equal], notEqual: [Function: notEqual], deepEqual: [Function: deepEqual], deepStrictEqual: [Function: deepStrictEqual], notDeepEqual: [Function: notDeepEqual], notDeepStrictEqual: [Function: notDeepStrictEqual], strictEqual: [Function: strictEqual], notStrictEqual: [Function: notStrictEqual], throws: [Function: throws], doesNotThrow: [Function: doesNotThrow], ifError: [Function: ifError] }
function lobb(m, n):
mult_part = (2*m + 1) / (m + n + 1)
if (m >= n):
maxfact = m + n
else:
maxfact = 2 * n
memo = fact(maxfact)
comb_part = memo[2* n] / (memo[m + n] * memo[2n - m])
return mult_part * comb_part
function fact(n):
memo = [1, 1]
if n <= 1: return memo[n]
for (nv in range(2, n + 1)):
memo[nv] = memo[nv - 1] * nv
return memo[n]
function fact(n) {
let memo = [1, 1];
if (n <= 1) return memo[n];
for (nv of [...Array(n).keys()].map(v => v + 2)) memo.push(memo[nv - 1] * nv);
return memo;
}
function lobb(m, n) {
mult_part = (2*m + 1) / (m + n + 1);
let maxfact = (m >= n) ? m + n : 2*n;
let memo = fact(maxfact);
comb_part = memo[2* n] / (memo[m + n] * memo[n - m]);
return mult_part * comb_part;
}