问裂变数

EN

Python 3,112个字节

def f(n,c=0):
 d=n-c;s=(n-d*~-d/2)/d
 return(s%1or s<1)and f(n,c+1)or+(d<2)or-~sum(f(int(s)+i)for i in range(d))

由于@FryAmTheEggman保存了4个字节。

稍后再解释..。

额外的事实:每个2的幂都有一个裂变数为1。这是因为偶数长度序列的和总是两个中间数之和，这是奇数，乘以序列长度的一半，也就是整数。奇数长度序列之和是中间数乘以序列长度，即奇数。因此，由于2的幂没有奇数除数，它只能表示为自身的和。

Python2，86

f=lambda n,R={1}:n-sum(R)and f(n,R^{[min(R),max(R)+1][n>sum(R)]})or-~sum(map(f,R-{n}))

较少的高尔夫球：

def f(n,R={1}):
    d=sum(R)-n
    if d==0:return (sum(map(f,R-{n}))
    if d<0:return f(n,R|{max(R)+1})
    if d>0:return f(n,R-{min(R)})

其想法是测试与n相加的连续整数的潜在运行情况。运行直接存储为一个集R，而不是通过它的端点。

我们检查当前运行的和如何通过它们的差异与所需的和n进行比较。

• 如果和太大，我们削减最小的元素在运行。
• 如果和太小，我们延长运行，使其最大值增大1。
• 如果和是正确的，我们递归，映射f到运行，求和，并为当前节点添加1。如果运行是{n}，我们已经尝试了所有非平凡的可能和，首先通过删除n来停止递归。

感谢Sp3000保存了3个字符。

Go，133个字节

func 算(n int)int{Σ:=1;for i:=0;i<n;i++{for j:=0;j<n;j++{if i*i+i-j*j-j==2*n{for k:=j+1;k<=i;k++{Σ+=算(k)};j,i=n,n}}};return Σ}

这是我第一次打高尔夫球，如果我犯了什么错误，很抱歉。

这使用了这样的想法:裂变“组合”也可以看作是两个有序整数序列之间的区别。例如，以数字13的裂变“组合”为例，它是6,7，但它可以看作是整数1.7减去整数1.5之和的总和。

  A: 1 2 3 4 5 6 7  sum = 28
  B: 1 2 3 4 5      sum = 15 
A-B:           6 7  sum = 13, which is also 28-15 = 13

回想一下高斯学时的公式，sum 1...n=(n^2+n)/2。因此，为了找到给定n的顺序整数的组合，我们也可以说，我们正在沿着范围1. n搜索‘端点’p和q，以便(p^2+p)/2 - (q^2+q)/2 =n。在上面的例子中，我们会搜索‘端点’5和7，因为7^2+7=56/2，5^2+5=30/2，56/2-30/2 = 28-15 = 13。

现在有多种可能的裂变方法--合成一个数字，正如Martin所指出的，9=2+3+4，也有4+ 5。但似乎很明显，“最低”的起始序列也将是最长的，因为与中等大小的数字相比，要将较小的数字加起来需要更少的数字。(不幸的是，我没有证据)

因此，为了找到9的组合，测试每个‘端点对’，p和q，将p和q分别从0迭代到9，并检验p^p+p/2-q^2+q/2=9。或者，更简单地说，将方程乘以2，以避免舍入的除法问题，并将所有的数学保持在整数中。然后我们寻找p和q，使得(p^p+p) - (q^q+q) = 9*2。我们找到的第一个匹配将是裂变合成端点，因为正如前面提到的，最低的一组数也是最长的，我们正在搜索低到高(0到9)。一旦找到匹配，我们就从循环中挣脱出来。

现在递归函数为给定的n找到那些‘易裂变端点’p和q，然后对树中从p到q的每个‘子’进行回顾。对于9，它会找到1和4，(20-2=18)，然后重新调用2，3和4，求和结果。对于像4这样的数字，它根本找不到匹配的，因此返回'1‘。这可能是可缩短的，但这就像我的第三个围棋程序，我不是递归专家。

感谢您的阅读。