Midnight Floating Thought

From India the sine function was introduced to the Arab world in the 8th century, where the term jya was transliterated into jiba or jyb. Early Latin translations of Arabic mathematical treatises mistook jiba for the Arabic word jaib, which can mean the opening of a woman's garment at the neck. Accordingly, jaib was translated into the Latin sinus, which can mean "fold" (in a garment), "bosom," "bay," or even "curve." Hence our word "sine." The birth of trigonometry また新説が。 the opening of a woman's garment at the neck とは女性の服の首回りの開いたところぐらいの意味だろうか。 さて 前回 の結論としては、アラビア語を調べないと判らない、ということだったので今回はアラビア語。 今まで出てきたどの説もアラビア語は jaib としているが、それらしい単語はむしろ جَيْب (jayb) という形のようだ。 (もちろんアラビア語の transliteration の方式に依るのかもしれないが素直に読めば y に当たる字が入っている) ここで脱線してアラビア文字について述べておこう(もちろん俄知識である)。 アラビア語の文字は右から左に(主に)子音だけ書くというスタイルで、しかも各文字に語頭、語中、語尾の形があるため、なかなか読みにくい。 今回の単語は ج (jīm) が語頭の形で右側の角張った部分と下の点(ここまでが文字そのもの)と上の´(アの音を表す記号)まで、 次の ي (yā) は語中の形で上に一回持ち上がった部分と下の二つの点...

インドの言葉 "jya-ardha" (高さ)が似た発音のアラビア語 "jiba" になり、母音を省いて "jb" のように書く習慣から "jaib" (胸)と混同されてラテン語では "sinus" (胸)に化け、それが今のサイン "sin" のもとだそうです 野﨑昭弘「算数・数学24の真珠」日本評論社 2012 jyā は弦を意味する言葉であり、もともとは半弦を意味する jyā-ardha が使われていたがそれが省略されて jyā が使われるようになったと考えられている。用語 jyā はアラビア語訳されるときにそのまま発音を写して jiba と訳されたが、アラビア語では母音が記されないため jiba と jaib とは同じ綴りとなりいつのまにか「湾」を意味する jaib が使われるようになった。そのためアラビア語の著作がラテン語訳されるときに湾を意味する sinus が使われ、そこから今日の sine が誕生した 上野健爾「円周率が歩んだ道」岩波書店 2013 胸と湾が同じ単語? sin·us,-ūs m indentation, curve, fold, hollow; fold of toga about the breast, pocket, purse; breast, bosom, lap; bay, gulf, lagoon; winding coast; valley, hollow; heart (e.g., of a city), interior; intimacy John C. Traupman, Ph.D., The New College Latin and English Dictionary, third edition, Bantam books 2007 両方の意味がちゃんと載っていた。 アラビア語の jaib の意味を調べないとどちらの説が正しいのか(あるいはラテン語同様広い意味をカバーする言葉でどちらも正解か)不明である。

自然数 $n$ と素数 $p$ が与えられて、$n$ が $p$ で割り切れるかどうか判定したいとしよう。 ふつうは余りを求めて、それが $0$ だったら割り切れる、それ以外なら割り切れない、と判断する。 しかし、暗算でそんな計算をするとき、思い返してみると右から桁を減らしていくことが多い。 たとえば $211$ が $13$ で割り切れないことを確かめようとする場合、1の位の $1$ を打ち消すために $91=7\times 13$ を引き、残りが $120$ だから $13$ では割り切れない、と思考を進めるわけである。 再帰的にこんな手続き $f(n,p)$ を定義すればいい。 1. $n=0$ ならば True を返す。 2. $n$ が $10$ で割り切れるならば $f(n/10,p)$ を返す。 3. $n$ の1の位と同じ1の位を持つ $p$ の倍数(のうち最小のもの)を $kp$ とするとき、$n\ge kp$ ならば $f(n-kp,p)$ を返し、$n\mathrm{い}\mathrm{く}\mathrm{つ}\mathrm{か}\mathrm{注}\mathrm{意}\mathrm{を}\mathrm{述}\mathrm{べ}\mathrm{る}\mathrm{と}、\mathrm{ま}\mathrm{ず}\text{(}p$ は $10$ と互いに素の場合にだけ適用できる。 その $10$ は $d$-進数の $d$ だと思って良い(プログラムで実現するときは $2$-進数で考えることだろう)。 $kp$ は事前にテーブルを用意しておいて辞書引きすれば良い(というか $p$ の1の位で $k$ は決まってしまう)。 特に$2$-進数ならば$k$は常に$1$なので話が簡単である。 他の人、あるいは既存のプログラムで、この方法で割り切れるかどうかの判定を行っている例があるのかどうか知りたいところである。

自然数が与えられたとき、その数が平方因子を持つかどうかの判定は、現在のところ、因数分解してみる以上に効率的な方法が知られていない。 べつに因子自身を知る必要が無いということを考えると、因数分解は手間が掛かりすぎという感覚があり、多分これは多くの(計算数論に多少なりとも興味のある)人に喉に刺さった小骨のような苛立ちをもたらしている。 以下に述べることは、問題の解決ではなく、こんなことを考えてみたけどうまくいかんなあ、という記録である。 整数の難しい問題は、一変数多項式に手がかりを求めると良いと言われる。 多項式が平方因子を持つかどうかの判定は簡単で、$(f,f^{\prime })$ を計算すると平方因子が求まる。 (もちろん $f^{\prime }$ は $f$ を微分したもの、$(,)$ は最大公約因子の記号、である) 例えば $f(X)=X^3+7X^2+8X-16$ とすると、 $f^{\prime }(X)=3X^2+14X+8$ で、 $f(X)$ と $f^{\prime }(X)$ の最大公約因子は $X+4$。 よって $f(X)$ は $X+4$ で2回割り切れる。 整数には微分が定義されていないので、そのまま使えるわけではないが、類似の現象を探すのが良さそうである。 次の関係に注目してみたい。 「$n$ が平方因子を持つ正整数ならば、$(n,\phi (n))>1$」 注意点としては、逆が成り立たないし、$\phi (n)$ の計算の手間も因数分解と大体同等だと思われる、という二つがある。 逆が成り立たないことは、$p_1|p_2-1$ となる $n$ の素因数の組 $p_1,p_2$ がある場合にも $(n,\phi (n))>1$ となることを見れば良い。 オイラー関数の計算の手間が因数分解と同等か正確なところは判らないが、RSA 暗号の安全性と関わってそういう議論があったはずだ。 オイラー関数を計算してはいけないという縛りの下に $(n,\phi (n))>1$ の成立を確かめよう、というのが次のタスクになる。 そこでひねり出したのが次の条件である。 \[\exists a \text{ ...

これは遠い昔、とある研究集会で発表したことのある話である。 概要ぐらいしか公に残されているものがないと思うので、昔のノートを参照しながら書いてみる。 (ちなみに最近このブログにポツポツ書いている数学系の記事は、だいたい昔のノートを読み返して抜き出したものだったりする。) 定義 まずは前段階として、擬素数について思い出しておく。 広義に擬素数とは素数ならば必ず満たす条件を満たしている必ずしも素数でない整数、ということだが、単に擬素数とだけ言えばフェルマーの小定理 「$p$ が素数ならば $a^{p-1}\equiv 1modp$」の式「$a^{n-1}\equiv 1modn$」を満たす合成数 $n$ のことである。 正確にはこのとき「$n$ は基 $a$ の擬素数である」という。 以降簡単のためにこれを「$n$ が $\mathrm{psp}(a)$ を満たす」と表現する(psp とは pseudo prime の略である)。 $n$ は奇数で $\mathrm{psp}(a)$ を満たすとしよう。 すると $n-1$ は偶数であり、2 でちょうど $s$ 回割り切れるとすると $n-1=2^s{n}^{\ast }$ と書くことができる。 もちろん $n^{\ast }$ は奇数である。 さて $n-1$ は偶数であるから(条件式の右辺を左辺に移項すると)平方の差の形なのでよく知られているように和と差の積に因数分解できる。 $$a^{n-1}-1=(a^{\frac{n-1}{2}}+1)(a^{\frac{n-1}{2}}-1)$$ この形の因数分解を $s$ 回繰り返す。 $$a^{n-1}-1=(a^{2^{s-1}{n}^{\ast }}+1)(a^{2^{s-2}{n}^{\ast }}+1)\cdots (a^{n^{\ast }}+1)(a^{n^{\ast }}-1)$$ $n$ が素数の場合、積を割り切ればその因子の一つを割り切る、という性質が成り立つので、右辺の因子の一つを割り切る。 一方 $n$ が合成数の場合、そのような保証はないが、たまたま素数と同じように右辺の因子のただ一つを割り切るかもしれない。 そのような擬素数を強擬素数といい、「$n$ が \(\mathrm{s...

オイラー(totient)関数 $\phi (n)$ は $1$ 以上 $n$ 以下の $n$ と互いに素な整数の個数を表す関数である。 言い方を変えると $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ の位数を表す関数である。 $n$ 次円分多項式の次数という捉え方もある。 この関数が乗法的関数であることはよく知られている。 すなわち $a$ と $b$ が互いに素なとき $\phi (ab)=\phi (a)\phi (b)$ を満たす。 さて一般に、二つの乗法的関数 $f$, $g$ があったとき、次のように積の和をとったもの $f\cdot g(n)=\sum _{d|n}f(d)g(d)$ も乗法的関数である。 よってたとえばオイラー関数の2乗和 $\sum _{d|n}\phi (d{)}^2$ は乗法的関数である。 こういったオイラー関数の2乗和や、より高次のオイラー関数の冪和について何かよく使われる記号がないものか、と昔から知りたく思っている。 ちなみに単なる因子の冪和については ${\sigma }_k(n)$ という記号がある。 $\sigma (n)={\sigma }_1(n)=\sum _{d|n}d$ を一般化したものである。 その考え方を踏襲すると $\sum _{d|n}\phi (d)=n$ なので、$n_k(n)$ になると考えるといいのかもしれない。 試しに OEIS を引くと、 A029939 Sum phi(d)^2; d|n. は出てくるが、3乗の冪和である数列 1,2,9,10,65 が出てこない。 そのぐらい需要がない。 その需要のないものをどうして気にするか、ということはまた改めて書く。

Wilson の定理とは、素数 $p$ に対し $(p-1)!\equiv -1modp$ が成り立つという初等整数論の定理である。 これが重要な定理ということは特にないと思うのだが、大体の教科書に載っている。 証明にはフェルマーの小定理を使ったり原始根を使ったりすることが多い。 しかし、そんな道具立ては解り易くないと思うのだ。 少し一般的な次のことを証明する (Gauss の一般化と呼ばれているようだ): $n$ を $3$ 以上の整数とするとき、$\prod _{i\in \mathbb{Z}/n{\mathbb{Z}}^{\times }}i\equiv (-1{)}^{k}modn$ が成り立つ。 ただし、$k$ は $1$ の平方根の個数の半分。 (証明) $\mathbb{Z}/n{\mathbb{Z}}^{\times }$ は群なので、各元に逆元が存在する。 自分自身が逆元である元以外は、$a$ と $a^{-1}$ が別々に存在して $a\cdot a^{-1}\equiv 1modn$ だから積に寄与しない。 自分自身が逆元である元とは $a^2\equiv 1modn$ ということなので、$1$ の平方根である。 このような元 $a$ に対し、$-a$ も同様に $(-a{)}^2\equiv a^2\equiv 1modn$ を満たす。 $n$ は $3$ 以上と仮定したので、 $a$ と $-a$ は等しくない。 この二つの元の積を考えると、$a\cdot (-a)\equiv -a^2\equiv -1modn$ である。 $1$ の平方根を $2$ 個ずつ組にしたので、$k$ を $1$ の平方根の個数の半分として $\prod _{i\in \mathbb{Z}/n{\mathbb{Z}}^{\times }}i\equiv (-1{)}^{k}modn$ が成り立つ。 (証明終わり) 元の形の Wilson の定理は、奇素数 $p$ に関しては $n=p$ として上の命題を適用すれば $\mathbb{Z}/p\mathbb{Z}$ が体だから \(a^2 \equiv 1 \bmod...

前回 ( abc予想と昔考えたこと )は、素数次円分多項式はその素数が7以上ならばabc予想の仮定の下で平方以上の素冪の値を高々有限回しか取らないということを示した。 素数次以外も同様のことが証明できる、というのはまあ読者の練習問題でもいいのだが、せっかくなので書いてみることにする。 $m$ を合成数とし、$\phi (m)$ が $6$ 以上(つまり $m=4,6,8,10,12$ 以外)と仮定しよう。 $m$次円分多項式 ${\mathrm{\Phi }}_m(X)$ が、$x$ で素冪の値 $p^n$ を取ると仮定する。ここでもちろん $n\ge 2$ である。 円分多項式はよく知られているように $X^m-1=\prod _{d|m}{\mathrm{\Phi }}_d(X)$ を満たすので、 $$x^m-1=p^n\prod {\mathrm{\Phi }}_d(x)$$ と書ける。ただし、右辺の積は $d=m$ 以外の $m$ の約数に亘る。 $x$ と右辺の各因子は互いに素なのでabc予想が使える。 abc予想: 任意の $ϵ>0$ に対して, ある正の定数 $K(ϵ)\ge 1$ が存在して, 次を満たす: $a$, $b$, $c$ が互いに素な整数で $a+b=c$ を満たすならば, 不等式 $$max\{|a|,|b|,|c|\}\mathrm{少}\mathrm{し}\mathrm{余}\mathrm{談}\mathrm{を}\mathrm{挟}\mathrm{む}\mathrm{と}、\mathrm{前}\mathrm{回}\mathrm{も}\mathrm{そ}\mathrm{う}\mathrm{だ}\mathrm{っ}\mathrm{た}\mathrm{の}\mathrm{だ}\mathrm{が}、\mathrm{左}\mathrm{辺}\mathrm{は}\text{(}max\text{)}\mathrm{を}\mathrm{取}\mathrm{る}\mathrm{の}\mathrm{が}\mathrm{大}\mathrm{事}\mathrm{な}\mathrm{の}\mathrm{で}\mathrm{は}\mathrm{な}\mathrm{く}、「\text{(}|a|\mathrm{で}\mathrm{は}\mathrm{ま}\mathrm{ず}\text{(}|a|\text{)}\mathrm{か}\mathrm{ら}\mathrm{使}\mathrm{お}\mathrm{う}。\text{[}{x}^m\mathrm{次}\mathrm{は}\text{(}|c|\text{)}\mathrm{を}\mathrm{使}\mathrm{う}。\text{[}{p}^n\prod {\mathrm{\Phi }}_d(x)\mathrm{式}\mathrm{変}\mathrm{形}\mathrm{を}\mathrm{簡}\mathrm{単}\mathrm{に}\mathrm{す}\mathrm{る}\mathrm{た}\mathrm{め}\mathrm{に}\text{(}ϵ=\frac{1}{m}\text{)}\mathrm{と}\mathrm{お}\mathrm{く}。\text{(}x\text{)}\mathrm{の}\mathrm{評}\mathrm{価}\mathrm{式}\mathrm{の}\mathrm{冪}\mathrm{は}\mathrm{次}\mathrm{の}\mathrm{よ}\mathrm{う}\mathrm{に}\mathrm{な}\mathrm{る}。\text{[}m-(m-\phi (m)+1)(1+\frac{1}{m})=\phi (m)-2+\frac{\phi (m)-1}{m}$$ 一方 $p$ の評価式の右辺の $x$ の冪は \[\epsilon m - \epsilon \varphi(m) + 1 + \epsilon = 2 - \frac{\varp...

gentoo と python と eselect と , dev-lang/python と /usr/lib/portage/pym , 0xF 0xB 0x31 0xFF と続いてきたシリーズも今回でひとまず終わり。 前回 libSystem.B.dylib で死ぬところまで見たが、 Gentoo Bugs #475284 では回避策の議論が進んだ。 eselect のコードでどこがこのバグを踏む原因になっているのかというと、 エラー出力のファイル記述子を置き換える辺りらしい。 決め打ちではエラーが起こるが、自動で振る機能は bash-4.1 以降の機能、というのが回避するコードを書く際の悩みどころだったようだ。 ともかく、対策済みのバージョンが eselect-1.3.6 としてリリースされた。 一件落着だ。 とはいえ、根本原因が塞がれたわけではないのでバグはまだオープンで、 バグタイトルが "app-shells/bash-4.2_p39-r1: "exec 3>&2" causes illegal instruction (seen with app-admin/eselect-1.3.5)" と大幅に変わって bash チームに投げられている状態である。

app-admin/eselect-1.3.5 問題の続き。 一応復習しておこう。 PORTAGE_ELOG_COMMAND で呼び出された gentwoo が eselect を呼び出したところで死ぬ。 環境変数を gentwoo に引き渡しておけば死なない。 Gentoo Bugs #475284 に報告してみて得た情報なども加味しながらもう少し情報を補足しよう。 環境変数が空っぽだと死ぬので env -i /path/to/eselect とすればいつでも再現できる、と主張したのだが、 これで現象が再現できるのは(少なくとも今のところは)私の Gentoo Prefix on OS X でだけである。 そもそも、eselect は bash スクリプトで、死んでいるのは具体的にどこなのか、と聞かれて core を吐かせることにする。 ulimit -c unlimited としておく(と core ファイルは /cores に core.PID という名前で残される)。 死んでいるのは bash の中だ。 bash 自体が死ぬような現象には遭遇した経験が無かったので、どうにもデバッグの糸口が摑めなかった。 とりあえず eselect の中に echo コマンドをいくつか挟んでみた。 どうも死ぬ場所は一定していないらしい(埋め込んだ echo が実行される前に死んだり、実行してから死んだりまちまち)。 とすると、むしろメモリーのゴミを踏んでしまっているか? メモリーエラーには valgrind。 ここでも環境変数を渡さないように env -i /path/to/valgrind /path/to/bash /path/to/eselect。 すると次のような出力を得る vex x86->IR: unhandled instruction bytes: 0xF 0xB 0x31 0xFF ==64989== valgrind: Unrecognised instruction at address 0x2a5ce9. ==64989== at 0x2A5CE9: _dispatch_mgr_invoke (in /usr/lib/libSystem.B.dylib) ==64989== by 0x2A4F58: _dispatch...

昨日の投稿で、gentwoo が上手く動かないのは python と eselect のせい、と書いた。 dev-lang/python は 2.7.3-r3 から 2.7.4 の間に何が変わったのか、ということを調べてみた。 昨日書いたように、portage.util の ImportError が第一の原因なので、それを見てみる。 python-2.7.3-r3 では sys.path に ${EPREFIX}/usr/lib/portage/pym が含まれているが、python-2.7.4 では含まれない。 では、python-2.7.3-r3 ではどこでこのパスを設定しているのか。 それは site.py の中である。 site.py にそれを書き加えているのはパッチ tar ボールの中の 03_all_add_portage_search_path.patch である。 python-2.7.4 ではこのパッチが消えている。 おお、これだ。 だがちょっと待て。 だとすると、普通に Gentoo Linux を使っている人も同じ症状になってしまわないか? ということで、VirtualBox に Gentoo Linux 環境をお手軽に用意するために liveDVD イメージをダウンロードして、起動。 最新の liveDVD とはいえ昨年末のなので、python のバージョンは 2.7.3 である。 当然、emerge --sync して emerge -1 =python-2.7.5 で 2.7.5 に上げる。 python2.7 を立ち上げて、import sys; print sys.path。 うん、なぜか /usr/lib/portage/pym がちゃんと含まれている。 パッチは消えたのだから、site.py には設定されていない。 環境変数? python -E で環境変数を無視して立ち上げると確かに pym のパスは消える。 $ env | grep pym PYTHONPATH="/usr/lib/portage/pym" そう、環境変数 PYTHONPATH で設定しているんだ。 環境変数自体は /etc/env.d/05portage で定義されていた。 翻って Prefix 環境で調べてみると、確か...

Gentoo の portage の機能として、make.conf で PORTAGE_ELOG_COMMAND にログ出力用の任意のコマンドを指定して実行させる仕組みがある。 gentwoo はそれを利用したログ収集のサイトで、そこにログを送るために betagarden overlay の app-portage/gentwoo をインストールして PORTAGE_ELOG_SYSTEM="custom:* save" PORTAGE_ELOG_COMMAND="gentwoo '${PACKAGE}' '${LOGFILE}'" といった行を make.conf に書き加えてある。 最近、といってももう3週間ぐらい、この gentwoo の呼び出しでエラーが発生するのである。 二種類のパターンがある。 一つめは gentwoo-2.7 という(Python 2.7 で実行される)スクリプト本体で発生するエラー。 Traceback (most recent call last): File "/Users/tetsushi/Gentoo/usr/bin/gentwoo-2.7", line 11, in from portage.util import getconfig ImportError: No module named portage.util !!! PORTAGE_ELOG_COMMAND failed with exitcode 1 二つめは gentwoo というラッパーシェルスクリプトで発生するエラー。 /Users/tetsushi/Gentoo/usr/bin/gentwoo: Execution of 'eselect python show --python2' failed !!! PORTAGE_ELOG_COMMAND failed with exitcode 1 どちらのエラーも portage がインストールする ${EPREFIX}/usr/lib/portage/pym/portage/elog/mod_custom.py で spawn_bash の引数に env=os.env...

初人間ドック。 バリウム飲んでぐるぐる回されると話には聞いていたが、なるほどぐるぐる回らされた。 バリウムが飲みにくいとか言われたが、ラッシーと変わらないぐらいじゃないの。 今日は身長が169センチ台の半ばだった。 いつもは168センチ台後半ぐらいなので、微妙に高めに出ている。 眼底検査の時に「睫毛が長くて邪魔」とか言われたが、ごめんなさい生えてる向きがわりと下向きなだけだと思います。 裸眼視力は相変わらず1.5あった。 腹囲を測るときに「ズボンのウエストサイズより太めに出るかもしれません」とか医者が言ったが、(私にとっては)逆です、先生。 いわゆる"メタボ"体型を念頭に置いて検査が出来上がっているんだな、と。 そんなこんなで検査が終わって、バリウムを排出するために下剤を飲んで下さい、という指示に素直に従った。 そして、飯を食って会社に向かう電車の中で腹痛が始まった。 何が印象に残ったって、もう何よりもこの腹痛による消耗した気分だった。

その昔、円分多項式に整数を代入したとき素冪が出てくることがあるのか、というようなことを考えたことがある。 その時は、円分多項式 ${\mathrm{\Phi }}_m(X)$ に対し素数 $p$ と原始 $m$ 乗根 $x$ を固定して、 $x$ から始まる $p$ 進 $m$ 乗根の展開に $0$ が沢山続くと…。 詳細は忘れたが、まあ不都合が発生するということになっていたはずである。 というようなわけで、$p$ 進展開を計算させてみた記憶がある。 最近 ABC予想入門 という新書を読んだので、それをこの素冪の問題に応用してみようと思う。 abc予想: 任意の $ϵ>0$ に対して, ある正の定数 $K(ϵ)\ge 1$ が存在して, 次を満たす: $a$, $b$, $c$ が互いに素な整数で $a+b=c$ を満たすならば, 不等式 \[\max \{|a|, |b|, |c|\} $p$, $q$ を素数として、${\mathrm{\Phi }}_q(x)=p^n$ だったとする。 式を書き直すと $x^q-1=(x-1)p^n$ となるので、$a=x^q$, $b=-1$, $c=(x-1)p^n$ として、 予想の前提を満たす。 よって、予想を仮定すれば \[\max \{x^q, 1, (x-1)p^n\} 一方左辺をより小さくして $(x-1)p^n$ として評価すると、 \[p^{n -1 -\epsilon} 今 $ϵ=1/4$、$K=K(1/4)$ とすると、 \[x^{q-5/2} 11/2\) ならば $x$ が十分大きいときに成り立たなくなる。 つまり、abc 予想が成り立てば、各素数 $q\ge 7$ に対し ${\mathrm{\Phi }}_q(x)$ が2次以上の素冪になるような $x$ は有限個しかない。 またその上限は $q$ と abc 予想の定数 $K(1/4)$ で決まる。 実に強力な予想である。

ブログ移転予定(旧リンク先: http://lowlife.jp/mft/weblog/2013/04/18.html#P2215. 転載先 ) なのでその作業の一環として Floating Log (旧リンク先 http://lowlife.jp/mft/) の内容を抜き出して 痕跡(旧リンク先: http://homepage3.nifty.ne.jp/text/diary/, 再移転先 ) に置いた。 ブログサイトとしての構造は全然保っていないので、まさに書き写された日記というだけの代物。 読み返すと、一文だけの日とかもあって、そういうのは今はツイッターで済ませてしまっているのだということに時代の変化を感じる。 (2022-03-16: リンク先を修正しました)

引き続いて GitHub、とは言ってもそんなに使っていないのだった。 Arithmetica その昔、20世紀の終わり頃、awk がメインのプログラム言語だった頃、多倍長整数の計算がしたくなって awk で実装したもの。 素数判定とか因数分解とかなんかも、メモリーの制約が厳しい環境で動くアルゴリズムを実装してある。 「awk でも多倍長整数が使いたい」という人向け(まあ滅多にいない)。 他は gentoo の翻訳プロジェクトが github を使っているので、そこに参加しているぐらい。

引き続いて BitBucket 編。 BitBucket は(最近は Git も扱えるけど) Mercurial のレポジトリ置き場。 その1: mft_experimental 現在自分の普段使いの OS は Mac OS X なのだが、パッケージマネージャーには Gentoo Prefix を使っている。 それの自分用オーバーレイ。 一時期よりは管理している(独自にパッチを当てたりしている)パッケージが減ってきた。 その2: csg と graphenum どちらもグラフ列挙用のプログラム。 csg は阪大にいたときに間に合わせで作った Python プログラム。9頂点が限界。 graphenum は NII 時代に宇野先生と考えたアルゴリズムの実装で、Python 実装と C 実装があるが、メインは C 実装。 11 頂点まではいけることを確認している。 もう少し速くなると良かったんだけど。 その3: nxbimatch 2部グラフのマッチングを列挙するプログラム。 最大マッチングと完全マッチングの列挙ができる。 グラフ自体は NetworkX という Python のグラフライブラリのものを使っている。 マッチングを一つ探すようなプログラムは良くあるが、列挙するものは見掛けないので自分で実装した。 その4: hcp これは GAE編 その2 の Hilbert class polynomials の実装を公開しているもの。 Google App Engine を公開データベースとして使うサンプル、ぐらいの気持ち。 ニッチなプログラムばかりだ。

技術者スキルシートとかいうものを埋めていたのだが、 どちらかというと趣味で動かしているプロジェクトはどうするのだ。 と、思って結局そこには書かなかったのだが、どこかに書きたくなったのでここに書く。 まずは Google App Engine 上で動かしているものについて。 (この後、BitBucket や GitHub に放り込んであるものなども書くつもり) その1: みんなで正誤表 昔から本の誤植が気になる方だったので @nifty のホームページ(まだ ある )とかでも手書き HTML で正誤表を地味に作っていたのだが、「これウェブアプリにすればいいんじゃない?」と思って GAE で作ったもの。 Python 系の書籍などでごく少数ながら公式っぽく扱ってもらったりして、まあ一番使われていると言って良いだろう。 一時期、SDK のバージョンと Python のバージョンとデータストアの種類と利用するフレームワーク( Kay )とアップデートしなければいけない状態になって、更新に二の足を踏んでいた。 が、最近少し時間があるので、一気に更新と懸案の検索機能追加などを済ませた。 ツイッターの @public_errata で更新情報をつぶやくようにしたが、 これを自動化するのが次に暇になったときの目標。 その2: Hilbert class polynomials NZMATH の機能の一部。 判別式ごとに Hilbert 類多項式の係数を返す、ただそれだけのもの。 データストアの更新前、Master/Slave 方式の時は free quota にぎりぎり収まっていたのに、HRD に代えたらぎりぎりインデックスが収まりきらない状態になってしまった。 無駄にインデックスが張られているフィールドをインデックス無しに変更して様子見。 その3: NZMATH / JSON NZMATH は Python で書いてあるんだし、そのまま GAE に載るよね。 というノリで作られた試作品。 結果が JSON で返るので、この名前になっている。 データストアは一切使っていなかったが、更新しろと言われたので更新した。 放置して旧式の M/S が使えなくなったときにどうなるか見るのもいいかと思っていたが、その2の Hilbert class polynomials ...

転職します。 ポスドクからプログラマーになります。 やり残したこととか: グラフの列挙: とにかく連結単純グラフを(頂点数を指定して)全部列挙する、という課題。 一応、ここ1年半ぐらいこのプログラムを書いていたりしたんですが、 世界最速には追いつけなかったのが心残り。 graphenum $L(m,n)$ の対称鎖分解: ここ半年ぐらい戯れていた未解決の予想。 任意の $m,n$ について $m\times n$ の長方形に入るヤング図形に包含関係で順序を入れた半順序集合は ランクに関して対称な鎖に分解できるだろうという、1980年頃出された予想です。 $L(3,n)$ と $L(4,n)$ は分解できることが知られているので、 その先をどうにかするのが問題で、今もプログラムとか書いて遊んでいます。 Waring 問題的なもの: Waring 問題は、 自然数の $k$ 乗を $g(k)$ 個足したら自然数全部表せるような $g(k)$ が存在する、 というのが元々の設定で、 $G(k)$ 個あれば有限個の例外を除いて表せるような $G(k)$ を求めよう、 というのが本質的な問題。 それを係数付きに拡張して考えると…という問題を、 これもコンピュータで計算してみたらと手を出してみたけど、 最近はMさんどうしているのでしょう。 NZMATH: 数論向けのソフトウェアを Python で作ろうというプロジェクト。 これを始めて、それで博士の学位ももらったんですが、 今は後輩がリーダーとして動いています。動いて…。まあ、うん。 Python3 に移行しないといけない、とか、やることはいろいろあるはず。 NZMATH home NZMATH @ sf.net