Arithmetic Games

(1) Show that every positive integer is a sum of one or more numbers of the form 2^r * 3^s, where r and s are nonnegative integers and no summand divides another

For example,

1 = 2^0 * 3^0, r = s = 0
2 = 2^1 * 3^0, r = 1, s = 0
3 = 2^0 * 3^1, r = 0, s = 1
4 = 2^2 * 3^0, r = 2, s = 0

How would you write 5?

23 = 9 + 8 + 6

Actually, we can write, 5 = 2 + 3 = 1 + 4

So, 5 = 2 + 3 = (2^1 * 3^0) + (2^0 * 3^1)
and, 5 = 1 + 4 = (2^0 * 3^0) + (2^2 * 3^0)

Naturally, a formal proof will be needed.

The formal proof: we proceed by induction.
That is to say, we suppose all integers less than n-1 can be represented.
Then we face two cases:
(1) If n is even, then, ...
(2) If n is odd, then, ...

P.S. This problem is originally due to Paul Erdos. Note that the representations need not be unique: for instance,

11 = 2 + 9 = 3 + 8

(2) Find the smallest prime p such that the digits of p (in base 10) add up to a prime number greater than 10.