数学研发论坛

 找回密码
 欢迎注册
楼主: 裴进兵

[猜想] 我自己琢磨的,恳请大家帮忙论证·

[复制链接]
 楼主| 发表于 2015-6-14 20:26:17 | 显示全部楼层
对一个正整数n,可能分解成如下几种情况
                 n=2a·3b·n1·n2·…·nk+d, d=0 or ±1
       正整数n i ( i=1,2,…,k ) 亦为上面形式的分解。就是说,n最后分成解成只有数字1、2、3组成的算式.
例如:
       56=15625=23·32 (23·33+1) +1
       a(15625)=2·3+3·2+2·3+3·3+1+1=29

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

点评

可以加减超过1的。3^15以内发现加减4的,即a(n+4)=a(n)+4或者a(n+4)=a(n)-4. 加减3的比比皆是。  发表于 2015-6-19 09:45
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-18 23:31:25 | 显示全部楼层
zhouguang 发表于 2015-6-11 15:54
算了下,n≤339322的时,a(n)≤40。M的代码如下:
ss = {{1}};...

我的M代码如下(计算到n=315为例),与@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的规模。用上面的程序算到315=14348907 , 已经穷尽k=45, 并且出现的最大k值为52.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 02:10:04 | 显示全部楼层
观察315以内的数据,发现了很多长为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}(递降)
在315以内没有发现6连段。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 09:47:31 | 显示全部楼层
裴进兵 发表于 2015-6-14 20:26
n的分解式中,各层级2的幂方和3的幂方只可以相乘,不可以相加减,加减的d不超过1

这个不正确。a(n+d)=a(n)±a(d)的情况,有d>1的情况。
在10000以内,至少d=2的情况我们知道比比皆是,虽然都可以化为加减1的形式。
在315以内,更是发现了更大的d, d=3比比皆是,d=4 也有几例。当a(n+d)=a(n)+3或4时,n+2可能只有(n)+(2)一种分解模式。
例如1671059~1671063的一段就是如此:
na(n)c(n)n的因子分解四则分解式一分解式二
1671059424213·191·673(26·3-1)·(4·37+1)No
167106043443·4·5·27851(26·3-1)·(4·37+1)+1No
167106144457·238723(26·3-1)·(4·37+1)+2No
167106245452·835531
167106344443·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=(25·3+1)·(2·37-1)+2.

d=3不可转化减小的最小两例(两例皆素数)是
5688679=5688676+3=(25·32+1)·(39+1)+3.
8561963=8561960+3=(24·32+1)·(310-1)+3.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 14:22:11 来自手机 | 显示全部楼层
b(n)的计算很简单,动态规划就行。但是a(n)由于牵涉到减法,小数据可能依赖于大数据,完全相同的算法不可用。如果计算出n个1能表达出的整数的集合,空间复杂度很大,要逼近n4/3,而且集合的表示效率不是很高。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 14:28:55 来自手机 | 显示全部楼层
首先容易证明a(n)≥3log3(n).另外整数可表示为每位都是1或-1的三进制表示,如5=32-3-1.由此可得a(n)≤4log3(n)+3
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 14:34:03 来自手机 | 显示全部楼层
上面不等式可以近似估计出,如果对于某个 n, 如果我们需要拆分成 n+k 和 k 表示的差,对充分大的n, k不大于3n 1/3.
特别的容易得出n≥6时必然k<n
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 14:41:26 来自手机 | 显示全部楼层
然后证明如果n的所以最优拆分最后一步都是n+k的拆分和k的拆分差的形式,那么n+k的最优拆分必然可以有乘法拆分的或两个不超过n的数的加法拆分
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 14:47:12 来自手机 | 显示全部楼层
然后利用上面性质我们就可以类似按顺序计算a(n),只是计算中对于用到减法模式,我们只需要穷举部分,而且只使用当前已知最优值即可以
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2015-6-19 14:54:17 来自手机 | 显示全部楼层
初始化a(n)为b(n)范围最大到N+3N1/3. 然后对每个不小于6的n,依次重新计算最优的a(n),如果发现得到更好的a(n),再利用加法和乘法公式更新大于n的那些数的a(n)(假设将后面的数分解为n加上或乘上一个),时间复杂度为O(n2)空间复杂度为O(n)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-6-26 12:40 , Processed in 0.075447 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表