Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回はメルセンヌ数（Mersenne Number）が素数であるかどうかを判定するリュカ・テスト (Lucas–Lehmer primality test) を見ていきます。メルセンヌ数とは を素数とし…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 前回、素数列を生成するアルゴリズムを見ましたが、今回は素因数分解 (factorization into primes) をするアルゴリズムを見ていきます。参考 『Javaによるアルゴリズ…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 ちょっと別用で素数 (prime number) を生成するコードを書いたので、こちらのブログで整理しておきます。 別用記事で見たように Int や Long に対してなら2行で書けま…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は最大公約数（GCD, Greatest Common Divsor）を求めるアルゴリズムを見ていきます。 最大公約数はアルゴリズムと言えばのユークリッド互除法で求められます。こ…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ。 今回は組合せの個数を計算するアルゴリズム。 その1では、あまり実用的ではないです…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は再帰関数の例としてよく出てくる自然数の階乗と、それに関連する順列の個数を計算するアルゴリズムを見ていきます。 再帰関数の例としてよく出てくると言っても…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は前回に引き続き、全順列を生成するアルゴリズムを見ていきます。 全開は『Java によるアルゴリズム事典』に載っている4つのアルゴリズムのうち1つ目のものを見…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回はある定まった次数（並べるモノの個数。 コード中では degree とする）の全順列を生成するアルゴリズムを見ていきます。 『Java によるアルゴリズム事典』には4…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は順列に辞書順序で番号を付けたとき、与えられた順列とその番号との相互の変換を考えます。 ただし番号は Int などの通常の整数値ではなく、階乗進法で表された…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は、階乗進法 (factorial representation) という数の表し方を見ていきます。階乗進法10進法が10を基数にしている、つまり10の累乗の級数で表されるのに対して、…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 以前に置換のアルゴリズムを扱ったときに、『Java によるアルゴリズム事典』に「置換の生成」がなくておかしいなぁと思ってたら、「順列」「順列の生成」の項目にある…

『Java によるアルゴリズム事典』には載ってなかったんですが、n 個のモノの全置換を生成するコードを見ていきます（目次）。Scala では List などの順序付きのコレクション（正確には scala.collection.SeqLike トレイトのサブ型）では permutations() メソ…

Scala で『Java によるアルゴリズム事典』のコードを書き換えてみようシリーズ（目次）。 今回は指定された置換の符号を計算するアルゴリズム。 ここでは Java や Scala のコードで扱い易くするため、n 個の置換は1から n の整数ではなく、0から n-1 の整数…

『級数・フーリエ解析 (岩波 数学公式 2)』に載ってる、二項係数を1つ含む級数の公式を導いてみます。 前々回、前回に二項係数を2つ含む級数の公式をあれこれ導いたので、ちょっと順番が前後しますが。確認二項係数は階乗を使って以下のように定義されるので…

前回、二項係数の加法定理（加法公式）を使って、『級数・フーリエ解析 (岩波 数学公式 2)』に載っている、二項係数を2つ含む級数の公式をいくつか導きました。 ただ、いくつか加法定理からは導けない公式があったので、今回はそれらを別の方法で導いてみま…

今回は二項係数（binomial coefficient）の第1引数に対する加法公式（加法定理？）を導きます。 この公式を使って、二項係数を２つ含む級数をあれこれ計算できます。 前回の記事『二項係数の定義を負の係数に拡張する』では、第1引数が整数（以下では ）の二…

前回の記事で、『級数・フーリエ解析 (岩波 数学公式 2)』に載ってる階乗や二項係数を含む級数の公式をいくつか導きましたが、実は という公式を導けなくて挫折してました、ハイ、スイマセン。 で、あれこれ思考＆調査したところ、どうも二項係数を負の値に…

ちょっと、とある公式を導くために二項係数を含む級数をあれこれ考えてたんですが、どうも導き方がよく分からなかったので、階乗や二項係数を含む級数の公式を片っ端から導いてみます。 公式は『級数・フーリエ解析 (岩波 数学公式 2)』に載ってるもの。 以…

以前の記事で以下のような下降階乗冪というのを扱いました： で、「下降」階乗冪ってのがあるなら「上昇階乗冪」というのもあって良さそうなので、同じように定義してみましょう。 定義は以下のようにするのが自然でしょう： この上昇階乗冪は、超幾何関数 (…

前回は、微分の離散版である差分に関する公式をいくつか導きました。 今回は積分の離散版である和分についての公式をいくつか導いていましょう。 前回と同じく『数学ガール (数学ガールシリーズ 1)』に載ってる公式です。和分の定義まずは和分の定義。 差分…

前からずっと気になっていたんだけど、『数学ガール (数学ガールシリーズ 1)』（一番最初の巻）の第6章に載っている、微分・積分の公式に対応する差分・和分の公式って結構スゴイ、そしてキレイ。 んで、ふと自分の手で実際に証明してみることに（というか証…

この記事では以下のような冪乗和 を生成母関数 (generating function) の方法を用いて求めてみます。 Wikipedia よると、結果で得られる公式は『ファウルハーバーの公式 (Faulhaber's formula)』というそうです（「wikipedia:ファウルハーバーの公式」）。参…

前回見たベルヌーイ数ですが、 正接関数 をはじめいくつかの初等関数*1の冪級数展開（テイラー展開）の係数として登場します。 今回はそれらの冪級数展開を導きたいと思います（やはり[wikipeida:ベルヌーイ数]に載ってる公式の導出をやってるだけですが）。…

正接関数 tan x の展開係数として現れるベルヌーイ数。 正直今まであんまり真面目に扱ったことがなく敬遠してたんですが、ちょっとあれこれベルヌーイ数にまつわる公式を自分の手で計算して確かめてみました。 ほとんどwikipedia:ベルヌーイ数に書いてある公…