Any integer greater than or equal to 12 can be written as a sum of 4's and 5's

fours_and_fives.py

import collections
import functools

#https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

@memoized
def fours_and_fives(n):
   """
   Any integer greater than or equal to 12 can be written as as sum of 3's and 5's
   Simulation of proof by strong induction
   """
   assert(n >= 12)

   if n == 12:
      return [4, 4, 4]
   elif  n == 13:
      return [4, 4, 5]
   elif n == 14:
      return [4, 5, 5]
   elif n == 15:
      return [5, 5, 5]

   else:
      l = list(fours_and_fives(n - 4))
      l.append(4)
      assert(sum(l) == n)
      return l