3.2.4 整数の操作と整数論に関連した関数

整数に関する関数の例

を で割ったときの余り．

In[1]:= Mod[17, 3]

Out[1]=

の整数部．

In[2]:= Quotient[17, 3]

Out[2]=

Modには実数を使うこともできる．

In[3]:= Mod[5.6, 1.2]

Out[3]=

Modの結果は，第2引数の符号を引き継ぐ．

In[4]:= Mod[-5.6, 1.2]

Out[4]=

任意の整数 aとbに対して，b*Quotient[a, b] + Mod[a, b]は常に aに等しい．

オフセットを含む整数剰余

特にModを使いオブジェクトの部分の指標を得る場合はオフセットを指定すると便利なことがある．

リストを循環的に扱い，18番目の部分を抽出できる．

In[5]:= Part[{a, b, c}, Mod[18, 3, 1]]

Out[5]=

最大公約数(greatest common divisor)の関数 GCD[, , ... ]は，すべての を割り切ることができる最大整数を与える．2整数を比の形で入力したなら， Mathematicaは， GCDを使い共通因数をキャンセルし，約分しつくした形の有理数を返す．

最小公倍数(least common multiple)の関数 LCM[, , ... ]は，各 のすべての因数を含んだ最小整数を与える．

24と15の最大公約数を求めると，3が得られる．

In[6]:= GCD[24, 15]

Out[6]=

クロネッカーのデルタあるいは クロネッカーの記号KroneckerDelta[, , ... ]は すべてが等しいなら1でそうでなければ0である． は完全対称テンソルと考えられる．

階数が3の完全対称テンソルを与える．

In[7]:= Array[KroneckerDelta, {3, 3, 3}]

Out[7]=

素因数分解と関連する関数

24の因数は と である．因数は，各リストの第1要素で，指数は第2要素である．

In[8]:= FactorInteger[24]

Out[8]=

もっと大きい整数について因数を探す．

In[9]:= FactorInteger[111111111111111111]

Out[9]=

数学的に見て，素因数分解は根本的に難解な問題である．このため， キーボードから簡単にタイプできるような整数でも，天文学的に長い時間をかけなければ分解できないことがある．与えられる整数が50桁程度までの大きさならば， Mathematicaは FactorIntegerを使うことで難なく分解することができる．特別な場合は，それより大きい整数でも分解できる．（素因数分解の問題によっては， FactorInteger[n]に FactorComplete->Falseの条件を与えておくことで，nから計算しやすい因数だけを抽出させ，検索がより早く終了するようにすることができる．）

これは大きいが，やや特殊な整数である．

In[10]:= 30!

Out[10]=

この整数は特別なため，簡単に因数分解される．

In[11]:= FactorInteger[%]

Out[11]=

Mathematicaは，整数が大きくなるとそれを分解できないかもしれないが，それでも，それが素数かどうかの判定は行うことができる．また，k番目の素数をすばやく探せるようにもなっている．

数を素数に分解するより，それが素数かどうかを判定する方が断然早い．

In[12]:= PrimeQ[234242423]

Out[12]=

最初の100個の素数を探させ，値をプロットさせる．

In[13]:= ListPlot[ Table[ Prime[n], {n, 100} ] ]

Out[13]=

100万番目の素数を探させる．

In[14]:= Prime[1000000]

Out[14]=

整数論では，素数の実際の値より素数がどう分布しているかを知る方が重要なことが多い．関数PrimePi[x]を使えば， 以下の素数の個数 を知ることができる．

以下の素数がいくつあるかを調べる．

In[15]:= PrimePi[10^9]

Out[15]=

デフォルト設定では， FactorIntegerは実整数だけを扱う．しかし， GaussianIntegers -> Trueのオプション設定が加えられたなら，整数実数部と整数虚数部からなる複素数のガウス整数も扱うことができるようになる．実素数で一意的に分解することが可能なように，ガウス素数で一意的に分解することが可能である．それでもガウス素数を選択するときは潜在的な曖昧さが残る．このため， Mathematicaでは，常に正の実部と負でない虚数部を持つガウス素数が選択される．ただし，最初の素数としてはと を許容することとする．

ガウス整数の中でなら， 2は として因数分解することができる．

In[16]:= FactorInteger[2, GaussianIntegers -> True]

Out[16]=

ガウス整数の因数を探させる．

In[17]:= FactorInteger[111 + 78 I, GaussianIntegers -> True]

Out[17]=

整数論で使う関数のいくつか

モジュラベキ関数 PowerMod[a, b, n]は bが正なら Mod[a^b, n]と同じ結果を与える．しかし，PowerModは a^bの完全形を生成することを避けられるので，より効果的である．

PowerModを使えば，正のモジュラベキばかりでなく有限体の逆数も求めることができる．例えば， PowerMod[a, b, n]において bが負の値を取る場合，式 の関係を満たす整数 が存在すればそれを与える．（このような整数が存在する場合，それは，必ず を法(modulo)として一意である．）一方， が存在しない場合， PowerModは未評価のまま残される． （ は， を で割った余りが であることを表す．）

PowerModを使えば， Powerと Modを組で使ったときと同じ機能を得ることができ，また，より効率よく計算することができる．

In[18]:= PowerMod[2, 13451, 3]

Out[18]=

7を法とした3の逆数を求める．

In[19]:= PowerMod[3, -1, 7]

Out[19]=

この逆数に3をかけ，7を法とすると，期待した通りに1が求まる．

In[20]:= Mod[3 %, 7]

Out[20]=

オイラー(Euler)の関数 は， より小さく，かつ， に対して素となる整数の個数を返す．また， と が互いに素ならば が成り立つ （フェルマ(Fermat)の小定理）．

メービウス(Möbius)の関数 は， が 個の異なる素数の積であるとき となり，1ではない2乗因数を含む場合に0となるよう定義される．もし，すべての に対して ならば， が成り立つ（メービウスの反転公式）．ただし，は，を割り切る正の について和を取ることを表す．

約数関数は， のすべての約数を 乗して加えた和を与える．関数 は の約数の個数を与え，と書かれることもある．また， は の除数の総和と等しく， と書かれることもある．

素数 に対しては， の関係が成り立つ．

In[21]:= EulerPhi[17]

Out[21]=

フェルマの小定理により，この結果は必ず1になる．

In[22]:= PowerMod[3, %, 17]

Out[22]=

24のすべての約数をリストに列挙する．

In[23]:= Divisors[24]

Out[23]=

を使い24の約数がいくつあるか調 べる．

In[24]:= DivisorSigma[0, 24]

Out[24]=

ヤコビ(Jacobi)の記号 JacobiSymbol[n, m]は， が奇数で，かつ，素数のとき，ルジャンドルの記号に帰着する．また，ルジャンドルの記号は， が で割り切れるとき 0に等しい．そうでない場合， が素数 を法とした平方剰余のとき1に等しく，そうでなければ に等しい． ここで， に対して素となる整数 は， の関係を満たす整数 が存在するとき， を法とする平方剰余である，という．一般の場合のヤコビの記号は， となる各素因数 に関するルジャンドルの記号 の全体の積である．

拡張最大公約数 ExtendedGCD[, , ... ]は， を の最大公約数とし， を となる整数としたときのリスト g, , , ... を返す．拡張最大公約数は，線形（不定）方程式の整数解を求める際に重要な役割を果たす．

リストの第1要素が105と196の最大公約数である．

In[25]:= ExtendedGCD[105, 196]

Out[25]=

数の第2ペアは の関係を満たす．

In[26]:= -13 105 + 7 196

Out[26]=

乗積順序関数 MultiplicativeOrder[k, n]はとなるような最小の整数 を与える．この関数はの指標あるいは 離散対数としても知られている．の記号もしばしば使用される．

一般化された乗積順序関数MultiplicativeOrder[k, n, , , ... ]は任意のに対してであるような最小の整数を与える．MultiplicativeOrder[k, n, -1, 1]はと表記されをで法とする部分順序関数として知られている．

カーマイケル関数あるいは 最小普遍指数はと互いに素であるようなすべての整数に対してであるような最小の整数を与える．

格子の簡約化関数LatticeReduce[, , ... ]は，いくつかの最近のアルゴリズムで使われる．基本的な考えとして，整数を成分とするベクトル は数学的な格子を定義するものとしてとらえる．格子の点を表すベクトルは，すべて を整数とする線形結合 として書くことができる．ある特定の格子に対して，数多くの「基底ベクトル」 が存在する．そこで，LatticeReduceは格子に対して特定の性質を持つ簡約された基底ベクトルの組を見出す．

3座標軸に沿った3つの単位ベクトルは，はじめから簡約された基底を形作って いる．

In[27]:= LatticeReduce[{{1,0,0},{0,1,0},{0,0,1}}]

Out[27]=

3つのベクトルからなる4次元の格子について基底ベクトルを探す．

In[28]:= LatticeReduce[{{1,0,0,12345}, {0,1,0,12435},
{0,0,1,12354}}]

Out[28]=

上の最後の例で， LatticeReduceは，互いにほぼ平行なベクトルをより垂直なベクトルに置き換え，いくつかのかなり短い基底ベクトルを見付けていることに注意が必要である．

連分数

の連分数表現の最初の10項を生成する．

In[29]:= ContinuedFraction[Pi, 10]

Out[29]=

連分数項のリストで代表される数値を再構築する．

In[30]:= FromContinuedFraction[%]

Out[30]=

結果はに近い．

In[31]:= N[%]

Out[31]=

これはの有理近似を直接与える．

In[32]:= Rationalize[Pi, 1/1000]

Out[32]=

連分数は数論でよく現れる．有理数の連分数表現は途中で打ち切られる．二次無理数は連分数表現を持ち，それは反復する．

数値の完全な表現

の連分数表現は8で始まり，限りなく反復される数列からなる．

In[33]:= ContinuedFraction[Sqrt[79]]

Out[33]=

が連分数表現から再構築される．

In[34]:= FromContinuedFraction[%]

Out[34]=

を循環小数で表す．

In[35]:= RealDigits[3/7]

Out[35]=

FromDigitsはもとの数値を再構築する．

In[36]:= FromDigits[%]

Out[36]=

数カウント関数

数77の基底2による表現．

In[37]:= IntegerDigits[77, 2]

Out[37]=

基底2による表現での1の個数を直接計算する．

In[38]:= DigitCount[77, 2, 1]

Out[38]=

数カウント関数のプロットは自己相似となる．

In[39]:= ListPlot[Table[DigitCount[n, 2, 1], {n, 128}],
PlotJoined->True]

Out[39]=

ビットごとの演算

ビットごとの演算はバイナリビットで表現された整数に施される．BitAnd[, , ... ]はバイナリビット表現でのすべてに1がある場所に，バイナリ表現で1がある整数を与える．BitOr[, , ... ]はバイナリビット表現で任意のに1がある場所に1がある整数を与える．BitXor[, ]はまたはのどちらかだけに1がある場所にバイナリビット表現で1がある整数を与える．BitXor[, , ... ]は奇数個のに1がある場所に1がある整数を与える．

基底2で入力された数値23と29のビットごとのANDを計算する．

In[40]:= BaseForm[BitAnd[2^^10111, 2^^11101], 2]

Out[40]//BaseForm=

ビットごとの演算は様々な組合せ論アルゴリズムで使用される．また低レベルのコンピュータ言語でもビットフィールドの操作によく使用される．しかしそれらの言語では整数は通常は8の倍数であるような限られた桁数しか許されない．Mathematicaでのビットごとの演算では無限の桁数の整数を扱うことができる．負の整数の場合は，左に1の数列が無限にあるような2の補数で表現される．これによりBitNot[n]はと同等となる．