pari-gp - パリ/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. PARIは正確な丸めを保証しないため、テストsqrtn(n,k)==floor(sqrtn(n,k))は信頼できません。sqrtn（）の値が数学的に正確な整数であっても、PARIは正確な答えより少し大きいまたは少し小さい実数を返す場合があります。roundを使用するよりも使用する方が少し良くなりますfloor。それでも信頼性はありませんが、多かれ少なかれ機能するソリューションがあります

   y = round（sqrtn（n、k））; y ^ k == n

（提供されるrealprecisionのは十分な大きさです）。しかし、ispowerは、数値がk乗でない場合は常に、非常に高速になるモジュラーテストから始まります。

Answer 2

素数冪には、1つのベース（素因数自体）のみを含む因数分解があります。したがって、テストを実行するためのより良い方法は次のとおりです。

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 ^ kなので、今でも1のコーナーケースがあります。

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など、許容できると思われる非常に小さい数です。

「...<イプシロン」だけでなく、4.0000000001を取得することもありますが、3.9999999999を取得することもあるので、その理由を記述します。