FC2ブログ

ユークリッドの互除法の逆演算(?) from azui


見る
(1,1,●)→(2,1)(2,1)
(1,0,●)→(1,0)(1,1)

(2,1)→(3,1)(3,2)
(2,1)→(3,1)(3,2)

(3,1)→(4,1),(4,3)
(3,2)→(5,2,)(5,3)

(4,1)→(5,1)(5,4)
(4,3)→(7,3)(7,4)
(5,2)→(7,2)(7,5)
(5,3)→(8,3)(8,5)

(5,1)→(6,1)(6,5)
(5,4)→(9,4)(9,5)
(7,3)→(10,3)(10,7)
(7,4)→(11,4)(11,7)
(7,2)→(9,2)(9,7)
(7,5)→(12,5)(12,7)
(8,3)→(11,3)(11,8)
(8,5)→(13,5)(13,8)

...


この二分木を構成するルールは次の単純なものです。

(m,n)→(m+n, m)(m+n, n)

この二分木ははじめの根(ルート)の互いに素か、そうでないかの情報を共有(コピー)しているようです。(当然かも・・)
そして、この二分木はすべての「互いに素の組」をもれなく、重複なく生成するようです。

ネットに三分木で同じようなことができるものがあるようです。
互いに素な整数の組の生成
(W)互いに素な整数の組の生成

この(1,1,●),(1,0,●)から生成した二分木を自然数k倍したものが
「互いに素でないもの組」をもれなく、重複なく生成するようです。

k(1,1,●)→k(2,1) k(2,1)
k(1,0,●)→k(1,0) k(1,1)

k(2,1)→k(3,1) k(3,2)
k(2,1)→k(3,1) k(3,2)

k(3,1)→k(4,1), k(4,3)
k(3,2)→k(5,2,) k(5,3)

k(4,1)→k(5,1) k(5,4)
k(4,3)→k(7,3) k(7,4)
k(5,2)→k(7,2) k(7,5)
k(5,3)→k(8,3) k(8,5)
..


たとえば,k=2なら

(2,2,○)→(4,2) k(4,2)
(2,0,○)→(4,0) k(2,2)

(4,2)→(6,2) (6,4)
(4,2)→(6,2) (6,4)

(6,2)→(8,2), (8,6)
(6,4)→(10,4,) (10,6)

(8,2)→(10,2) (10,8)
(8,6)→(14,6) (14,8)
(10,4)→(14,4) (14,10)
(10,6)→(16,6) (16,10)
..

当然ですが(1,1,●),(1,0,●)から生成した互いに素の二分木の中に
(5,1)(5,2)(5,3)(5,4)がすべて含まれていれば5は素数。
(7,1)(7,2)(7,3)(7,4)(7,5)(76)がすべて含まれていれば7は素数。
などといえるでしょう。

from azui



互いに素な整数の組の生成
(W)互いに素な整数の組の生成

P.S
この二分木を逆走することは「ユークリッドの互除法」を行っていることと同じです。

from azui
スポンサーサイト

comment

Secret

プロフィール

syarekoube

Author:syarekoube
しゃれこうべとあずいの2人によるブログです。
主にアクションゲーム制作について発表しています。
あと、数学の研究です。

カテゴリー
最近の記事
最近のコメント
最近のトラックバック
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

ブログ内検索
RSSフィード
リンク