京大、16次方程式の判別式計算に成功 | エンタープライズ | マイコミジャーナル たぶんここに書いた話と同じです。n次方程式の判別式の具体的表示（1） - 桃の天然水 n次方程式の判別式の具体的表示（2） - 桃の天然水判別式は、根の差積を自乗したものなの…

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)作者: 結城浩出版社/メーカー: SBクリエイティブ発売日: 2011/02/26メディア: 単行本購入: 19人 クリック: 779回この商品を含むブログ (103件) を見る買って通勤時に4日で読んだけど、とにかく重い。持ち…

判別式を根で表せたので、今度は基本対称式で表すことを考えましょう。3次方程式の場合基本対称式は根をp, q, rで表したとき、 s1 = p + q + r s2 = pq + pr + qr s3 = pqr の3つがあります。判別式は6次なので、これらの基本対称式の積で6次になる式の線形…

現代思想2011年4月号 特集=ガロアの思考 若き数学者の革命作者: 上野 健爾,吉田 輝義,砂田 利一,黒川 信重,小島 寛之,竹内 薫出版社/メーカー: 青土社発売日: 2011/03/28メディア: ムック購入: 15人 クリック: 269回この商品を含むブログ (6件) を見るこの雑…

時代は数論！今すぐ始められる、簡単☆ProjectEuler入門ガイド - EchizenBlog-Zwei Project Eulerを紹介する記事が上がっていたので、退役軍人（？）の私からも少しアドバイスなんぞを。Project Eulerの問題は基本的には1問目から順に解きましょう。最初の方…

最初に戻って、素数のガウス整数の素因数を格納するときに、2つ配列を作ってそれぞれに実部と虚部を格納していましたが、よく考えるとそれぞれは10000以下なので、16ビットごとにそれを格納して一つの整数にすればよいですね。 そうすると、それでも250MBく…

5の約数は、1, 2 + i, 2 - i, 5ですが、整数は足して考えてもよいです。ai + bii(ai ≥ bi ≥ 0)に対して1と5を掛けると、ai + bii, 5ai + 5biiとなり、90度回転したbi - aii, 5bi - 5aiiと実部の和を取ると、6ai + 6biとなり、最初から6としたときと同じにな…

例えば、5の実部が正の約数は、 1, 2 + i, 1 - 2i, 2 - i, 1 + 2i, 5 ですが、15の約数は、5の約数とそれを3倍したものになります。すなわち、s(15) = 4s(15)となります。105なら、s(105) = (1 + 3 + 7 + 21)s(5)となります。 ガウス整数の約数を計算しなけ…

素因数分解をするのではなく、素数の積を生成するのと同じ方法で約数の組を作っていきます。最も素直に書いてみました。 しかし、やっぱり遅いですね。

素因数分解ができればガウス整数での約数の和が求められるようにしましょう。 まず、素数のべき乗について考えます。例えば、3はガウス整数でも素数なので9なら約数は(1, 3, 9)です。一般に4の剰余が3なら同じようになります。 5 = (2 + i)(2 - i)なので、5e…

この問題はメモリを多く使えば簡単のようですが、いつもやっているように300MBを目標にしてPythonでなるべく速くなるようにします。ガウス整数の範囲で約数の和を求めるということなので、素因数分解ができれば約数は簡単に求められるでしょう。ガウス整数の…

昨日アップする順番間違えた。前回の結果、プロセスは2つの子プロセスを発生させるとき、 N E 1 1.0 2 1.5 3 2.0 4 2.33333333333 5 2.66666666667 6 3.0 7 3.33333333333 8 3.58333333333 9 3.83333333333 10 4.08333333333となりました。さらに、 0 ／ 1 …

ガウス整数は、a, bを整数としたとき、a + ibと表せる数を言います。 ガウス整数は、素因数分解の一意性があります。例えば5なら、 5 = (2 + i)(2 - i) と一意に分解できます。ただし、-1、±iを掛けた数は同じ因数とみなします。すなわち、 5 = (-1 + 2i)(-1…

http://projecteuler.net/index.php?section=problems&id=308 ちょっと工夫したら8秒になった。

http://projecteuler.net/index.php?section=problems&id=309 ごく素直に書いたら3分弱で答えが出てきた。しかし、はねられた。何がまずいんだろう。これ以上ないほど素直に書いたので確かめるのが難しい。 ああ、100万以下じゃなくて100万未満か。 明日以降…

http://projecteuler.net/index.php?section=problems&id=308 検索をするとヒントになるようなページが出てくる。これを読むと、なるほどだから素数になるんだとわかる。ちゃんとわかったわけではないが。とにかくこれがヒントになって、あとは速くなるよう…

以前やったように封筒から取り出した回数で分類して速くならないでしょうか。 例えば、A3を使うとして状態が(0, 0, 1)だったとすると、取り出した回数が3回なので、A4までで考えると、(0, 0, 1, 3), (0, 0, 1, 2), (0, 0, 1, 1), (0, 0, 1, 0)の状態が考えら…

元のコードはこうでしたが、 from itertools import izip, count def next(s, k): return s[:k] + (s[k] - 1,) + tuple(n + 1 for n in s[k+1:]) def E(s): num_papers = sum(s) if num_papers == 0: return 0.0 return (1 if num_papers == 1 else 0) \ + s…

あれこれ考えたのですが。 例えば、必要な紙がA3だったとしましょう。すなわち、A4、A5まで紙は切られません。そうすると取りうる状態は、 (1, 0, 0), (0, 1, 1), (0, 1, 0), (0, 0, 2), (0, 0, 1), (0, 0, 0)の6つになります。同じ手順でA4が必要だったとし…

この問題は前回やったようにメモ化を使って簡単に解けますが、動的計画法（DP）ではどうでしょうか。DPの問題点はどの状態になるかどうかわからないところです。よく例に出されるフィボナッチ数列なら、n項をFnとして、F1 = F2 = 1として、F3から順に求めて…

http://projecteuler.net/index.php?section=problems&id=308 少し出遅れた。 英語が全然わからないんだけど。 10分経ったらわかってきた。 2のべきなんか出てこないと思ったら、打ち間違えていただけだった。 2の83乗まで出てきたが。 解ける気がまったくし…

メモ化（memoize）は、Project Eulerで何問かに1問必ず使う手法なので、絶対に覚えましょう。 Project EulerのProblem 151を考えます。意味が分かりにくい問題ですが、分かれば簡単です。まず最初にA1の紙が1枚封筒に入った状態を考えます。この状態を (1, 0…

http://projecteuler.net/index.php?section=problems&id=306 この問題はまともに解くとDPで2つ前の項を使うのでパッと見は並列化できないように思えるが、少し工夫すればほぼ並列化できる。 4分20秒くらいだったのが、4コアで並列化して69秒になった。4分切…

さて、元の問題をもう一度。 n本の棒があります。棒iの長さはaiです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。 プログラミング…

http://projecteuler.net/index.php?section=problems&id=307 どうしてもオーバーフローする 間違えていただけだった。ムダに時間を費やした。5着。 これ、すぐに誕生日の問題と同じだと気づいたのに。 まあ、食事の時間の前に片がついたのはよかった。 フォ…

次の図のように考えるとうまくいきます。赤い部分が長いほうから見て最長の同じ長さの棒があるところで、この長さをkとします。長さが、100, 60, 40, 20, 20, 20, 10, 5, 5とすればkは20です。なぜこうするとよいのかというと、同じ長さの棒があると、そこで…

なんとかDPかメモ化ができないでしょうか。 例えば、棒を長い順に並べなおして、最初が10、9、8だったとすると、これ以降がどうであれ1回目で三角形になることがわかりますね。だから、この場合の数を数えればしらみつぶしよりかなり効率的に数えることがで…

まず、しらみつぶしに調べてみましょう。といってもこんな風にやるのは無理なので、数を小さくします。N = 10、M = 7としてみました。 #include <iostream> #include <algorithm> #include <functional> const int N = 10; const int M = 7; int c[M]; bool is_trianble(int *a) { return a[0] </functional></algorithm></iostream>…

http://projecteuler.net/index.php?section=problems&id=306 結局、N=106としてGrundy数をNまで求めればいいんだけど、O(N2)なのでなんともならなくて、昨日の段階では20時間以上かかると見込んでいた。でも、職場のPCなら8時間もあれば終わるんじゃないか…

http://projecteuler.net/index.php?section=problems&id=306 長い文が来た。5分で理解したけど、正しく理解したか不安。 やっと50が出たけど、よくわからないなあ。 10000でも50秒かかる。