Shortest representation of an Underload number
Python 2.7 - 87 84 92

u=lambda n:n&gt;1and min([u(i)+u(n/i)for i in range(2,n)if n%i&lt;1]+[':'+u(n-1)+'*'],key=len)or''


Explanation:
This is a pretty straightforward solution. It recursively tests all possible representations of n as either the product of two numbers or as :(n-1)*, and then finds the minimum length solution. range(2,n) is necessary so that the recursion has bounded depth, and n&lt;2 gives the base case.

Notes:
i and n/i are the two factors of n. The ... and ... or ... replacement for ... if ... else ... doesn't work because '' evaluates to false. min of strings gives one of the shortest strings. Python 2.7 saves 1 character by using / instead of //.

Edit: Moved the base case to the back of the expression, allowing me to use ... and ... or ... and shave a couple spaces.

Test cases:

u(1)
''
u(5)
'::*:**'
u(49)
'::*:*:*:*::***'