うえぽんSW局

古いタイプの日記ブログです。気まぐれに更新してます。

タグ:数学

 2016年も最後となってしまったので、以前書いた「素数探しの旅」がその後がどうなったか書いておこうと思います。

 まず探していた素数というのは以下のように1234567890123…と続く数列で素数となるものです。
 1
 12
 123
 1234
 12345
 123456
 1234567
 12345678
 123456789
 1234567890
 12345678901
 123456789012
 1234567890123
 :
 :

 以前の記事では以下の桁数において素数(もしくは確率的素数)となることを発見しました。
 171桁
 277桁
 367桁
 561桁
 567桁
 18881桁

 ではこれ以上の桁数で素数は存在するのだろうか?
 というわけで、あれからチマチマと素数を探し続けていました。
 そうして半年かかって21万1761桁までテストしましたが、発見できませんでした
 (もしかしたら自分がミスして見逃している可能性があるかもしれませんので、他の方の検証も欲しい所です)

 長らくチマチマと探していましたが、2016年が終わるのを目途として素数の探索はをこれにて打ち切りにしたいと思います。この挑戦はかなり無茶だったかもしれません。


 以下はもしかしたら素数探索の手助けになるかもしれないメモです。

●一般項
 次の式で求められる(^は乗数、[]は小数点以下切り捨てを意味する)。
 [10^k*1234567890/9999999999]
 for文を使うより一般項で普通に計算した方が速い。

●末尾が1と7だけ探索すれば良い
 2と5の倍数を除外すると末尾が1、3、7、9の4つを探せば良いことが分かるが、3と9も除外することができる。なぜなら各桁の数を合計すると必ず3の倍数になるため(3の倍数を求める方法)。

●最大公約数を求めることでさらに除外
 素因数分解や素数判定は時間がかかるが、最大公約数の計算は比較的高速に求めることができる。
 例えば下の2つの数の最大公約数を求めるとその数は7となり、両方とも素数でないことが分かる。
 123456789012345678901234567890(30桁)
 12345678901234567(17桁)
 この例では桁数が30*k+17の形のときは7の倍数になる(つまり素数ではない)ことを意味するので、その形になるものを素数判定の対象から除外することができる。
 他にも、110*k+87桁、110*k+21桁などが素数の判定から除外できる。
 こういうのをたくさん探しておくことで、素数判定の対象を減らせる。

●素数判定の前に軽く素因数分解した方が速いことも
 桁数が大きくなるとミラー・ラビン素数判定法でもかなりの時間を要する。
 そこで素数判定の前に“軽く”素因数分解をやるやり方も有効になってくる。
 自分はポラード・ロー素因数分解法を使った。


 というわけで2016年はこれでお終いです。
 良いお年を。
このエントリーをはてなブックマークに追加

 日付をyyyymmdd形式の8桁の値とみなしたとき、その値が素数であるのを素数日と呼んでいるそうな。
 例えば、2016年4月1日は20160401となり、この値を判定すると素数であることが分るので、素数日ということになる。

 それならばと、こんな雑学を作ってみたいと思った。

 「今日の日付(A)は素数日です。そして明日の日付(B)も素数日です。このように2日連続で素数日になるのは珍しく、前回は(C)と(D)だったので実に(E)年ぶりとなります」

 さて、(A)~(E)にはどのような数字が入るのか?
 この雑学を披露できるのはいつになるのか?
 という探索をしてみた。


 まず素数日となる候補だが、偶数日は2の倍数になるためこれはまず候補から外れる。
 そして、奇数日が2日連続するのは限られていて、月末の31日と翌月の1日というパターンが候補となる。
 このとき、うるう日の2月29日も月末で奇数日になるなので忘れないようにする。(ついでに年越しの12月31日から1月1日も忘れやすいので注意)
 調べるのは次のようになる。

 1月31日 → 2月1日
 2月29日 → 3月1日(うるう年のみ)
 3月31日 → 4月1日
 5月31日 → 6月1日
 7月31日 → 8月1日
 8月31日 → 9月1日
 10月31日 → 11月1日
 12月31日 → 1月1日

 ここでさらに注意が必要なのが、うるう年(うるう日)について。
 実は4年に1回あるのではなく、400年に97回(100回ではない)になるように設けられているということだ。
 うるう年の規則はこのようになっている。

 (1)4で割り切れる年はうるう年
 (2)ただし100で割り切れる年は平年
 (3)ただし400で割り切れる年はうるう年


 以上を踏まえて、前世紀(20世紀)と今世紀(21世紀)の範囲で2日連続の素数日を探索したところ、以下が該当することが分かった。

 20世紀
 19130731, 19130801
 19210531, 19210601
 19240229, 19240301
 19250131, 19250201
 19301231, 19310101
 19500331, 19500401
 19721231, 19730101
 19781231, 19790101
 19790131, 19790201
 19830331, 19830401
 19871231, 19880101
 19900831, 19900901
 19971031, 19971101

 21世紀
 20020531, 20020601
 20170831, 20170901
 20180731, 20180801
 20201231, 20210101
 20280229, 20280301
 20291231, 20300101
 20361031, 20361101
 20640331, 20640401
 20680831, 20680901
 20750131, 20750201
 20800229, 20800301
 20800531, 20800601
 20811031, 20811101
 20930731, 20930801

 今から一番近いのは20170831と20170901のパターン。
 これはちょうど1年後の今日! というわけで、当初の目的である雑学の披露を忘れないよう、さっそくブログに予約投稿しておこうと思う。
このエントリーをはてなブックマークに追加

 あのコピペの素数にはかなわないが、こんな素数を発見した。

71 ← 素数
701 ← 素数
7001 ← 素数
70001 ← 素数
700001 ← 素数
7000001 ← 素数じゃない (197 * 35533)
70000001 ← 素数じゃない (43 * 61 * 26687)
700000001 ← 素数
7000000001 ← 素数
70000000001 ← 素数じゃない (53 * 1320754717)
700000000001 ← 素数じゃない (41149 * 17011349)
 :
(ずっと素数じゃない)
 :
7000000000000000000000000000000000000000000001 ←たぶん素数


 あのコピペの素数は、ツイッターを検索するといまだに披露しているbotがいくつもあるようだ。
このエントリーをはてなブックマークに追加

 1000000000000066600000000000001は素数だそうな。
 真ん中にある666は獣の数字と呼ばれる不吉な数。
 さらに、両サイドに並ぶ0の数はそれぞれ13個と、これまた不吉な数。
 そして回文になっているので回文素数である。
 このよくできた素数はベルフェゴール素数(Belphegor's prime)と呼ばれているそうな。

 参考:Belphegor's prime - Wikipedia

 ちなみに、666は最初の7つの素数の2乗の総和である。
 2*2 + 3*3 + 5*5 + 7*7 + 11*11 + 13*13 + 17*17 = 666


 以上だとwikipediaからのただの受け売りなので、独自に発見したのを一つ。
 似たような素数がないかと色々素数判定してみたところ、どうやら以下の回文数も素数らしいことが分かった。(「らしい」とするのは素数判定に使ったミラーラビン素数判定法が確率的素数判定法のため。しかし512個の素数でテストしたのでほぼ間違いなく素数だと思う)

 1000000000000077700000000000001

 これはベルフェゴール素数の666を777に置き換えただけである。それも回文素数になるというのは少し驚きだ。

 しかし、自分だけの発見かと思ったら、この数字で検索するとすでに発見した人がいるのが少し悔しい……。それでも、検索件数は少ないし、日本語のサイトはないので、今なら知っている人は少なく自慢できるかもしれない。
このエントリーをはてなブックマークに追加

 「追悼でマンデルブロ集合を作成」の続き。
 前回は double の精度の限界に直面してしまったので多倍長計算ライブラリのGMPを使ってマンデルブロ集合を作ってみました。出力部分だけAviUtlを使っていたりします。

 しかし…動画にしてみようと思ったものの、処理に時間が掛かりすぎるために断念。(1920x1440を一枚出力するのに1時間も掛かる)
 静止画で我慢することにしました。

 で、バックベアードのようなものを発見。

マンデル191_ループ少な


 が、漸化式の最大ループ回数を 2048 から一気に 16384 回まで増やすと、黒かった部分に何かあったりしました。

マンデル191


 周りに鎖みたいなのが 8 本ありますが、円の中では 16 本に増えていることに注目。

 中心にズームすると、

マンデル197


 外側に 16 本の鎖、内側に 32 本とさらに倍になってます。

 さらにズーム。

マンデル200


 32本の鎖が円の中で64本へ増えています。
 そして中心に見覚えのあるものが。

 ズームしてみると、いつものあれがザビエルな感じで出現してハッピーエンド。

マンデル202


[追記]
 あとでこのブログ記事を読み返してみましたが、「ザビエルな感じ」とは自分で書いておいてよく分かりません…。後光的なものを見てそう思ったのでしょうか…。
このエントリーをはてなブックマークに追加

 数学者のマンデルブロー氏が今月の14日に亡くなったそうです。

 時事ドットコム:数学者マンデルブロー氏死去

 追悼ということで、マンデルブロ集合をプロットしてみました。
マンデルブロ集合


 上のは拙作「lua for aviutl」で作成しました。ソースは下の通り。
-- 【マンデルブロー集合】

function func_proc()
    local ycp_edit = aviutl.get_ycp_edit() -- 現在の編集画像領域取得
    local w, h = aviutl.get_size() -- 現在のサイズ取得

    -- 設定項目
    local ar = -0.75 -- 描画座標(実数部)
    local ai =  0.0 -- 描画座標(虚数部)
    local al = 2.5 -- 大きさ
    local loop_max = 64 -- ループの上限

    -- 計算数を減らすための事前計算
    local dcol = 4096.0 / loop_max -- 色の階調幅
    local range = w
    if h > w then range = h end
    range = al / range -- 1ドットあたりの差分

    for y = 0, h do
        local ci = ai + range * (y - h/2) -- 虚数部
        for x = 0, w do
            local cr = ar + range * (x - w/2) -- 実数部
            local zr, zi, i = cr, ci, 0
            while i < loop_max and zr*zr + zi*zi <= 4 do
                zr, zi = zr*zr - zi*zi + cr, 2 * zr * zi + ci
                i = i + 1
            end
            aviutl.set_pixel( ycp_edit, x, y, 4096 - i * dcol, 0, 0 )
        end
    end
end

-- スクリプト終了時に呼ばれる関数
function func_exit()
end

 せっかくAviUtlでプロットしているので、動画にもしてみました。
 ただ、luaでは処理に時間がかかりすぎるため、C言語で作成したプラグインでプロットしてます。



 doubleの精度ではこれが限界です。
 小技として1920x1440で作成して640x480に縮小することでアンチエイリアスの効果を出してます。1920x1440と大きいため、38秒の動画作成に30分以上かかりました。
 BGMは魔王魂さんの音楽素材を使わせていただきました。
このエントリーをはてなブックマークに追加

↑このページのトップヘ