Math

似非エラトステネスの篩は「アイデアとして正しい」のか?

少し前に某所でエラトステネスの篩の実装が正しくないとかなんとかで話題になったことがあった*1*2。そこでの結論が「アイデアとしては正しいが高速化のための実装としては間違い」みたいなところに落ち着いてしまってイマイチ腑に落ちなかったので少し調べ…

ユーザーの平均継続期間が解約率の逆数であることを等比数列を使わずに理解する

ユーザーの平均継続期間は「解約率=一定」と仮定すれば「1/解約率」で示せる。これについてはユーザの平均継続期間が「1/解約率」で求められることの数学的証明 - it's an endless world.に等比数列を用いたわかりやすい証明があるが、「解約率=一定」とした…

ユークリッドの互除法

tex記法のテスト。 割られる数を、割る数をとする()。 商を、余りをとする()。 また、としておく。 このとき、 …(1) であり、 である。また、、に対し、、はただ一つ定まる。 、の共通の約数のうち最大のものを最大公約数と呼び、 であらわす。なお、と…

Rでオイラーのφ関数の列挙

自然数nに対して、1からnまでの自然数の中でnと互いに素であるものの個数をで与えることとしたとき、このをオイラーのφ関数(オイラーのトーシェント関数:Euler's totient function)と呼ぶ(cf.オイラーのφ関数 - Wikipedia)。 具体的にの値を1から10まで求め…

Rで最大部分列和問題

最大部分列和(Maximum Segment Sum、略してMSS)問題とは、与えられた整数列の部分列の和のうち最大のものを求めるという問題。 非常に簡単な例で言うと、 a = {-1, -1, 1, 1, 1, -1, -1}という数列の最大部分列和mss(a)は{1, 1, 1}の和の3になる。 他にも、 …

Rでエラトステネスの篩

すごい暇だったのでエラトステネスの篩(Sieve of Eratosthenes)分かる範囲で調べてみようと思った。 数学において、エラトステネスの篩(エラトステネスのふるい)は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシ…

ユークリッドの互除法とその拡張

ユークリッドの互除法 まずはユークリッドの互除法について確認。 ユークリッドの互除法は2つの正整数の最大公約数をもとめる手法。 2つの正整数をm, nとする E1. mをnで割った剰余をrとする E2. rが0に等しければ終了。nが最大公約数である。 E3. m ここで …

ベクトルを表す太字の書き方

ボールドを手書きで書くときの例として参考になるサイトとTeXのパッケージ. http://d.hatena.ne.jp/Gauss/20080722/1216724697 VƒCƒVƒJƒ•¨—”Šw|ƒxƒNƒgƒ‹ŠÖ”‚Æ”÷•ª mathbbol.sty: TeXパッケージ bbm.sty: TeXパッケージ 要するに自分がかっこいいと思…

GNU MDK(MIX Development Kit)のインストール

MIX/MIXALとは何か MIXとはドナルド・クヌース著『The Art of Computer Programming』に登場する架空のコンピュータの名前.この架空のコンピュータMIXでプログラムを組むためのアセンブリ言語がMIXAL(MIX Assembly Language). 参考 MIX (プログラミング) -…

Knuth's Power Tree Method

指数の計算 a^nを素朴に計算するとn-1回の乗算が必要になる.例えばa^5なら a^2 = a * a a^3 = a^2 * a a^4 = a^3 * a a^5 = a^4 * a しかし,少し工夫することによって乗算の回数は節約できる.例えばa^15は5回の乗算で計算できる. a^2 = a * a a^4 = a^2 …

igraphパッケージの使い方 2.グラフオブジェクトのプロット

プロット igraphパッケージにはグラフオブジェクト(igraphクラス)をプロットするためのplot.igraph()関数が用意されている.勿論,使う場合はplot()関数にグラフオブジェクトを渡すだけでいい. > ## plot.igraph()が用意されている > g <- graph.tree(15) >…

igraphパッケージの使い方 1. グラフオブジェクトの作成と取り扱い

近頃Rのigraphパッケージで遊んでるんだけど割と面白いので使い方を忘れないうちにメモっておく. グラフはプロットした方が理解しやすいんだけどとりあえず今回はグラフオブジェクトの作成と要素へのアクセスとかその辺.プロットは次回. グラフって何ぞと…

Rのanimationパッケージとigraphパッケージでプリム法をアニメーション表示

せっかくさっき(Problem 107 - もうカツ丼でいいよな)プリム法を実装したので,Rのanimationパッケージでクラスカル法のシミュレーション - ぬいぐるみライフ?の真似してアニメーション化してみた.プリム法についてはプリム法(最小全域木問題)を参考にし…

ペル方程式

参考:ペル方程式 - Wikipedia 数論よくわからん… いや説明聞いたらたぶんその場では分かった気になるんだろうけどすぐに忘れてしまう. よくわからんものは結果だけ暗記しちゃった方が実用的には良いのかもしれないなーとかそんなことを思うこの頃. いや,…

平方根を連分数展開したときの循環節を掃きだす

Project EulerのProblem 66を解く際に平方根の連分数を求める関数を書きました。これについてちょっとメモを。 それと当然ながらProject EulerのProblem 64〜66あたりのネタバレになっちゃいます。注意して下さい。 ## 連分数の循環節を掃きだす rep.frac <-…