我自己琢磨的，恳请大家帮忙论证·

裴进兵

对一个正整数n，可能分解成如下几种情况
                 n=2^a·3^b·n₁·n₂·…·n_k+d, d=0 or ±1
       正整数n _i ( i=1,2,…,k ) 亦为上面形式的分解。就是说，n最后分成解成只有数字1、2、3组成的算式.
例如：
       5⁶=15625=2³·3² (2³·3³+1) +1
       a(15625)=2·3+3·2+2·3+3·3+1+1=29

在n的分解式中，各层级的2的幂方和3的幂方只可以相乘，不可以相加减，加减的d不超过1。

hujunhua

zhouguang 发表于 2015-6-11 15:54
算了下，n≤339322的时，a(n)≤40。M的代码如下：
ss = {{1}};...

我的M代码如下（计算到n=3¹⁵为例），与@zhouguang的算法完全不同。

1. n=1;
   
2. mw={1,2,3};
   
3. mw0[x_]:=Module[{m=x},
   
4.   ds=Divisors[m];
   
5.   l=(1+Length@ds)/2;
   
6.   ds1=ds[[2;;Floor@l]];
   
7.   ds2=ds[[-2;;Ceiling@l;;-1]];
   
8.   If[PrimeQ[m],m,Min@(mw[[ds1]]+mw[[ds2]])]]
   
9. Do[n=3n;mw1=mw0/@Range[n,2n];
   
10.   Do[mw1[[i]]=Min[mw1[[i]],mw1[[i-1]]+1]; mw1[[-i]]=Min[mw1[[-i]],mw1[[-i+1]]+1],{i,2,Length@mw1-1}];
    
11.   mw=mw~Join~Rest@mw1;
    
12.   mw1=mw0/@Range[2n,3n];
    
13.   Do[mw1[[i]]=Min[mw1[[i]],mw1[[i-1]]+1]; mw1[[-i]]=Min[mw1[[-i]],mw1[[-i+1]]+1],{i,2,Length@mw1-1}];
    
14.   mw=mw~Join~Rest@mw1;
    
15.   Print[n],{14}]
    
16. mw

复制代码

我的电脑用zhouguang的程序只能算到k=25的规模。用上面的程序算到3¹⁵=14348907 , 已经穷尽k=45, 并且出现的最大k值为52.

hujunhua

观察3¹⁵以内的数据，发现了很多长为4的连续自然数段，以及3个长为5的连续自然数段。这在10000以内是没有发现的。
最早的递降四连段是a(40037)~a(40040)={34,33,32,31}
最早的递升四连段是a(111554)~a(111557)={34,35,36,37}
3个五连段分别是
a(9573958)~a(9573962)={46,47,48,49,50},
a(12813850)~a(12813854)={47,48,49,50,51},
a(6371698)~a(6371702)={49,48,47,46,45}(递降)
在3¹⁵以内没有发现6连段。

hujunhua

裴进兵 发表于 2015-6-14 20:26
n的分解式中，各层级2的幂方和3的幂方只可以相乘，不可以相加减，加减的d不超过1

这个不正确。a(n+d)=a(n)±a(d)的情况，有d>1的情况。
在10000以内，至少d=2的情况我们知道比比皆是，虽然都可以化为加减1的形式。
在3¹⁵以内，更是发现了更大的d, d=3比比皆是，d=4 也有几例。当a(n+d)=a(n)+3或4时，n+2可能只有(n)+(2)一种分解模式。
例如1671059~1671063的一段就是如此：

n	a(n)	c(n)	n的因子分解	四则分解式一	分解式二
1671059	42	42	13·191·673	(26·3-1)·(4·37+1)	No
1671060	43	44	3·4·5·27851	(26·3-1)·(4·37+1)+1	No
1671061	44	45	7·238723	(26·3-1)·(4·37+1)+2	No
1671062	45	45	2·835531	略
1671063	44	44	3·557021	略

表中c(n)=min{a(n/d)+a(n)}(d跑遍n的真因子）。对于素数n， c(n)定义为n.
若a(n)<c(n),  n的四则分解式必是(n-d)+(d)的模式（d可取负值）。（如果n非素数，这就是一个压缩点。）
若a(n)=c(n),  n的四则分解式必有(n/d)·(d)的模式（d是n的真因子）

由于1671060和1671061都是压缩点, 所以1671060，1671061只能分解为1671059+1和1671059+2。
其中1671061可分解为1671060+1，但由于1671060只有1671059+1，故1671061实际上只有1671059+2，d=2不可转化减小。

经过搜索，d=2不可转化减小的最小例子是
424183=424181+2=(2⁵·3+1)·(2·3⁷-1)+2.

d=3不可转化减小的最小两例（两例皆素数）是
5688679=5688676+3=(2⁵·3²+1)·(3⁹+1)+3.
8561963=8561960+3=(2⁴·3²+1)·(3¹⁰-1)+3.

mathe

b(n)的计算很简单，动态规划就行。但是a(n)由于牵涉到减法，小数据可能依赖于大数据，完全相同的算法不可用。如果计算出n个1能表达出的整数的集合，空间复杂度很大，要逼近n^4/3,而且集合的表示效率不是很高。

mathe

首先容易证明a(n)≥3log₃(n).另外整数可表示为每位都是1或-1的三进制表示，如5=3²-3-1.由此可得a(n)≤4log₃(n)+3

mathe

上面不等式可以近似估计出，如果对于某个 n, 如果我们需要拆分成 n+k 和 k 表示的差，对充分大的n, k不大于3n ^1/3.
特别的容易得出n≥6时必然k<n

mathe

然后证明如果n的所以最优拆分最后一步都是n+k的拆分和k的拆分差的形式，那么n+k的最优拆分必然可以有乘法拆分的或两个不超过n的数的加法拆分

mathe

然后利用上面性质我们就可以类似按顺序计算a(n),只是计算中对于用到减法模式，我们只需要穷举部分，而且只使用当前已知最优值即可以

mathe

初始化a(n)为b(n)范围最大到N+3N^1/3. 然后对每个不小于6的n,依次重新计算最优的a(n),如果发现得到更好的a(n),再利用加法和乘法公式更新大于n的那些数的a(n)(假设将后面的数分解为n加上或乘上一个），时间复杂度为O(n²)空间复杂度为O(n)