pari-gp - Pari/GP 将整数与实数进行比较

Question

我想测试一个整数是否是 Pari-gp 中的完美幂。该测试sqrt(n)==floor(sqrt(n))适用于测试正方形，但对于其他所有幂都失败：sqrtn(n,k)==floor(sqrtn(n,k))使用k >=3.

我想可能是因为一个数字是实数，另一个是整数。该测试仍然适用于正方形。我究竟做错了什么？

Answer 1

1. 您应该直接使用ispower(), 和 ispower(, k)以获得完美的 k 次幂。

2. 该factor方法的问题在于，对于大输入，它会非常慢，而ispower在多项式时间内运行。

3. 该测试sqrtn(n,k)==floor(sqrtn(n,k))不可靠，因为 PARI 不保证精确舍入：即使 sqrtn() 的值在数学上是精确整数，PARI 也可能返回比精确答案稍大或稍小的任何实数。你会round比 with好一点floor。虽然它仍然不可靠，但这是一个或多或少可行的解决方案

   y = 圆形(sqrtn(n, k)); y^k == n

（只要realprecision足够大）。但是 ispower 从模块化测试开始，只要数字不是 k 次方，它就会大大加快速度。

Answer 2

素数幂的因式分解只涉及一个基数（素数因子本身）。因此，执行测试的更好方法是：

isPrimePower(x) = {
  matsize(factor(x))[1]==1
}

这是前 10 个数字的测试：

for(i=0,10,print(i,"->",isPrimePower(i)))
0->1  (yes, p^0)
1->0
2->1  (yes, 2^1)
3->1  (yes, 3^1)
4->1  (yes, 2^2)
5->1  (yes, 5^1)
6->0
7->1  (yes, 7^1)
8->1  (yes, 2^3)
9->1  (yes, 3^3)
10->0

对于复合基数，我必须假设您的意思是某个单基数的完美功率因数提高到指数 e >= 2。否则任何 n = n^1。即使现在我们也有 1 的极端情况，因为 1=1^k。

isPerfectPower(x) = { 
  local(e);
  if(x==1, return(0));
  factors = factor(x);
  e = factors[1,2];
  if(e < 2, return(0));
  for(i=2,matsize(factors)[1],
      if(factors[i,2] != e, return(0));
  );
  return(1);
}

再次测试：

> for(i=1,20,print(i,"->",isPerfectPower(i)))
1->0
2->0
3->0
4->1
5->0
6->0
7->0
8->1
9->1
10->0
11->0
12->0
13->0
14->0
15->0
16->1
17->0
18->0
19->0
20->0

Answer 3

您可以测试 frac(sqrtn(261,3)+epsilon) < 2*epsilon 其中 epsilon 是您认为可以接受的一个非常小的数字，例如 1E-15

我写它为什么而不仅仅是“... < epsilon”，因为有时你会得到 4.0000000001，但你也可以得到 3.9999999999。