论坛 › 算法交流 › 关于整数的等幂和拆分的计数问题

wayne 发表于 2010-6-18 13:56:11

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

前段时间，emath两大高手伫立于巅峰，进行了一番隔空传音般的对话，彻底解决了整点直角三角形问题。

我甚是佩服，在好奇之余，又搜索了一下Mathematica的文档，发现Mathematica竟然有相关的内置函数：SquaresR 函数 和 PowersRepresentations 函数


也就是说下面的两个方程的整数解的个数均有好的算法：

n_1^2+n_2^2+....+n_d^2=n其中ni可正可负，可以为0.
以及
n_1^p+n_2^p+....+n_d^p=n其中，0<=n_1<=n_2<=...<=n_d

那这个算法到底是什么呢？
mathe 和 hujunhua可否再给我们展示一下？

mathe 发表于 2010-6-18 14:03:05

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

wayne 发表于 2010-6-18 14:17:42

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

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

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

wayne 发表于 2010-6-18 14:27:42

哦，反复测试了几个数之后，
感觉 Mathematica的这两个函数似乎并不是很神奇。
我把n设大了，有好多数计算的非常的慢：
比如，将1729表示成10个数的立方，倒是很快的PowersRepresentations{{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 发表于 2010-6-18 14:29:21

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

wayne 发表于 2010-6-18 14:33:18

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

qianyb 发表于 2010-6-18 14:49:10

1282051358533580267640组解，这么多啊！

hujunhua 发表于 2010-6-18 15:36:40

惭愧，我就一“算盲”。我倒是有一个问题要请教。

关于整点直角三角形的计数，基于数论计数公式的算法和那个帖子中的高手给出的搜索算法，哪个效率高些？如果搜索算法效率还高些，搞数论公式，对于大数就没意义了。

wayne 发表于 2010-6-18 16:27:25

7# qianyb


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

wayne 发表于 2010-6-18 16:31:29

8# hujunhua

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

查看完整版本: 关于整数的等幂和拆分的计数问题