## Introduction

At the time of writing this, I’m a highschool student. With the way our school system is laid out, I end up doing
*a lot* of math - more so than computer science - and lately I’ve been very passionate about it.

Anyways, our story begins on the 5th of February, 2023. I was working on a Discord bot for ChatSift, responsible for some sort of leveling system - users would gain XP for sending messages, and crossing certain thresholds would cause you to level up. As I was working out my database schema, I landed on this:

```
model User {
userId String
guildId String
xp Int @default(0)
@@id([userId, guildId])
}
```

and thought to myself, “hmm, I could potentially get away with not storing the current level, and just calculate it on the fly.”

The main reason I even thought of this was because the formula to determine the XP required for a given level is
$base + (level - 1) * multiplier$. For example, if the base was `100`

, and the multiplier was `50`

, then the XP required
for level 1 would be `100`

, and the XP required for level 2 would be `150`

, and so on. This is a very simple formula, and
it would be trivial to track if the user had enough XP to level up, and if so, increment their level and subtract the XP
on the fly, but I thought it would be a headache to have to recompute the level for *every* user in the whole community if
an admin decided to change the `base`

or the `multiplier`

.

# Optimization problems

As such, I opted to not store the level, and instead just store the *total* XP the user has *ever* accumulated, and
compute the level on the fly as-needed. At this point, I realized that calculating how much XP is needed for say, level 3,
is the sum of the XP required for levels 1, 2, and the usual $base + (level - 1) * multiplier$.

I then decided to represent this mathematically before implementing it, and I ended up with this:

$$ n, m \in \mathbb{N*} \newline f: \mathbb{N*} \rightarrow \mathbb{N*} \newline f(x) = \begin{cases} n & x = 1 \newline f(x - 1) + xm & x > 1 \end{cases} $$

where `n`

is our base, `m`

is our multiplier and `x`

is the level.

I then wrote this up in my TypeScript codebase:

```
export function calculateRequiredXp(settings: GuildSettings, level: number): number {
const { requiredXpBase, requiredXpMultiplier } = settings;
if (level === 1) {
return requiredXpBase;
}
return calculateRequiredXp(settings, level - 1) + requiredXpMultiplier * level;
}
```

It quickly became apparent to me that this was not going to perform all that well. Calculating what level a user is looked like this:

```
export function calculateUserLevel(settings: GuildSettings, user: User): number {
for (let level = 1; ; level++) {
const requiredXp = calculateRequiredXp(settings, level);
if (user.xp < requiredXp) {
return level - 1;
}
}
}
```

If they were level `N`

, we would actually be computing the XP required for level 1 `N`

times. This is obviously not
ideal, and I decided to try and optimize it. I opted for memoization and ended up with this:

```
const requiredXpMemo = new Map<`${number}-${number}-${number}`, number>();
export function calculateRequiredXp(settings: GuildSettings, level: number): number {
const { requiredXpBase, requiredXpMultiplier } = settings;
const memoKey = `${requiredXpBase}-${requiredXpMultiplier}-${level}` as const;
if (requiredXpMemo.has(memoKey)) {
return requiredXpMemo.get(memoKey)!;
}
const result = calculateRequiredXp(settings, level - 1) + requiredXpMultiplier * level;
requiredXpMemo.set(memoKey, result);
return result;
}
```

# Math comes to the rescue - maybe

This was already a lot better in terms of speed, but we were going to store a lot of values in that map, and I was
confident that there was more room for improvement. I went back to my original `f`

function and wrote it as a series:
$a_x = a_{(x - 1)} + (x - 1) * m$, where $a_1 = n$ and $x > 1$.

Calculating the first few terms of this series, we get:

$$ a_1 = n \newline a_2 = n + m \newline a_3 = n + 3m \newline a_4 = n + 6m \newline a_5 = n + 10m $$

At this point, my brain flashed me back throughout this fall when I did recurring series in math class. Unfortunately, other than a few specific cases, class had only really taught us how to “guess” a closed-form formula, and prove it using mathematical induction. Looking back, I’m a bit disappointed in myself for not trying that out more, but I digress.

I noticed that in my series, only the coefficient of the `m`

term was changing, and only depending on `x`

. As such,
I now knew that I could isolate the logic for calculating the coefficient of the `m`

term into its own function,
and only that would need to be recursive. Since that function would not rely on the values of `n`

and `m`

, the
memoization was going to be a lot more powerful. I ended up with this:

```
const multiplifierCoefficientMemo = new Map<number, number>();
function calculateMultiplifierCoefficient(level: number): number {
if (multiplifierCoefficientMemo.has(level)) {
return multiplifierCoefficientMemo.get(level)!;
}
if (level === 1) {
return 0;
}
const result = calculateMultiplifierCoefficient(level - 1) + level;
multiplifierCoefficientMemo.set(level, result);
return result;
}
export function calculateRequiredXp(settings: GuildSettings, level: number): number {
const { requiredXpBase, requiredXpMultiplier } = settings;
if (level === 1) {
return requiredXpBase;
}
return requiredXpBase + level * requiredXpMultiplier * calculateMultiplifierCoefficient(level);
}
```

# OEIS to the rescue

Across the 2 days I worked on this, I was chatting with some friends about it, and around this point one of them suggested that I should plug my series into oeis, which I didn’t even know existed.

So, looking at our current `calculateRequiredXp`

, we have:

$$ n, m \in \mathbb{N*} \newline f, g: \mathbb{N*} \rightarrow \mathbb{N} \newline g(x) = \begin{cases} 0 & x = 1 \newline g(x - 1) + x & x > 1 \end{cases} \newline f(x) = n + x * m * g(x) $$

`g`

written out as a recurring series is $a_x = a_{(x - 1)} + x - 1$, where $a_1 = 0$ and $x > 1$.

Our first few terms are: `0, 1, 3, 6, 10, 15`

. I plugged this into oeis, and wouldn’t ya know it,
this is the A000217 sequence, which gets us this closed-form formula: $\frac{n * (n - 1)}{2}$

Plugging this back into our original function, we have:

$$ n, m \in \mathbb{N*} \newline f: \mathbb{N*} \rightarrow \mathbb{N*} \newline f(x) = n + m * \frac{n * (n - 1)}{2} $$

and in TypeScript land:

```
export function calculateRequiredXp(settings: GuildSettings, level: number): number {
const { requiredXpBase, requiredXpMultiplier } = settings;
return requiredXpBase + (requiredXpMultiplier * (level * (level - 1))) / 2;
}
```

# Conclusion

Even though I couldn’t figure out the closed-form formula myself, I’m still pretty happy about my thought process throughout this seemingly simple task. I’m particularly entusiasthic about the fact that I was able to use my math knowledge to solve a real-world problem, and I’m looking forward to using it even more in the future.

It’s also particularly gratifying to see that my code is a lot more efficient now.