The Festival of 1 + n + f(n-1) Lights

mgcadmin 26-12-2024

As Hanukkah approached and I gathered my holiday supplies, I ran through my list to make sure I had everything I needed. Latkes? Check. Chcoclate Gelt? Double check. Menorah? Check. Candles? Check.... I think? How many am i going to need? Now, I could have just googled the answser like any sane person would do, but where is the fun in that? Besides, at this point the question meant more than the answer. 

To me their was only one way I was going to answer this question: with an algorithm.

For those out of the loop(no pun intended), Hanukkah lasts for eight (crazy!) nights. On each night, you light n candles for the nth night, plus one special candle, called the samos, which is used for lighting the other candles. This means on the first night you need two candles, the second night needs three candles and so on for eight nights.

With this in mind, we can easily compute the total number of candles we will need for all 8 nights using the following simple recursive algorithm:

#include <stdio.h>
#include <stdlib.h>

int candles(int n) {
	if (n < 1) {
        return 0;
    }
	return 1 + n + candles(n-1);
}

int main(int argc, char* argv[]) {
	printf("%d\n", candles(atoi(argv[1])));
}

And so I arrived my answer: I will need 44 candles to cover all 8 nights. All set!

Happy Hanukkah!

---