往桶里放数字使相邻数字之和为质数

KeyTo9_Fans

把数字1、2、3、……、m依次放入n个桶里，使得最新放入的数字与桶顶数字之和不为合数

如果某个桶是空的，则要求最先放入的数字不为合数

给定n，求最大的m，使得至少存在一种放置方案

例1：

当n=1时，最大的m是4：

第1步：把1放入桶里可行，因为1不是合数
第2步：把2放入桶里，(1+2)不是合数
第3步：把3放入桶里，(2+3)不是合数
第4步：把4放入桶里，(3+4)不是合数
5就没法放了，因为(4+5)是合数

因此当n=1时，最大的m是4

例2：

当n=2时，最大的m好像是7，放法如下：

第1个桶放 1 2 5 6
第2个桶放 3 4 7

8好像无论如何都没法放

当n=3时，最大的m好像是43，放法如下：

1 4 7 10 13 18 19 22 25 28 33 34 39 40 43
2 3 8 9 14 15 16 21 26 27 32 35 38 41 42
5 6 11 12 17 20 23 24 29 30 31 36 37

还有更优的解吗？

对于更大的n，最优解是多少？最优解的数列是否被OEIS收录过？

mathe

100

200
120

300
230
130
123

400
240
430
140
423
124

450
540(合并上一个)
245
435
145
453(合并435)
154(合并145)

460
246
436
645
146

760
470
467
276
247
736
437
745
675
176
147

786
487
748
678(重复)

796
987
497
798(重复)
749(重复)

a96
7a6
a87
98a
4a7
49a

复杂度还行

mathe

比较遗憾，就到43为止了

mathe

除了2以外，每个偶数前面是一个奇数，而且不能重复使用，所以得出
{4,6,8}->{1,3,5}
{10,12,14}->{7,9,11}
18->13
16->15
20->17
26->21
22->19
24->23
28->25
30->29
32->27
34->33
38->35
36->31
40->39
42->{37,41}
44-> empty
由此得出最多到43

mathe

应该把和拓展为素数或素数的幂

KeyTo9_Fans

素数越来越稀疏，无论给多少个桶，都是没办法无限放置的

我猜测能放置的数字数量大约是素数间隔ln(n)的反函数，也就是最大的m大约是exp(n)

枚举算法的搜索量是双层指数级增长的，最优解的数列即使被收录，也会标有“Hard”关键字

素数的幂没多少，我感觉加上它们对结果影响不大

mathe

使用贪心法，每次遇到素数的幂，当开一个桶，每次遇到一个非素数幂，放在当前可用最小数字上面，验算到10000都没有问题。所以看来素数的幂是完全可以一直演算下去的。

mathe

换成素数幂以后，一个桶显然可以放到7，然后由于7+8=15不是素数幂，所以结束，最多可以放到7.
两个桶可以放到17， 三个桶47， 四个桶73，5个桶103。

KeyTo9_Fans

写了个程序，枚举所有可能的放法，发现当n大于2时，无论n是几，m的最大值都是43

也就是无论给多少个桶，都无法放置44

确实需要把【非合数】这个条件放宽到【素数或素数的幂】

放宽后的求解结果如下：

7,17,47,73,103,104,277

下一项把我的内存干爆了，求解程序报【terminate called after throwing an instance of 'std::bad_alloc'】错误

#####

还有一种放宽条件的方法是：空桶里可以放任何数

非空的桶里才要求相邻两数之和为质数

该规则的求解结果如下：

4,7,43,60,61,62,172,269