こんにちは。
今回は「ウラムの螺旋をつくってみよう」という題です。
ウラムの螺旋とは
ウラムの螺旋は、自然数を螺旋状に並べて素数だけに色をつけた図で、所々に一直線上に並んだ部分が見えます。
素数という謎の数でも規則性を感じるところがあるという点で面白いです。
もう少し広い範囲で描画したのが、アイキャッチにあるような図です。
プログラム化する
螺旋状に並べる
まずは、数字を螺旋状に並べていきます。
調べてみると十人十色で、様々なやり方があるようなので、自分のわかりやすいものを使ってみてください。
（自分はいろいろ調べた結果、自分で考えたものが一番わかりやすいという結論に至って以下のような方法を考えましたが、結局一番最初に参照したサイトのものと似たようなものができました。）
int number = 1; //数字 float x, y; float len; int turnedNumber = 1; //曲がるときの数字 float difference = 1; //螺旋の一辺の長さ int turnCounter = 0; //曲がった回数 void setup(){ size(500, 500); background(0); //初めの位置 x = width/2; y = height/2; len = 40; //数字の間の距離 } void draw(){ text(number, x, y); //数字の描画 //曲げるべきかの判断（後述） if(number == turnedNumber+difference){ //今の数字が曲がるべき所の数字と同じであったら turnedNumber = number; //今の数字を曲がったときの数字として保存 turnCounter ++; //曲がった回数を1増やす if(turnCounter % 2 == 0){ //曲がった回数2回毎に difference += 1; //一辺の長さを1増やす } } //曲げる方向の指定（後述） switch(turnCounter % 4){ //曲がった回数を4で割ったときの余りで場合分け case 0: //割り切れたとき x += len; //右方向に break; case 1: //1余ったとき y -= len; //上方向に break; case 2: //2余ったとき x -= len; //左方向に break; case 3: //3余ったとき y += len; //下方向に break; } number ++; //数を1増やす }
曲がるべきかの判断
曲がるべきかの判断は、今の数字が曲がるべきときの数字と同じ値になったら曲がった回数を増やすという処理によって行っています。
曲がるべきときの数字は、1、2、3、5、7、10、13、17、…となっています。
（便宜上、1のときも曲がると考える。）
これをturnedNumberで管理します。
この数列の各数字の間で差をとると、1、1、2、2、3、3、4、…となり、2個毎に1増える数列となります。
これをdifferenceで管理します。
プログラム的には、もし今の数字がturnedNumber+differenceと同じであった場合、そこで曲がらなければならないのでturnCounterを1増やして曲がったことにする、という流れです。
順に見ていくと、初めは、
number = 1 turnedNumber = 1 difference = 1 turnCounter = 0
となっています。
このとき、turnedNumber+difference = 2となり、曲がるべきところはnumber = 2のときとわかります。
今はnumber = 1なので何もしません。
drawが一回終わるとnumber ++;によりnumber = 2となるため、曲がったことにする処理が走ります。
turnedNumberを今の数字に置き換える。
（turnedNumber = 2）turnCounterを1増やして曲がったことにする。
（turnCounter = 1）turnCounterが2で割り切れる値のときにdifferenceを1増やす。
（turnCounter = 1のため実行せず、difference = 1のまま）
これによりturnedNumber+difference = 2となり、次に曲がるべきところはnumber = 3のときとわかります。
再びdrawが終わるとnumber ++;によりnumber = 3となるため、曲がったことにする処理が走ります。
・・・・・
というような流れで曲がるべきところで曲がったことにする処理が実行されるようになっています。
曲がる方向の指定
曲がる方向の指定は、曲がった回数を4で割ったときの余りによって場合分けしています。
これは、曲がる方向が右、上、左、下、右、…という順で繰り返されるため使える方法です。
処理の中身はコードを見ればわかると思うので、具体的に中身を見てみます。
初めは、
turnCounter = 0
となっています。
初め（number = 1）のときは、turnCounter%4 = 0のため、x += len;により右方向へ進みます。
1回曲がった（number = 2、turnCounter = 1）ときは、turnCounter%4 = 1のため、y -= len;により上方向へ進みます。
2回目（number = 3、turnCounter = 2）では、turnCounter%4 = 2のため、x -= len;により左方向へ進みます。
numberが4のときはturnCounterは変わらないため、turnCounter%4 = 2でx -= len;によりそのまま左方向へ進みます。
3回目（number = 5、turnCounter = 3）では、turnCounter%4 = 3のため、y += len;により下方向へ進みます。
4回目（number = 7、turnCounter = 4）では、turnCounter%4 = 0のため、x += len;により右方向へ進みます。
・・・・・
以降同様にして、反時計回りに並んでいきます。
実行すると、数字が螺旋状に書かれました。
ただ、このままだと画面外になってもずっと書き続けるので、
if(x < 0 || width < x || y < 0 || height < y){ noLoop(); //drawを止める }
と追加しておくことにします。
続いて、数字同士を線で結んでみます。
それに伴って、数字の描画はやめることにします。
int number = 1; float x, y, px, py; float len; int turnNumber = 1; float difference = 1; int turnCounter = 0; void setup(){ size(500, 500); background(0); x = width/2; y = height/2; //ひとつ前の位置 px = x; py = y; len = 40; } void draw(){ if(number == turnNumber+difference){ turnNumber = number; turnCounter ++; if(turnCounter % 2 == 0){ difference += 1; } } switch(turnCounter % 4){ case 0: x += len; break; case 1: y -= len; break; case 2: x -= len; break; case 3: y += len; break; } stroke(255); //線を白く line(px, py, x, y); //ひとつ前の位置と今の位置との間で線を引く //ひとつ前の位置を保存 px = x; py = y; number ++; if(x < 0 || width < x || y < 0 || height < y){ noLoop(); } }
実行すると、線が螺旋状に描かれるようになりました。
素数の判定と描画
では、素数かどうか判定して、その位置に円を描くようにしてみます。
まずは素数の判定から。
素数の判定方法は様々あるようですが、一番わかりやすいであろう「エラトステネスのふるい」を使ってみます。
エラストテネスのふるいは、ある数を2からその数-1までの値で割ってみて、どれかひとつでも割り切れたらその数は素数ではない、というものです。
（そもそも素数の定義が「2以上で、1とその数自身以外で割り切れない自然数」なので方法としては単純かと思います。）
これをプログラムで表すと、
boolean isPrime(int num){ //boolean型の値を返す関数 if(num == 1){ //numが1だったら return false; //素数でない } for(int i = 2; i < num; i ++){ //2からnum-1まで繰り返す if(num % i == 0){ //もしnumをiで割ったときに割り切れたら return false; //素数でない } } return true; //上記の条件を満たさない数は素数 }
例えば「println(isPrime(10));」などとすれば「false」、「println(isPrime(11));」などとすれば「true」と返されるはずです。
追記（2022/03/11）
2~num-1までの数で割るという操作を行うと計算数が多くなって描画に時間がかかるので、
for(int i = 2; i < num; i ++){
を、
for(int i = 2; i <= sqrt(num); i ++){
とすると計算数が簡単に減らせます。
例えば、num=20のときを考えてみます。
20を自然数のかけ算で表すには、1×20、2×10、4×5、5×4、10×2、20×1となります。
（5×4、10×2、20×1の部分は前半と同じ形なので「折り返し」と呼ぶことにします。）
変更前のままでは、iが2、4、5、10のときに割り切れるので素数ではない、という判定法になります。
しかし、2×10から、2で割り切れるならば10で割り切れることもわかりますし、4×5から、4で割り切れるならば5で割り切れることもわかります。
そこで、sqrt()を使ってiを20の平方根（= $2 \sqrt{5}$ = 4.4…）までにすることで、折り返し後の計算を省くことができ、計算数を減らすことができるというわけです。
以上
次に、素数のときに円を描くようにします。
draw()内に、
if(isPrime(number) == true){ //素数のときに ellipse(x, y, 10, 10); //円を描く }
と追加すれば実装できます。
実行すると、素数の位置に円が描かれるようになりました。
これでウラムの螺旋の完成です。
線を消して素数の描画方法を変え、もっと大きな数まで適用すると、
所々で直線的に並んでいる部分が見えますね。
描画方法を変えてみる
以上でウラムの螺旋は完成しましたが、あまりに点の数が多いと描画に時間がかかります。
それは、drawを何度も実行しているからです。
drawを実行するスピードはframeRate()で指定されており、デフォルトでは60、つまり1秒間に60回実行するということになっています。
for文の具体的な実行速度はわかりませんが、早いことは確かです。
for文に組み込んでしまえば、一度drawを実行するだけで全て描画できるので完成までの時間が短くなります。
（frameRate(10000);などとしても早くはなる）
実装方法は簡単で、draw()内のコード全てを「for(int number = 1; number < 任意の値; number ++)」といったfor文で囲ってやればできます。
大きすぎると全て描画するまでに少し時間がかかりますが、for文を使わないよりは全然早いです。
まとめ
以上で、processingでウラムの螺旋を描くことができました。
螺旋だけでなく、何かしらの素数番目で何か処理をするというようにすると面白いかもしれません。
