integer - 计算异或为零的整数分区

Question

我正在寻找一种有效的方法来计算异或为零的整数分区数： F(n,c) = #{ (x1,x2, ... ,xc) | x1 + x2 + ... + xc = n & x1 xor x2 xor ... xor xc = 0 }

对于 n 和 c 的小值，很容易运行嵌套循环来计算这些值。但是对于较大的值，它是不可处理的。我想获得一个封闭的形式或至少一个允许动态编程的递归公式..

score 1 · Accepted Answer

除非您的问题的约束导致一个特别聪明且非常不明显的解决方案，否则我相信您会问一个非常困难的问题，该问题将处于研究数学的最新水平。

首先，只计算一个整数的普通无限制分区（即计算将整数表示为正整数之和的可区分、与顺序无关的方法的数量）是一个有着数百年历史的深刻数学问题。

你有一些额外的非正统约束——首先你只想要具有给定数量的术语的分区子集（这可能会使它更容易），然后，我认为，对二进制表示的 XOR 的约束条款，这可能很难处理。

你打算 n 有多大？上面的参考资料说 p(1000) 大约是 2.44 * 10^31。

如果n很大，你也相信c会很小吗？这将大大简化事情。

要解决您的问题，您需要吸引专门从事该领域的研究数学家的兴趣。

www.aimath.org/news/partition/

您可以使用“Partitions”作为关键字来尝试 Math Overflow。

我发现this thread about partitioning into exact c (they use 'k' for this part)单个部分，这是你的第一个（更简单的）约束。

1 回答 1