How many total gifts in the twelve days of christmas if we extend 12 to any number?

Question

I got this question today in an interview: write a function to calculate the total number of gifts received for any day in the 12 days of christmas song. I wrote a simple function using a for() loop in c#'ish code that worked. Then the interviewer asked me to extend it to any number of days. The conversation then turned to how to optimize the loop. Apparently there's a cool math trick that will do this within the limits of whatever your integer is. Anyone know what it is and what it's called? Any language is ok and a reference to the algorithm would be fabuloso.

Answers that use recursion are NOT what I'm looking for.

EDIT: Answer for day 2 is 4 gifts total, not 3 since I will have 2 Trees (1 from today, 1 from yesterday) and 2 partridges. On day 12 I'll have received a total of 364. I want the formula that lets me input 12 and get 364.

Answer 1

• On the first day, you get 1.
• On the second day, you get 1 + 2.
• On the third day, you get 1 + 2 + 3.
• ...
• On nth day, you get 1 + 2 + 3 + ... + n.

The sum 1 + 2 + ... + n is n(n+1)/2. So the total number, T(N) is the sum of n(n+1)/2 for n in 1..N, where N is the number of days.

Now, n(n+1)/2 = n^2 / 2 + n / 2, and sum of n^2 for n in 1..N is N(N+1)(2N+1)/6, so you get:

T(N) = N(N+1)(2N+1)/12 + N(N+1)/4
     = N(N^2 + 3N + 2) / 6

No loops. No recursion.

Answer 2

The $P$-th type of present (where the $1$st is partridges, the $2$nd is turtle doves, etc.) comes in quantities of $P = \sum_{X = 1}^{P} 1$.

On day $D$, you receive presents of type $1$ through $D$, for a total of $\sum_{P = 1}^{D} \sum_{X = 1}^{P} 1$ many presents on that day.

And so, if the days run from $1$ through $N$ (canonically, $N$ is 12, but our interest now is in allowing it to vary), you receive overall $\sum_{D = 1}^{N} \sum_{P = 1}^{D} \sum_{X = 1}^{P} 1$.

This counts the number of non-decreasing triples $1 \leq X \leq P \leq D \leq N$.

This is the same as the number of increasing triples $1 \leq X < P + 1 < D + 2 \leq N + 2$.

So the answer is $\binom{N + 2}{3} = \frac{(N + 2)(N + 1)N}{6}$.