Shortest representation of an Underload number Flavour text

The stack-based esolang Underload has some interesting ties to functional programming. One of them is its treatment of the numerical datatype&mdash;like the lambda calculus, you represent the natural number N by a function which perform an action N times.

To make things simple, we will only consider only the following subset of Underload commands:


: - This command duplicates the top item on the stack.
* - This command concatenates the top two items on the stack into a single item.


We define an Underload numeral N as a string of : and * which, when executed, consume the top item on the stack, and produce N copies of that item concatenated together. Some examples:


There are no Underload numerals 0, -1, 1/2, &pi;.
The empty string  is the Underload numeral 1, because it leaves the stack untouched.
:* is the Underload numeral 2, because it duplicates the top item, and then concatenates those two copies together into a single item: (A):* = (A)(A)* = (AA).
::** is the Underload numeral 3: (A)::** = (A)(A):** = (A)(AA)* = 
(AAA).
:::*** is the Underload numeral 4.
:*:* is also the Underload numeral 4: (A):*:* = (AA):* = (AA)(AA)* = (AAAA).


In general, you will find that, if M and N are the Underload numerals M and N, then :N* is the numeral N+1, and MN is the numeral M&times;N.

The challenge

Your task is to write the shortest program (taking input on STDIN) or function (taking input via argument) which produces the shortest representation of the Underload numeral for its input as a string. That is to say, if the input is a positive natural number N &gt; 1, you must produce an Underload numeral N whose length in characters is less than or equal to that of every other Underload numeral N.

Sample inputs and outputs: ("Input - OUTPUT.")


1 - .
2 - :*.
5 - ::*:** (2&times;2+1).
7 - ::*::*** (2&times;3+1) or :::**:** (3&times;2+1).
33 - ::*:*:*:*:** (2&times;2&times;2&times;2&times;2+1).
49 - ::*:*:*:*::*** (16&times;3+1, length 14) but not ::*::***::*::*** (7&times;7, length 16).


If the input is not a positive natural number, you are free to return an error, produce undefined behaviour, or even fail to terminate. An explanation of your submission's method of finding the answer is appreciated.

Standard loophole restrictions apply: no extra input, no web requests, output/return value must be exactly the answer and not an infinite random stream of : and *, etc.
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)
'::*:*:*:*::***'