求将一个正整数分成几个正整数之和，其最小公倍数最大的问题

sunwukong

这个问题我记得 csdn 有过讨论的，不过我现在找不到了。印象中 csdn 的讨论也没找出一个算法，最好的结果是有人把 2000 以内的结果列出来。题目是：

已知一个正整数 $N$，把 $N$ 化为 $m$ 个正整数之和：

$N = a_1+a_2+…+a_m$，

$a_1$、$a_2$、…、$a_m$ 的最小公倍数是 $L$：

$L=LCM{a_1, a_2, …, a_m}$，

求 $L$ 最大时的值以及此时的划分方案。

我想到的一些思路：

记 $N$ 对应的最大的 $L $ 为 $f(N)$ 。

如果某个正整数 $Q$，有

       $f(Q-1) \quad \quad < \quad \quad   f(Q)=f(Q+1)=f(Q+2)=…=f(Q+t) \quad  \quad  < \quad  \quad  f(Q+t+1)$，

则 $Q$ 的最优划分方案唯一，形式如下：

$p_1^(k_1)$、$p_2^(k_2)$、……、$p_m^(k_m)$，

其中 $p_1$、$p_2$、…、$p_m$ 是 $m$ 个素数，$k_1$、$k_2$、…、$k_m$ 是 $m$ 个正整数，而且

   $p_1<p_2<…<p_m$  ，
   $k_1>=k_2>=…>=k_m$（当 $p_1!=2$ 时）
或 $k_1<=2、k_2>=k_3>=…>=k_m$（当 $p_1=2$ 时）。

$Q+1$、$Q+2$、…、$Q+t$ 的最优划分方案不唯一，但都是在 $Q$ 的划分方案再添上任意1个或几个正整数得来。

这可以通过几步来证明：

（1）如果最优划分方案唯一，则划分的各个数之间两两互素。
（2）如果$a>b>=e$，其中 $e$ 是自然底数，则 $a^b<b^a$，
（3）…… （还没想好）

[ 本帖最后由 sunwukong 于 2008-9-12 11:58 编辑 ]

无心人

n  = 2  1 + 1 L = 1
n = 3 1 + 2 L = 2
n = 4 1 + 3 L = 3
n = 5 2 + 3 L = 6
n = 6 1 + 2 + 3 L = 6
n = 7 3 + 4 L = 12
n = 8 3 + 5 L = 15
n = 9  4 + 5 L = 20
n = 10 2 + 3 + 5 L = 30

sunwukong

n =2，L =2，不拆分
n=3， L=3，不拆分
n=4， L=4，不拆分

mathe

http://blog.csdn.net/mathe/archive/2006/11/27/1416907.aspx