关于整数的等幂和拆分的计数问题

wayne

前段时间，emath两大高手伫立于巅峰，进行了一番隔空传音般的对话，彻底解决了整点直角三角形问题。 我甚是佩服，在好奇之余，又搜索了一下Mathematica的文档，发现Mathematica竟然有相关的内置函数：SquaresR 函数 和 PowersRepresentations 函数 也就是说下面的两个方程的整数解的个数均有好的算法： $n_1^2+n_2^2+....+n_d^2=n$其中n_i可正可负，可以为0. 以及 $n_1^p+n_2^p+....+n_d^p=n$其中，$0<=n_1<=n_2<=...<=n_d$ 那这个算法到底是什么呢？ mathe 和 hujunhua 可否再给我们展示一下？

mathe

不知道这里d是固定还是可变。另外Mathematica能够处理的n有多大？如果n不是太大，那么动态规划显然可以处理

wayne

mathe好神奇的速度。
=========================
那个d是函数的一个参数，你可以视为固定的。

比如，第一个方程的解的个数就是  SquaresR[d,n]
将45表示成两个整数的平方和，就是SquaresR[2, 45]=8

第二个方程的解就是 函数  PowersRepresentations[n,d,p]
将6963472309248表示成2个数的立方，那么就是 PowersRepresentations[6963472309248, 2, 3]的返回值：
{{2421, 19083}, {5436, 18948}, {10200, 18072}, {13322, 16630}}

wayne

哦，反复测试了几个数之后， 感觉 Mathematica的这两个函数似乎并不是很神奇。 我把n设大了，有好多数计算的非常的慢： 比如，将1729表示成10个数的立方，倒是很快的

1. PowersRepresentations[1729, 10, 3]

复制代码

{{0, 0, 0, 0, 0, 0, 0, 0, 1, 12}, {0, 0, 0, 0, 0, 0, 0, 0, 9, 10}, {0, 0, 0, 0, 0, 0, 1, 6, 8, 10}, {0, 0, 0, 0, 0, 1, 3, 3, 7, 11}, {0, 0, 0, 0, 1, 3, 3, 6, 9, 9}, {0, 0, 0, 0, 1, 3, 4, 5, 8, 10}, {0, 0, 0, 0, 2, 2, 3, 7, 7, 10}, {0, 0, 0, 0, 3, 3, 4, 4, 6, 11}, {0, 0, 0, 0, 4, 5, 5, 7, 7, 9}, {0, 0, 0, 1, 2, 6, 6, 6, 7, 9}, {0, 0, 0, 1, 4, 4, 4, 8, 8, 8}, {0, 0, 0, 2, 4, 4, 5, 5, 7, 10}, {0, 0, 0, 3, 3, 3, 4, 7, 8, 9}, {0, 0, 0, 3, 3, 3, 6, 6, 6, 10}, {0, 0, 1, 1, 1, 3, 3, 5, 6, 11}, {0, 0, 1, 1, 3, 3, 6, 6, 8, 9}, {0, 0, 1, 2, 2, 4, 4, 7, 8, 9}, {0, 0, 1, 2, 2, 4, 6, 6, 6, 10}, {0, 0, 1, 3, 3, 3, 4, 5, 9, 9}, {0, 0, 1, 4, 5, 5, 6, 7, 7, 8}, {0, 0, 2, 2, 5, 6, 7, 7, 7, 7}, {0, 0, 2, 3, 3, 3, 4, 4, 8, 10}, {0, 0, 2, 3, 4, 6, 6, 7, 7, 8}, {0, 0, 2, 4, 4, 6, 6, 6, 6, 9}, {0, 0, 3, 3, 3, 4, 4, 4, 5, 11}, {0, 1, 1, 1, 1, 4, 5, 8, 8, 8}, {0, 1, 1, 1, 2, 2, 7, 7, 8, 8}, {0, 1, 1, 1, 2, 5, 5, 5, 7, 10}, {0, 1, 1, 2, 2, 3, 5, 6, 7, 10}, {0, 1, 1, 2, 2, 4, 4, 5, 9, 9}, {0, 1, 1, 2, 6, 6, 6, 6, 7, 8}, {0, 1, 1, 4, 5, 5, 5, 6, 7, 9}, {0, 1, 2, 2, 2, 4, 4, 4, 8, 10}, {0, 1, 2, 2, 4, 4, 4, 4, 5, 11}, {0, 1, 2, 3, 3, 5, 7, 7, 7, 8}, {0, 1, 2, 3, 4, 5, 6, 6, 7, 9}, {0, 1, 3, 3, 3, 4, 6, 7, 8, 8}, {0, 1, 6, 6, 6, 6, 6, 6, 6, 6}, {0, 2, 2, 4, 4, 4, 4, 6, 8, 9}, {0, 3, 3, 3, 3, 4, 5, 6, 6, 10}, {0, 3, 3, 5, 6, 6, 6, 6, 7, 7}, {0, 4, 4, 4, 5, 5, 6, 6, 7, 8}, {0, 5, 5, 5, 5, 5, 5, 5, 5, 9}, {1, 1, 1, 1, 2, 2, 2, 3, 7, 11}, {1, 1, 1, 1, 2, 2, 5, 7, 8, 9}, {1, 1, 1, 2, 3, 3, 3, 5, 8, 10}, {1, 1, 1, 2, 5, 6, 6, 6, 6, 9}, {1, 1, 1, 3, 3, 3, 4, 5, 5, 11}, {1, 1, 1, 3, 3, 6, 6, 6, 8, 8}, {1, 1, 2, 2, 4, 4, 6, 7, 8, 8}, {1, 1, 2, 3, 3, 3, 3, 4, 6, 11}, {1, 1, 2, 3, 3, 5, 5, 7, 7, 9}, {1, 1, 2, 4, 4, 5, 5, 5, 6, 10}, {1, 1, 3, 3, 3, 4, 5, 6, 8, 9}, {1, 1, 4, 4, 4, 4, 4, 4, 7, 10}, {1, 2, 2, 3, 3, 3, 6, 7, 7, 9}, {1, 2, 2, 3, 4, 4, 5, 6, 6, 10}, {1, 2, 4, 4, 6, 6, 6, 6, 6, 8}, {1, 3, 3, 3, 3, 3, 5, 5, 7, 10}, {1, 3, 4, 4, 5, 5, 5, 7, 7, 8}, {1, 4, 4, 4, 5, 5, 5, 6, 6, 9}, {2, 2, 3, 4, 5, 5, 7, 7, 7, 7}, {2, 2, 4, 5, 5, 5, 5, 5, 8, 8}, {2, 3, 3, 3, 3, 3, 3, 6, 7, 10}, {2, 3, 3, 3, 3, 3, 4, 4, 9, 9}, {2, 3, 3, 4, 4, 5, 6, 7, 7, 8}, {2, 3, 4, 4, 4, 5, 6, 6, 6, 9}, {3, 3, 3, 4, 4, 4, 6, 6, 8, 8}}

wayne

19721表示成10个数的立方，算了一分钟，有2760组解

wayne

SquaresR函数还是很快的。 将100000表示成10个整数的平方，共有1282051358533580267640组解

qianyb

1282051358533580267640组解，这么多啊！

hujunhua

惭愧，我就一“算盲”。我倒是有一个问题要请教。 关于整点直角三角形的计数，基于数论计数公式的算法和那个帖子中的高手给出的搜索算法，哪个效率高些？如果搜索算法效率还高些，搞数论公式，对于大数就没意义了。

wayne

7# qianyb 一觉醒来，发现将10000表示成20个整数的平方也计算出了，共有257559629384518810765941633263639704组解，比1282051358533580267640长，

wayne

8# hujunhua 他们的代码是给出所有的解，然后再计数，而从数论的角度出发，直接计数，不用给出所有的解，速度自然是颠颠的快啊。