#ユークリッドの互除法とは
ユークリッドの互除法とは2つの自然数の最大公約数を求める手法の一つです。
#計算の仕方
二つの自然数$x_0$と$x_1$に対して、$x_0$と$x_1$の最大公約数は次の手順により求めることができます。
Step 1：$x_0$を$x_1$で割り、その余りを$x_2$とする
Step 2：$x_1$を$x_2$で割り、その余りを$x_3$とする
Step 3：$x_2$を$x_3$で割り、その余りを$x_4$とする
： （この操作を割り切れるまで繰り返す）
Step n：$x_{n-1}$を$x_n$で割ると割り切れた。このとき$x_n$が最大公約数である
#なぜ最大公約数を求められるのか
例）34と12の最大公約数をユーグリッドの互除法を利用して求める
34÷12＝2…10 ⇔ 34=12×2＋10 …①\\
12÷10＝1…2 ⇔ 12＝10×1＋2 …②\\
10÷2＝5…0 ⇔ 10＝2×5＋0 …③\\
③より2が10の約数であることが分かる
②より12は（2が約数である）10に2を足したものである。
したがって2が12の約数であることが分かる
①より34は（2が約数である）12を2倍した数に（2の約数である）10を足したものである。
したがって2が34の約数であることが分かる
よって、2は34と12の公約数であることが分かる。
以下の図は34×12個の正方形を敷き詰めた様子を表しています。
図より34×12の長方形を埋め尽くすことが出来る一番大きな正方形の一片の長さが2であることがわかります。したがって34と12の最大公約数は2となります。
#計算例
990115と11126の最大公約数をユークリッドの互除法を用いて求める
990115÷11126=88…11027\\
11126÷11027=1…99\\
11027÷99=111…38\\
99÷38=2…23\\
38÷23=1…15\\
23÷15=1…8\\
15÷8=1…7\\
8÷7=1…1\\
7÷1=7…0\\
以上の計算より990115と11126の最大公約数は1であると分かる。
#ユークリッドの互除法を用いたProcessingコード
これらは巴山竜来さんの著書「数学から創るジェネラティブアート」のコード1.2、1.4（p51、54）を元に作成したものです。
例①
例①のコード
//横縦比がnumA:numBの長方形を正方形によって分割
int numA = 9;
int numB = 38;
int scalar = 15; //長方形の拡大倍率
numA *= scalar; //数値の大きさを拡大
numB *= scalar;
//プログラム実行中に動く変数
int wd = numB; //分割に使う正方形の幅の大きさ（初期値numB）
int xPos = 0; //正方形のx位置（初期値0）
int yPos = 0; //正方形のy位置（初期値0）
int itr = 0; //分割の繰り返し回数（初期値0）
color col; //色のための変数
//描画
size(600, 600); //描画ウィンドウサイズ
background(255); //背景色を設定
//繰り返し処理
while (wd > 0) { //幅が0になるまで以下を実行
itr++; //繰り返し回数を1増やす
if (itr % 2 ==1) { //繰り返し回数が奇数のとき、x軸方向への正方形を増やす
while (xPos + wd <= numA) { //幅を足したとき、長方形を超えなければ以下を実行
fill(color(random(255),10,110,128)); //正方形を塗りつぶす色の設定。赤、緑、青の比率と透明度を指定
rect(xPos, yPos, wd, wd); //（xPos,yPos）を左上の頂点とする1辺wdの正方形を描画
xPos += wd; //x位置を更新
}
wd = numA - xPos; //幅を更新
} else { //繰り返し回数が偶数のとき、y軸方向へ正方形を加える
while (yPos + wd <= numB) { //幅を足したとき、長方形を超えなければ以下を実行
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd); //（xPos,yPos）を左上の頂点とする1辺wdの正方形を描画
yPos += wd; //y位置を更新
}
wd = numB - yPos; //幅を更新
}
}
例②
例①に、同じ形の長方形をランダムな位置に発生させる
例②のコード
int numA = 9;
int numB = 38;
int scalar = 15;
numA *= scalar;
numB *= scalar;
int wd = numB;
int xPos = 0;
int yPos = 0;
int itr = 0;
color col;
size(700, 700);
background(255);
float RAN = random(50,700-numA); //乱数RANを作成
float DOM = random(700-numB); //乱数DOMを作成
while (wd > 0) {
itr++;
if (itr % 2 ==1) {
while (xPos + wd <= numA) {
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd);
fill(color(random(180,255),230,10,128));
rect(RAN, DOM, wd, wd); //（RAN,DOM）を左上の頂点とする1辺wdの、例①とは別の正方形を描画
xPos += wd;
RAN += wd; //x位置を更新
}
wd = numA - xPos;
} else {
while (yPos + wd <= numB) {
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd);
fill(color(random(180,255),230,10,128));
rect(RAN, DOM, wd, wd); //（RAN,DOM）を左上の頂点とする1辺wdの、例①とは別の正方形を描画
yPos += wd;
DOM += wd; //y位置を更新
}
wd = numB - yPos;
}
}
例③
例②に、もう一つ同じ形の長方形と円をランダムな位置に発生させる。
例③のコード
int numA = 9;
int numB = 38;
int scalar = 15;
numA *= scalar;
numB *= scalar;
int wd = numB;
int xPos = 0;
int yPos = 0;
int itr = 0;
color col;
size(700, 700);
background(255);
float RAN = random(50,700-numA);
float DOM = random(700-numB);
float ran = random(50,700-numA); //乱数ranを作成
float dom = random(700-numB); //乱数domを作成
while (wd > 0) {
itr++;
if (itr % 2 ==1) {
while (xPos + wd <= numA) {
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd);
fill(color(random(180,255),230,10,128));
rect(RAN, DOM, wd, wd);
fill(color(100,random(100,180),200,128));
rect(ran, dom, wd, wd); //（ran,dom）を左上の頂点とする1辺wdの正方形を描画
xPos += wd;
RAN += wd;
ran += wd; //x位置を更新
}
wd = numA - xPos;
} else {
while (yPos + wd <= numB) {
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd);
fill(color(random(180,255),230,10,128));
rect(RAN, DOM, wd, wd);
fill(color(100,random(100,180),200,128));
rect(ran, dom, wd, wd); //（ran,dom）を左上の頂点とする1辺wdの正方形を描画
yPos += wd;
DOM += wd;
dom += wd; //y位置を更新
}
wd = numB - yPos;
}
}
fill(color(random(255),10,110,128)); //色を指定
ellipse(random(100,600), random(100,600), 200, 200); //x座標y座標共に100以上600未満の位置を中心とする直径200の円を描画
例④
例①に円を発生させ、例①の長方形をバラバラにしたものをランダムな位置に発生させる
例④のコード
int numA = 9;
int numB = 38;
int scalar = 15;
numA *= scalar;
numB *= scalar;
int wd = numB;
int xPos = 0;
int yPos = 0;
int itr = 0;
color col;
size(600, 600);
background(255);
while (wd > 0) {
itr++;
if (itr % 2 ==1) {
while (xPos + wd <= numA) {
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd);
rect(random(1,600), random(1,600), wd, wd); //x座標y座標共に1以上600未満の位置を左上の頂点とする1辺wdの正方形を描画
xPos += wd;
}
wd = numA - xPos;
} else {
while (yPos + wd <= numB) {
fill(color(random(255),10,110,128));
rect(xPos, yPos, wd, wd);
rect(random(1,600), random(1,600), wd, wd); //x座標y座標共に1以上600未満の位置を左上の頂点とする1辺wdの正方形を描画
yPos += wd;
}
wd = numB - yPos;
}
}
fill(color(random(255),10,110,128));
ellipse(160, 300, 200, 200); //（160,300）を中心とする直径200の円を描画
例⑤
作成した長方形を、比率を変えることなく正方形に縮める。色に統一感を持たせる
例⑤のコード
int numA = 17;
int numB = 29;
float ratio = (float) numB / numA; //比率
float wd = width; //長方形の縦または横の長さ
float xPos = 0;
float yPos = 0;
int itr = 0;
size(500, 500);
colorMode(HSB, 360, 100, 100);
while (wd > 0.1){ //wdが許容誤差(0.1)より大きければ以下を実行
itr++;
if (itr % 2 == 1){
while (xPos + wd * ratio < width + 0.1){ //xPos+wd*ratioがwidthを超えないとき以下の文を実行
fill(color(random(180,300), 35, 100)); //色相、彩度、明度を設定
rect(xPos, yPos, wd * ratio, wd); //(xPos,yPos)を左上の頂点とする縦wd横wd*ratioの長方形を描画
xPos += wd * ratio; //xPosにwd*ratioを加える
}
wd = width - xPos; //wdにwidth-xPosを代入
} else {
while (yPos + wd / ratio < width + 0.1){ //yPos+wd/ratioがwidthを超えないとき以下の文を実行
fill(color(random(180,300), 35, 100));
rect(xPos, yPos, wd, wd / ratio); //(xPos,yPos)を左上の頂点とする縦wd/ratio横wdの長方形を描画
yPos += wd / ratio; //yPosにwd/ratioを加える
}
wd = width - yPos;
}
}
色の指定をせず元のコード1.4の通り実行すると以下のような図が描画される
もとのコード
colorMode(HSB, 1);
fill(color(random(1), 1, 1));
#参考文献
・巴山 竜来『数学から創るジェネラティブアート』技術評論社、2019年
p51コード1.2（例①～④）
p54コード1.4（例⑤）
・Casey Reas、Ben Fry、船田 巧(翻訳)『Processingをはじめよう 第2版』オライリージャパン、2016年