数学研发论坛

 找回密码
 欢迎注册
楼主: hujunhua

[提问] 格点正方形,可否发现一个新数列?

[复制链接]
发表于 2012-6-12 11:22:02 | 显示全部楼层
90# hujunhua
昨晚上睡觉前,发现在 n=k-1 的最优图案的基础上 构造 n=k的最优图案是可行的,且比较方便,
需要考虑的情况并不复杂,粗略分析大致就是三角数 。
有时间我写个程序, 很自信能打破很多记录。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-13 00:01:50 | 显示全部楼层
91# wayne
我的思路:
将n*n 划分4个区域,其中2个区域是正方形,填充以最优的图案,另2个长方形区域是备用的。当存在跨区域的正方形时,就在长方形区域里去掉相应的点,以破坏 这种跨区域正方形的存在性。
因为跨区域的正方形不会很多的,所以在长方形区域补充的红色点也不会很多,最终得到的图案应该很优。

比如,将 n=10 ,划分成 8*8 , 2*2两个正方形区域和 2*8的两个长方形区域。
对8*8 , 2*2的两个正方形区域填充以最优图案, 然后使用贪心策略 对长方形区域填充红色点。


不知是否可行?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-6-13 21:33:48 | 显示全部楼层
这个思路或许可以得到不等式
a(m+n)>a(m)+a(n)
由这个不等式则可以得到 a(n)>O(n)
这个结果很弱。 为了得到更强的结果,或许需要将问题扩展为m×n矩形点阵,看看是否成立不等式
a(m+n, m+n)≥a(m, m)+a(m, n)+a(n, n)或者等式
考虑到二次型$m^2+mn+n^2$与$\sqrt3$的关系,如果上述不等式能成为等式,就可将数列a(n,n)A194082扯上关系

评分

参与人数 1鲜花 +12 收起 理由
wayne + 12 很有建设性!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-13 22:51:55 | 显示全部楼层
93# hujunhua
, 是哈,
将问题扩展为m×n矩形点阵 应该更利于展开讨论。

针对较小的n,m,我们不妨 先用程序算出 a(n,n),a(m,m),a(n,m),
然后再算出a(n,m) 验证一下 这个不等式的强弱性。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-6-30 15:07:51 | 显示全部楼层
很热闹。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-19 09:33:38 | 显示全部楼层
接$83#$:

通过更长时间地运行程序,继续在$n=12$、$13$、$14$、$15$、$16$上取得了突破。

目前的结果如下:

$n=9$:


$n=10$:


$n=11$:


$n=12$:
Square_free_12_67.PNG

$n=13$:
Square_free_13_76.PNG

$n=14$:
Square_free_14_85.PNG

$n=15$:
Square_free_15_95.PNG

$n=16$:
Square_free_16_105.PNG

另外,$n=7$的所有方案已经枚举完,结果为$27$,否定了该数列是三角形数的猜想。

评分

参与人数 1威望 +8 金币 +8 贡献 +8 经验 +8 鲜花 +8 收起 理由
hujunhua + 8 + 8 + 8 + 8 + 8 向着A194082又迈进一步

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-19 10:15:22 | 显示全部楼层
A194082是一个上界,目前的结果并没有达到。
在$83#$之前,$n=0$到$n=8$的结果与$A194082$一致。
而$83#$的结果在$n=9$也与$A194082$一致了,但是在$n=10$以上还不一样(比$A194082$小)。

目前的结果表明A194082这个上界太松了,可能存在一个比A194082更紧的上界。 KeyTo9_Fans 发表于 2012-6-11 21:39


每前进一步都要付出巨大的努力,而在n=11离$A194082$还差3步(鸿沟啊!),感觉在n=11时能脱离$A194082$。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-19 10:26:11 | 显示全部楼层
{1, 6, 20, 50, 105, 196, 336, 540}
http://oeis.org/A002415
一个很笨的但是有效的程序:
Table[Length@
  Select[Select[
    Select[Sort /@
      Subsets[Flatten,
        1], {4}], #[[2]] + #[[3] ...
wayne 发表于 2012-5-29 14:13

我被彻底搞晕了,嵌套这么多层!!!!!!!!!
而且一点注释都没有,缩进也不对齐.
反正我遇到这样的程序都就疼.
不过我服了wayne居然嵌套了那么多层还没头晕
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-19 14:47:12 | 显示全部楼层
n=16时:
捕获.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-9-10 10:15:16 | 显示全部楼层
一些OEIS数列,计算更多的项需要付出相当的努力。

我正在作一个计算,计算完成后,可得到OEIS A002071 (http://oeis.org/A002071)的前40项。
这个计算过程的目的是找出所有符合如下条件的数n
  1) n是一个 173 smooth number,
  2) n+1 也是一个173 smooth number。
173 smooth number 指这样的数,它的所有素因子不大于173.

关于smooth number,请参阅http://en.wikipedia.org/wiki/Smooth_numbers
关于consecutive pairs of p-smooth numbers及其计算方法,请参阅http://en.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem

173是第40个素数,若$P_k$表示第k个素数,则求consecutive pairs of $P_k$-smooth numbers需要解 $2^k$个pell方程,因此,我的这个计算需要求解 $2^40$ $~~$ 1万亿个pell方程,在一个2.2G的双核电脑,大约需要8个月,我动用了多台电脑,预计可在2个月内完成。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-11-20 23:36 , Processed in 0.058815 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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