メインコンテンツへスキップ
見出し画像

ウラムの螺旋を描くPythonプログラム

    今回の記事は完全に深夜テンションで作ったPythonプログラムの紹介です。

    ウラムの螺旋という一部層には有名な数学の特徴があります。簡単に言うと、自然数をある一定の法則で並べると、素数が斜めの線としてつながって見えるという特徴になります。

    なんとなくPythonで作ってみようと思ったら結構大変だったので記事にしました。

    1. ウラムの螺旋とは

    ウラムの螺旋とは、その名の通り数を螺旋状に並べていったものです。具体的には下のようになります。

    画像
    時計回りの渦巻きのような配置になっている

    ここで、素数のところの四角を別の色で塗ると斜めの線が現れる、というのが大きな特徴です(これについては後日別の記事で書こうと思っています)。

    2. プログラム化のポイント

    今回はtkinterで作りましたが、いくつかプログラムで分かりにくいところを書いておきます。

    (1) 素数の判定

    素数の判定は既に記事にしていますが、その方法だと正確ではあるものの時間がかかります。今回は演算の速さの方が優先なので、フェルマーテストを使って判定します。

    ↓以前書いた記事

    フェルマーテストとは、フェルマーの小定理を利用した素数判定法です。100%素数という断定はできないですが、素数であることがほとんどでかつ計算も速いです。

    【フェルマーの小定理】
    aを2以上の自然数、pを素数とする。このとき、pの倍数でない全てのaにおいて、ap−1≡1 (mod p)  が成り立つ。aを2以上の自然数、pを素数とする。\\このとき、pの倍数でない全てのaにおいて、\\a^{p-1}\equiv1  (\mathrm{mod}  p)    が成り立つ。

    mod p\mathrm{mod}  pとは「ppで割った余り」のことです。条件を満たす全てのaaにおいてap−1÷pa^{p-1}\div pのあまりが11ならppは素数、という定理です。

    この定理を使うのですが、実際にすべてのaaに対して判定することは不可能です(aaは無限に存在するため)。そこで、3030以下の素数に限定して判定します。この方法だともちろん100%とは言えませんが、これでもかなり精度は良いです。

    (2) 罫線の表現

    こういうマス目の罫線を引くときに便利な手法ですが、いちいち線を引くと画面の解像度の問題などで一部不均一に見えることがあります。そこで、背景を黒塗りしたうえで等間隔に白い四角を敷き詰めてマス目を作っていきます。この方法だと素数であるときの背景は色を変えるだけでよいので汎用性も高いです。

    (3) 数の描画

    一番の難関がココで、螺旋の数字をどのように書くかという問題です。私は素直に螺旋の通りに書いていくプログラムにしましたが左上からとかでも頑張ればいけそうです。

    参考までに、私の案の概要を書きます。
    ①1,2,3を書く
    ②「2個進んで90°右に回転」を2回繰り返す(このとき数字も書く)
    ③「3個進んで90°右に回転」を2回繰り返す(数字も書く)
    ④「4個進んで90°右に回転」を2回繰り返す(数字も書く)
    ⑤「5個進んで(以下略
    ⑥この法則を埋まるまで繰り返す

    3. プログラムコード

    最後にプログラムコードです。
    深夜テンションで作ったので汚いうえにコメントもつけてないのはご了承ください。

    import tkinter as tk
    from tkinter import messagebox
    from tkinter import simpledialog
    
    def size(a,text):
        if (int(a)-6)//(len(str(text))) + (len(str(text))-1)//2 <= 2:
            return 1
        else:
            return (int(a)-6)//(len(str(text))) + (len(str(text))-1)//2
    
    def prime_jud(num):
        primelist = [2,3,5,7,11,13,17,19,23,29]
        for i in primelist:
            if i == num:
                continue
            elif pow(i,num-1,num) != 1:
                return False
        return True
    
    
    wh = 600
    
    root = tk.Tk()
    root.title("Ulam's Spiral")
    root.resizable(0,0)
    canvas = tk.Canvas(root,width=wh,height=wh,bd=0,highlightthickness=0)
    canvas.pack()
    
    canvas.create_rectangle(0,0,wh,wh,fill="black")
    root.update()
    
    initvalue = None
    while initvalue == None:
        initvalue = simpledialog.askinteger("Ulam's spiral",
                                            "螺旋の中央の数を入力してください",
                                            initialvalue=1,parent=root,minvalue=1)
        if initvalue == None:
            messagebox.showwarning("Ulam's spiral","入力してください",parent=root)
    
    wid = None
    while wid == None:
        wid = simpledialog.askinteger("Ulam's spiral",
                                      "何周描くかを入力してください(1~40)",
                                      initialvalue=10,parent=root,
                                      minvalue=1,maxvalue=40)
        if wid == None:
            messagebox.showwarning("Ulam's spiral","入力してください",parent=root)
    
    canvas.create_text(wh/2,wh/2,text="処理中…",anchor=tk.CENTER,
                       font=("Consolas",30),fill="white")
    root.update()
    
    a = wh / (wid*2+1)
    for i in range(wid*2+1):
        for j in range(wid*2+1):
            canvas.create_rectangle(a*i,a*j,a*(i+1)-1,a*(j+1)-1,fill="white")
    
    if prime_jud(initvalue):
        canvas.create_rectangle((wh-a)/2,(wh-a)/2,(wh+a)/2,(wh+a)/2,fill="green")
    canvas.create_text(wh/2,wh/2,text=initvalue,anchor=tk.CENTER,
                       font=("Consolas",size(a,initvalue)),
                       fill=("white" if prime_jud(initvalue) else "black"))
    x = wh/2 + a
    y = wh/2
    d = 1
    count_d = 0
    count_roop = 0
    roop = 2
    for number in range(initvalue+1,(wid*2+1)**2+initvalue):
        if prime_jud(number) == True:
            canvas.create_rectangle(x-a/2,y-a/2,x+a/2,y+a/2,fill="green")
            color = "white"
        else:
            color = "black"
        canvas.create_text(x,y,text=number,anchor=tk.CENTER,
                           font=("Consolas",size(a,number)),fill=color)
        count_roop += 1
        if count_roop == roop:
            count_roop = 0
            count_d += 1
            d += 1
        if count_d == (3 if roop==2 else 2):
            count_d = 0
            roop += 1
        if d % 4 == 0:
            x += a
        elif d % 4 == 1:
            y += a
        elif d % 4 == 2:
            x -= a
        else:
            y -= a
    
    root.update()
        

    フェルマーテストの部分(prime_jud\verb|prime_jud|関数)はaaを30以下の素数にしてますが、正確さを求めるなら配列primelist\verb|primelist|にそれ以降の数も追加してください(ただし素数推奨、aaがppの倍数だと機能しないため)。

    実行すると最初の数と螺旋の大きさを入力した後螺旋が表示されるはずです。tkinterなのでPythonさえ入っていればどの機種でも動くと思います。


    4. 次回予告

    まずは最初の数を1と入力すると下のようになるはずです。

    画像

    ところどころに直線は見えますが、あまり長いものはないですね。しかし、少し入力値をいじると下のようにはっきりと長い直線が現れます。

    画像
    右肩下がりのきれいな直線です。

    さて、これを出すにはどうすればいいのでしょうか?

    答えは次回の記事で。

    【ヒント①】
    最初の数が1のとき、右肩下がりの直線上に現れるのは小さい順に1,3,7,13,21,31,43,57,73,…1,3,7,13,21,31,43,57,73,…です。この数列の一般項は…?
    【ヒント②】
    Leonhard Euler\verb|Leonhard Euler|

    数学好きには割と有名かもしれませんが。



    【次の記事】


    この記事が参加している募集

     
     
    数学とPythonが好きな人です。 主に数学と自作のPythonプログラムの解説記事を書いています。 最近はBVE関連にハマってます… X垢(主にBVE):https://x.com/__init__92435

    あなたへのおすすめ