#数学挑战题

手工求最大n

把整数1到n分到两个集合，使得每个集合的任意两个数之和都不是平方数，求n的最大值？

要求不能借助程序等外部工具，用算法手工快速简洁的推导出最大n值？ ​​
​
我还说手工快速简洁的算，结果很多人用程序跑都没有写明白程序跑出来错误结果。

这张图是用手工简单快速算的，有能看图就能看明白的吗？

图中这个方法：
1、简单快捷，手工就能简单快捷完成。
2、严格证明14是最大n。
3、能够给出最大n时候的所有分组办法。
4、方法可扩展到别的比如和不能为立方数，缺一些数等。当然立方数因为取值比较大一点，这个表就有点大，手工慢一些。

⚠️有兴趣的看谁设计程序跑一跑和不能位3次方数4次方数等？检验一下自己的算法结果如何。

答案是最大n是14，但是很多人的做法其实是没有严格证明是14的。

好点的有14的分组，但是也没有能解题方法里能快速简洁的给出14的分组所有情况。这个情况分组是唯一的，比如缺13分组就不唯一了。

⚠️解释一下这个染色图。

其实这个图就是标准的二分染色算法，算法比较简单，手工去跑的程序。

取一个合理的num，maxn=num。

从1开始
1、1未染色，染色1号颜色。从2开始到maxn，染色和为平方数的。3、8、15染色1号反颜色-1。
2、2未染色，染色2号颜色，7、14染色-2号颜色。
3、3已经染色-1，6、13染色1。
4、4未染色，染色4，5、12染色-4。
5、5染色4、11染色-4。
6、6染色1，10染色-1。
7、7染色-2，9染色2
8、8染色-1。
9、9染色2。
10、10染色-1，15染色1，但15已经染色-1。冲突，最大maxn=14。还必须继续到maxn，有可能还有更小的maxn，遇到新的冲突更新maxn。
11、11染色4，14染色-4。
14已经染色-2，4号颜色是2号颜色，-4号颜色是-2号颜色。
程序的话用数组值代表颜色，这里就可以替换掉了。前面的不会冲突，如果不要分组的方法，可以只往后面替换。颜色替换可以替换成标号小的。
12、12染色-4，或者已经被替换了-2，13染色2。
13已经染色1，说明2号颜色是1号颜色。就是1、2、4号颜色都是1号颜色，-1、-2、-4都是-1号颜色。
13、13染色1、4，也就是染色1。
14、14染色-2、-4，也就是染色-1。

到了最大maxn，maxn不等于num，结束说明最大maxn=14。如果maxn=num，说明num取小了，可以取大一些继续。加大num手工可以再原有基础上继续。
124号颜色都确定了，最大14只有唯一分组方法。

改进了一下标记顺序，更适合动态数目的n，效率也更好。
Python代码：

def maxn(num,pa):
a=[i for i in range(num+1)]
for i in range(1,num+1):
for j in pa:
if (j<=i):continue
if j>=2*i: break
s=j-i
if(a[i]==i)|(a[i]==-a[s]): a[i]=-a[s]
else:
if a[i]==a[s]:return i-1
else:
m=a[i]
n=a[s]
for k in range(1,i):
kk=a[k]
if kk==n:a[k]=-m
if kk==-n:a[k]=m
return num
def test(be,end):
for i in range(be,end+1):
num=10**i
pa=[j**i for j in range(2,2+int((2*num)**(1/i)))]
mn=maxn(num,pa)
print(mn)
test(2,5)

maxn= 2 14
maxn= 3 123
maxn= 4 1287
maxn= 5 16759
maxn= 6 511710
maxn= 7 9766163
maxn= 8 413210916
maxn= 9 10341401476
maxn= 10 288409853638

改进算法后python代码可以搜索两个数和不能为更大的方幂的结果，结果如上图。大致是maxn=(1/ln2*n)^n的增长。
更精确一点的表达式是（2+int(1/(2^(1/n)-1)))^n，这个表达式值就非常靠近结果了。

maxn= 2 14 8 1.750000
maxn= 3 123 62 1.983871
maxn= 4 1287 1200 1.072500
maxn= 5 16759 16384 1.022888
maxn= 6 511710 500000 1.023420
maxn= 7 9766163 9743585 1.002317
maxn= 8 413210916 407865360 1.013106
maxn= 9 10341401476 10330523392 1.001053
maxn= 10 288409853638 288325195312 1.000294

这后面结果一般搜索算法是没有能力搜索了，时间、存储空间都早就满足不了了。

不用任何库代码，优化后的Python代码：

def maxn(p):
a=[0]*(10*8**p)
n=15
b=[i**p for i in range(2,n)]
for i in range(n-1):
d=b[i]-1
e=b[i+1]
for j in range(e//2,d):
m=getb(b,e-j-1)
n=getb(b,d-j)
m=geta(a,m)
n=geta(a,n)
if m==n: continue
elif m==-n:return j
else:
a[m]=n
a[-m]=-n
def getb(b,m):
s=1
while(1):
for i in range(len(b)):
if(m>b[i]):continue
if (m==b[i])|(m<=b[i]//2): return s*m
m=b[i]-m
s=-s
break
def geta(a,m):
while(1):
n=a[m]
if n==0: return m
m=n
def test():
n=9
for i in range(2,n):
mn1=(2+int(1/(2**(1/i)-1)))**i//2
mn2=maxn(i)
print("maxn=",f"{i:>2.0f}",f"{mn2:>8.0f}") #, f"{mn1:>12.0f}",f"{mn2/mn1:.6f}")
test()