---
# System prepended metadata

title: NCPC 2018 初賽 Problem C - Partition an Integer
tags: [程設專題]

---

<style>
  body[style],
  body[style *= "background-color: #f3f3f3"]{
    background-color: #f3f3f3 ! important;
  }
</style>

# NCPC 2018 初賽 Problem C - Partition an Integer
###### tags: `程設專題`

:::spoiler partition of 11
```
                      lcm
11  = 9 + 1 + 1    ---  9
    = 8 + 2 + 1    ---  8
    = 7 + 3 + 1    --- 21
    = 7 + 2 + 2    --- 14
    = 6 + 4 + 1    --- 12
    = 6 + 3 + 2    ---  6
    = 5 + 5 + 1    ---  5
    = 5 + 4 + 2    --- 20
    = 5 + 3 + 3    --- 15
```
:::

## 題目
$n$ 是一個大於 $2$ 的正整數，給定 $n$，找出三個正整數 $(a, b, c)$，滿足 $n=a+b+c$ 且 $𝑙𝑐𝑚(𝑎,𝑏,𝑐)$ 最小。

$2 < n \le   2^{31}$

## 符號定義
- Partition(拆分)：
  - When $a+b+c=n$, $(a,b,c)$ is a partition of n.
- $f(n)$：
  - $f(n)=(a,b,c)$ when $(a,b,c)$ is the optimal partition of n.


## 觀察

$\forall n \in \Bbb N \land n >2$

#### $lcm(f(n))$ 上界
1. $n$ is odd
$n = 2k + 1 = 1 + k + k\\
\Rightarrow lcm(f(n)) \le lcm(1,k,k) = k = \dfrac{n-1}{2}$
2. $n$ is even
$n = 2k + 2 = 2 + k + k\\
\Rightarrow lcm(f(n)) \le lcm(2,k,k) \not= k = \dfrac{n-2}{2}$
$\because lcm(2,k,k) = 
\begin{cases}
2k,\quad k\text{ is odd}\\
k,\quad k\text{ is even}\\
\end{cases}$
    - $n$ is a multiple of 2 but is NOT a multiple of 4
    $\begin{split}
      n &= 2(2k') + 2\\
        &=4k'+2\\
        &= 2 + 2k' + 2k'\\
    \end{split}$
    $lcm(f(n)) \le lcm(2, k',k') = \dfrac{n-2}2$
    - $n$ is a multiple of 4
    $\begin{split}
      n &= 2(2k' -1) + 2\\
        &= 4k'\\
        &= k' + k' + 2k'\\
    \end{split}$
    $lcm(f(n)) \le lcm(k',k', 2k') = \dfrac{n}2$

#### $lcm(f(n))$ 下界
if $n$ is a multiple of 3
$\Rightarrow n = k + k + k\\
\Rightarrow f(n) = (k, k, k),  lcm(f(n)) = k$

### 小結
$\dfrac n3 \le lcm(f(n)) \le \dfrac n2$


## Solution in $O(n^2)$

### Idea
WLOG, let $a \le b \le c \Rightarrow lcm(a,b,c) \ge c$
Let $k = lcm(a,b)$
$lcm(a,b,c) = lcm(lcm(a,b), c) = lcm(k,c)$

if $lcm(a,b,c) = lcm(k,c) = c \Rightarrow k|c$

### Pseudocode
```cpp=
f(n):
  (A,B,C) = (∞,∞,∞)
  for (c = n-2;c >= n/3;c--):
    for (b = c, a = n-b-c; a <= b; a++, b--):
      if (a <= 0 || c % a != 0) continue;
      k = lcm(a,b)
      if (c % k == 0):
        if c < C:
          (A,B,C) = (a,b,c)
        break;
  return (A,B,C)
```
ref. [wiki LCM](https://zh.m.wikipedia.org/zh-tw/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8)

## output
:::spoiler result of $n < 50$
```
 3:  1  1  1
 4:  1  1  2
 5:  1  2  2
 6:  2  2  2
 7:  1  3  3
 8:  2  2  4
 9:  3  3  3
10:  2  4  4
11:  1  5  5
12:  4  4  4
13:  1  6  6
14:  2  6  6
15:  5  5  5
16:  4  4  8
17:  1  8  8
18:  6  6  6
19:  1  9  9
20:  4  8  8
21:  7  7  7
22:  2 10 10
23:  1 11 11
24:  8  8  8
25:  5 10 10
26:  2 12 12
```
```
27:  9  9  9
28:  4 12 12
29:  1 14 14
30: 10 10 10
31:  1 15 15
32:  8  8 16
33: 11 11 11
34:  2 16 16
35:  7 14 14
36: 12 12 12
37:  1 18 18
38:  2 18 18
39: 13 13 13
40:  8 16 16
41:  1 20 20
42: 14 14 14
43:  1 21 21
44:  4 20 20
45: 15 15 15
46:  2 22 22
47:  1 23 23
48: 16 16 16
49:  7 21 21
50: 10 20 20
```
:::

![](https://i.imgur.com/wbjVxkG.png)![](https://i.imgur.com/WB4lJ2A.png)


### Lemma 1
::: info
**Lemma 1. (Optimal Partition for Primes)**
$f(p) = (1,b,b) = (1,\dfrac{p-1}2,\dfrac{p-1}2)$, where $p \ge 3$ and $p$ is a prime number.
:::

**Pf. (by contradiction)**
Suppose that $(1+2x,b-x,b-x)$ is a *better* partition of $p$ where $x,b-x\in\Bbb N$ 
such that $lcm(1+2x,b-x,b-x) < lcm(1,b,b) = b$
$lcm(1+2x,b-x,b-x) = lcm(1+2x,b-x) < b\Leftrightarrow 1 + 2x \mid b-x$
Let $b-x=(1+2x)k$, $k \in \Bbb N$
$\begin{split} \\
p &= (1+2x) + (1+2x)k + (1+2x)k \\
&= (1+2x)(1+2k) \Rightarrow p \text{ is not a prime number}
\end{split}$

Therefore $(1,b,b)$ is the optimal partition for $p$.

### Lemma 2
$\begin{split}
R &= R_1 + R_2 + R_3\\
  &= dr_1 + dr_2 + dr_3,\ d \mid r_1 \land d \mid r_2 \land d \mid r_3\\
  &= d(r_1 + r_2 + r_3)\\
  &= d\cdot r
\end{split}$

:::info
**Lemma 2.**
When $R$ has optimal partition $(R_1, R_2, R_3)$, then
$f(R)=d \cdot f(r)$
where $R = d\cdot r$ and $d$ is a common factor of $r_1, r_2$ and $r_3$.
:::

**Pf. (by contradiction)**
Suppose there exists a partition $(r_1',r_2',r_3')$ such that $lcm(r_1',r_2',r_3') < lcm(r_1,r_2,r_3)$ then by assumption we have

$lcm(r_1',r_2',r_3') < lcm(r_1,r_2,r_3)$
$\Rightarrow d \cdot lcm(r_1',r_2',r_3') < d \cdot lcm(r_1,r_2,r_3)$
$\Rightarrow lcm(dr_1',dr_2',dr_3') < lcm(dr_1,dr_2,dr_3)$
$\Rightarrow(dr_1',dr_2',dr_3')$ is a better partition for $R$, a contradiction.

:::warning
When $R=d\cdot r$, we know $f(R)\Rightarrow d\cdot f(r)$
ex.
$\begin{split}
f(24) &= (8,8,8)\\
      &= 8\cdot (1,1,1)\\
\Rightarrow f(3) &= (1,1,1)
\end{split}$

How about $d\cdot f(r)\Rightarrow f(R)$?

ex.
$\begin{split}
f(4) &= (1,1,2)\\
6\cdot f(4) &= 6\cdot(1,1,2)\\
6\cdot f(4) &= (6,6,12)\\
f(24) &\not= (6,6,12)
\end{split}$
:::

### Formula Derivation
For $n\ge 3$, if $n$ has an optimal partition 

$\begin{split}
f(n) &= (n_1, n_2, n_3)\\
  &= d(n_1', n_2', n_3')\\
\end{split}$

where $d$ is a common factor of $n_1', n_2'$ and $n_3'$.

Let $p$ be a prime number, $p \ge 3$, where $p = n_1'+n_2'+n_3'$.

By **Lemma 2**, $f(n) = d\cdot f(p)$ where $f(p)$ is the optimal partition of $p$.
By **Lemma 1**, we obtain that $f(p) = (1,b,b)$ where $b=\dfrac{p-1}2$.
Then

$\begin{split}
f(n) &= d\cdot f(p)\\
    &= d\cdot(1,b,b)\\
    &= (d,bd,bd)
\end{split}$
$\Rightarrow f(n)$ must be in form $(d,bd,bd)$ where $\begin{cases}
d = \dfrac np,\\
b = \dfrac{p-1}2.
\end{cases}$

$\begin{split}
lcm(d, bd, bd)&= bd\\
              &= \dfrac{p-1}2 \cdot \dfrac np\\
              &= \dfrac n2\cdot(1-\dfrac1p)
\end{split}$
$\because\dfrac n2$ is a constant,
$\therefore$ minimize $p$ cause the minial $lcm(d, bd, bd)$.

### Conclusion 
$\forall n = p\cdot d$
$\because$ choose $p=2$ is illegal
$\therefore$ rewrite $n = 2^k\cdot x$ where $x$ is odd.

Thus, $\forall n = 2^k\cdot x ,x \not= 1$
$f(n) = 2^k\cdot f(x)$

Def. $f(1) = (\dfrac14, \dfrac14, \dfrac12)$

$f(x)=\begin{cases}
(1, \dfrac{x-1}2, \dfrac{x-1}2)&, &x \in \text{prime numbers}\\
\dfrac xp\cdot f(p)&, &x \notin \text{prime numbers} \land x \not= 1, p\text{ is the smallest prime factor of } x\\
(\dfrac14, \dfrac14, \dfrac12)&, &x=1
\end{cases}$
