Solve binomial coefficient without lookup

Question

I want to solve for n in the expression (binomial coefficient):

\$y=\frac{n^2+n}2\$

let y = (Math.pow(n, 2) + n) / 2;

I know the \$y\$ value, but I want to compute \$n\$.

---

Here is what I have so far, but I would want to know if there was a way to compute the value rather than look it up. In this example, I have to lookup the max value in a reversed array that is constrained by a length of 10.

Edit: Here is another avenue I took (still not an expression):

// Iterative
const toBase = n => {
  if (n < 1) return 0;
  let value = n, delta = 0;
  while (value > 0) value -= delta++;
  return delta - 1;
};

// Recursive
const toBase = (n, delta = 0) =>
  n === 0 && delta === 0
    ? 0
    : n < 1
      ? delta - 1
      : toBase(n - delta, delta + 1);

const MAX_BASES = 10;
const range = n => new Array(MAX_BASES).fill(0);
const binomialCoefficient = n => (Math.pow(n, 2) + n) / 2;
const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i));
const toBase = n => baseMax.indexOf([...baseMax].reverse().find(max => n > max)) + 1;

const main = () => {
  const inputs = getInputs().trim().split(/\n/)
    .map(l => l.trim().split(/\s+/g).map(v => parseInt(v.trim(), 10)))
    .filter(([v]) => !isNaN(v));
  inputs.forEach(input => validate(...input));
};

const validate = (n, expected) => {
  const actual = toBase(n);
  if (actual !== expected) {
    throw new Error(`${actual} !== ${expected} for n=${n}`);
  }
  console.log(`${n}: ${expected} === ${actual} | valid!`);
};

const getInputs = () => `
 0 0

 1 1

 2 2
 3 2

 4 3
 5 3
 6 3

 7 4
 8 4
 9 4
10 4

11 5
12 5
13 5
14 5
15 5

16 6
17 6
18 6
19 6
20 6
21 6

22 7
23 7
24 7
25 7
26 7
27 7
28 7

29 8
30 8
31 8
32 8
33 8
34 8
35 8 
36 8
`;

main();

.as-console-wrapper { top: 0; max-height: 100% !important; }

14

14 - 1 =  13
13 - 2 =  11
11 - 3 =   8
 8 - 4 =   4
 4 - 5 =  -1

Background: I noticed a pattern which looked very similar to a factorial expression, but with addition rather than multiplication. After some research, I stumbled upon the following question which lead me in the right direction:

"Factorial, but with addition" - Mathematics Stack Exchange

Answer 1

A review of the first 5 lines

Only looking at the code related to the problem and ignoring the testing code as it looks haphazardly put together.

Thus

const MAX_BASES = 10;
const range = n => new Array(MAX_BASES).fill(0);
const binomialCoefficient = n => (Math.pow(n, 2) + n) / 2;
const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i));
const toBase = n => baseMax.indexOf([...baseMax].reverse().find(max => n > max)) + 1;

Minor point

You should use the operator ** (Exponentiation) rather than the math function Math.pow . Both ** and Math.pow use the same pow function under the hood so there is no performance difference, however ** is cleaner.

The bad part

The only thing that is bad in your code, even assuming you are forced to lookup the values, is that every time you call toBase you recreate the array, reverse it, and then search it.

To get the correct value subtract the index from the arrays length. There is an edge case when the input is 0. That can be handled with a ternary.

You only need to reverse the array once.

 const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i)).reverse();

Subtract the index from the arrays length to get the result you are after. The edge case n = 0 can be handled with a ternary.

 const toBase = n => !n ? 0 : baseMax.length - baseMax.indexOf(baseMax.find(max => n > max));

Rather than use Array.find you can use Array.findIndex This will save you having to search the array twice, once to find the value n <= max then again to find the index with Array.indexOf

Thus you get

 const toBase = n => !n ? 0 : baseMax.length - baseMax.findIndex(max => n > max);

And you don't need to reverse the array which makes it even simpler

 const baseMax = range(MAX_BASES).map((v, i) => binomialCoefficient(i));
 const toBase = n => !n ? 0 : baseMax.findIndex(max => n <= max);

A functional solution.

The function (n ** 2 + n) / 2 is a quadratic \$\frac{1}2n^2 + \frac{1}2n + 0 = y\$

You can solve the quadratic when \$y=0\$ using \$\begin{array}{*{20}c} {x = \frac{{ - b \pm \sqrt {b^2 - 4ac} }}{{2a}}} \\ \end{array}\$

However as we change \$n\$ the solution we are after is no longer at \$y = 0\$

If we move the parabola down so that \$y\$ is at 0 for the value \$n\$ we are solving for we can then solve for any value of \$n\$

The quadratic to solve is \$\frac{1}2x^2 + \frac{1}2x - n = 0\$

\$ {x=\frac{{-\frac{1}2+\sqrt{\frac{1}4-4*\frac{1}2*-n} }}{{2*\frac{1}2}}}\$

which is

\$x=-\frac{1}2+\sqrt{\frac{1}4+2n} \$

Now we get \$x\$ for \$n\$ and round it up when \$x\$ is a fraction.

The rewrite

An thus the 5 lines become one line.

const toBase = n => Math.ceil(-0.5 + (0.25 + 2 * n) ** 0.5);

Answer 2

We have \$y=\frac{n^2+n}2=\frac{n(n+1)}2\$ and thus \$2y=n(n+1)\$ and thus \$\sqrt{2y}\$ lies between \$n\$ and \$n+1\$, so just round down:

n = Math.floor((2 * y) ** 0.5)

or

n = Math.floor(Math.sqrt(2 * y))