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!

About these ads

Pages: 1 2

9 Responses to “The Twelve Days Of Christmas”

  1. Dan said

    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.

  2. Matthew Feng said

    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.

  3. Matthew Feng said

    An edit to my previous post, 2**n-1 doesn’t work, sorry.

  4. Ben said

    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

  5. Ben E Oliver said

    sum $ map (\x -> (1+x) * (x/2)) [1..12]

  6. [...] The Twelve Days Of Christmas (programmingpraxis.com) [...]

  7. [...] The Twelve Days Of Christmas (programmingpraxis.com) [...]

  8. Globules said
    import Data.List (genericLength, mapAccumL, intercalate)
    import Data.Ratio
    import RecMath.GaussElim
    import System.Environment
    
    -- For efficiency (and fun!), we can find a polynomial that is equivalent to the
    -- function totalGifts.  We calculate the differences between successive values
    -- of the function, differences of the differences, and so on.  For example,
    -- using our 12 days problem:
    -- 
    --   n       1   2    3     4     5 ...
    --   f(n)    1   4   10    20    35 ...
    --   d(1)      3   6    10    15 ...
    --   d(2)        3    4     5 ...
    --   d(3)           1     1 ...
    --   d(4)               0 ...
    -- 
    -- If the i'th difference is equal to 0 then we use the first i function values
    -- to construct a linear system of equations to solve for the coefficients of
    -- the polynomial.  The equations are generated by plugging into:
    -- 
    --   c   n^(i-1) + c   n^(i-2) + ... + c n + c  = f(n)
    --    i-1           i-2                 1     0
    -- 
    -- the i different values.  In our 12 days problem, this leads to:
    --
    --     a +   b +  c + d =  1
    --    8a +  4b + 2c + d =  4
    --   27a +  9b + 3c + d = 10
    --   64a + 16b + 4c + d = 20
    -- 
    -- Upon solving this system we get a=1/6, b=1/2, c=1/3 and d=0.  So, the
    -- resulting polynomial is:
    -- 
    --   1/6 n^3 + 1/2 n^2 + 1/3 n
    -- 
    -- Of course, all of the above depends on the ability to represent our function
    -- with a polynomial.
    -- 
    -- See http://www.math.cmu.edu/~bkell/21110-2010s/formula.html for more detail.
    
    -- Given a function, f, and an initial value, i, return the coefficients of a
    -- polynomial equivalent to the function.  It's assumed that f can be 
    -- represented by a polynomial.
    coefs :: (Integral a, Integral b) => (a -> b) -> a -> [Rational]
    coefs f i = let vs = values f i
                    sz = length vs
                    m = map (mkRow sz . fromIntegral . fst) vs
                    x = map (fromIntegral . snd) vs
                in linearSolve m x
      where mkRow len = scanl (*) 1 . replicate (len-1)
    
    -- Given a function, f, and an initial value, i, return the list of pairs, 
    -- [(i, f(i)), (i+1, f(i+1)), ..., (n, f(n))], sufficient to allow the
    -- calculation of the equivalent polynomial.
    values :: (Integral a, Eq b, Num b) => (a -> b) -> a -> [(a, b)]
    values f i = map (\k -> (k, f k)) [i..i+n-1]
      where n = genericLength $ last diffs
            diffs = takeWhile ((/=0) . last) . tail . scanl step [] $ map f [i..]
            step = flip $ scanl (-)
    
    -- Evaluate a polynomial at a given value.  The polynomial is represented by a
    -- list of coefficients.
    eval :: (Num a, Integral b) => [a] -> b -> a
    eval cs n = let n' = fromIntegral n in foldr (\l r -> l+n'*r) 0 cs
    
    showRat :: Rational -> String
    showRat r | denominator r == 1 = show $ numerator r
              | otherwise = show (numerator r) ++ "/" ++ show (denominator r)
    
    showPoly :: [Rational] -> String
    showPoly cs = let terms = snd $ mapAccumL (\n c -> (n+1, term c n)) 0 cs
                  in intercalate " + " $ filter (not . null) terms
      where term 0 _ = ""
            term c p = showRat c ++ "n^" ++ show p
    
    --------------------------------------------------------------------------------
    
    giftsOnDay :: [Int]
    giftsOnDay = 0 : [n | i <- [1..], let n = i + giftsOnDay !! (i-1)]
    
    totalGifts :: Int -> Int
    totalGifts n = sum $ take (n+1) giftsOnDay
    
    main :: IO ()
    main = do
      args <- getArgs
      let nDays = read $ head args :: Int
          tot = eval cs nDays
          cs = coefs totalGifts 1
      putStrLn $ "The total number of gifts after " ++ show nDays ++ " days is "
                 ++ showRat tot ++ "."
      putStrLn $ "A polynomial for the total number of gifts is " ++ showPoly cs
    

    When run, this produces:

    $ ./xmas 12
    The total number of gifts after 12 days is 364.
    A polynomial for the total number of gifts is 1/3n^1 + 1/2n^2 + 1/6n^3
    $ 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: