If my calculations are right, the perfect number should be e (2.718).

However we cannot use this number.

This condition actually is much easier because **all the integers larger than 3 can be broken into only 3s and 2s without 1s**.

For example

```
4 = 2 + 2
5 = 3 + 2
6 = 3 + 3
...
13 = 3 + 3 + 3 + 2 + 2
```

Whenever you **combine two 3s or a 3 and a 2, the product becomes smaller**. So you don't combine them.

For example:

```
16 = 3 + 3 + 3 + 3 + 2 + 2
or
16 = 6 + 6 + 2 + 2
or
16 = 6 + 5 + 5
because 6 < 3 * 3, 6 * 6 < 3 * 3 * 3 *3.
because 5 < 2 * 3, 5 * 6 < 2 * 3 * 3 *3.
```

**It is obvious you don't want a combination.**

Then how many 3s you want to have?

**As many as possible** unless you produce a 1. If you have a 1, then substitute one 3-and-1 pair with a 2-and-2 pair.

For example:

```
7 = 3 + 3 + 1 = 3 + 2 + 2
```

if you spare some room for 2s, the product becomes smaller again.

For example:

```
2 * 2 * 2 < 3 * 3
```

Then the solution is simple:

- Use as many 3 as possible
- Avoid 1

```
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n == 2:
return 1
elif n == 3:
return 2
k = n / 3
m = n % 3
if m == 1:
return 4 * (3 ** (k-1))
elif m == 2:
return 2 * (3 ** k)
else:
return 3 ** k
```