The Twelve Days Of Christmas
December 25, 2012
If you calculated 78 gifts, try again. That’s the number of gifts given on the twelfth day, not the total number of gifts given over twelve days.
The sum of the numbers from 1 to n is n(n+1)/2; for n=12, that’s 78. But that is only the number of gifts given on the twelfth day.
The total number of gifts given on n days is the nth tetrahedral number. You can think of the triangle on a billiard table, with fifteen balls; stack ten balls on top of the fifteen, then stack six balls on top of the ten, then stack three balls on top of the six, and finally stack one ball on top of the three, for a total of 35 balls. In terms of our song, we have 1 gift on the first day, 2+1=3 gifts on the second day (a total of 4 gifts), 3+2+1=6 gifts on the third day (a total of 10 gifts), 4+3+2+1=10 gifts on the fourth day (a total of 20 gifts), 5+4+3+2+1=15 gifts on the fifth day (a total of 35 gifts), and so on.
The formula for the nth tetrahedral number is n(n+1)(n+2)/6, which is 364 for n=12. Here’s the program:
(define (xmas n)
(* n (+ n 1) (+ n 2) 1/6))
> (xmas 12)
364
You can run the program at http://programmingpraxis.codepad.org/Ti7hK8mt.
Merry Christmas!
This problem statement leaves some ambiguity, as the number of gifts given in N days depends exactly on which of the 12 days gifts were given. In addition to the parameter N, a consecutive range or non-consecutive set of days must be specified in order to know how many gifts were given in total.
Gifts that day: 2**n-1 or n(n+1)/2
Gifts total: n**2
At least I think that is what it is, assuming the following:
1. The number of gifts received is not modular, and
2. The gifts received = n + n-1 + n-2 + n-3 + … + 1.
An edit to my previous post, 2**n-1 doesn’t work, sorry.
Not so elegant solutions, the first is recursive,
— recursive
crimbo presents 0 = presents
crimbo presents days = crimbo (presents + loot) (days-1)
where loot = sum [1..days]
twelve_days = crimbo 0
— using map
f a b = (a + b) * ((1 + (b – a)) / 2)
tolv_dager days = sum $ map (f 1) [1..days]
*Main> twelve_days 12
364
*Main> tolv_dager 12
364.0
sum $ map (\x -> (1+x) * (x/2)) [1..12]
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]
My Java solution here.
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]
When run, this produces:
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]
[…] The Twelve Days Of Christmas (programmingpraxis.com) […]